[racket] Checking infinite loops

From: Eric Tanter (etanter at dcc.uchile.cl)
Date: Mon Oct 4 08:37:09 EDT 2010

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.
For instance, in the simply-typed lambda calculus, this program is easy, since any STLC program does terminate. (but of course then, STLC is not complete)

-- Éric

Posted on the users mailing list.