[racket] Checking infinite loops

From: Patrick Li (patrickli.2001 at gmail.com)
Date: Mon Oct 4 11:56:08 EDT 2010

Thanks for explaining that to me. I never actually looked up the formal
definition of Turning-Completeness before.

So this seems rather positive. Through some clever search algorithms, or
heuristics, we can have a infinite-loop checker that works well enough in
practice.

  -Patrick

On Mon, Oct 4, 2010 at 10:55 AM, Eric Tanter <etanter at dcc.uchile.cl> wrote:

> 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
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101004/4b232d0b/attachment.html>

Posted on the users mailing list.