[racket] Checking infinite loops

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