[plt-scheme] OT: not the halting problem, but what is it?

From: Jos Koot (jos.koot at telefonica.net)
Date: Tue May 4 13:05:13 EDT 2010


-----Original Message-----
From: samth0 at gmail.com [mailto:samth0 at gmail.com] On Behalf Of Sam
Sent: 04 May 2010 17:49
To: Jos Koot
Cc: John Clements; Prabhakar Ragde; plt-scheme at list.cs.brown.edu
Subject: Re: [plt-scheme] OT: not the halting problem, but what is it?

On Tue, May 4, 2010 at 11:37 AM, Jos Koot <jos.koot at telefonica.net> wrote:
> I don't think the relationship is coincidental. The fact that "does 
> halt" or "does have a normal form" is not decidible is, imho, a direct 
> consequence of the more general fact that there is no complete non trivial

Well, Rice's theorem and the Halting problem are quite related.  But the
statement I made wasn't about non-trivial predicates, but about predicates
at all.  There are uncountably many predicates on programs that are not
predicates on computable functions at all.

sam th
samth at ccs.neu.edu

Posted on the users mailing list.