[racket] Checking infinite loops

From: Stephen Bloch (sbloch at adelphi.edu)
Date: Mon Oct 4 10:02:41 EDT 2010

On Oct 4, 2010, at 8:37 AM, Eric Tanter <etanter at dcc.uchile.cl> wrote:

> Just for the sake of precision:
> On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:
>> But there is NO program, in ANY language, that takes in another program and always tells correctly (in finite time) whether that other program contains an infinite loop.
> The "in ANY language" is too much: This is true of any _Turing complete_ language.

Even more precisely, this is true if the language of the program being analyzed is Turing complete.  The language in which you write the alleged analyzer doesn't matter, as long as it can be called from a Turing-complete language.

Stephen Bloch
sbloch at adelphi.edu

Posted on the users mailing list.