[racket] Checking infinite loops

From: Eric Tanter (etanter at dcc.uchile.cl)
Date: Mon Oct 4 10:55:03 EDT 2010

right ;)

-- Éric


On Oct 4, 2010, at 10:02 AM, Stephen Bloch wrote:

> 
> 
> 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.