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

Ok
Jos 

-----Original Message-----
From: samth0 at gmail.com [mailto:samth0 at gmail.com] On Behalf Of Sam
Tobin-Hochstadt
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
predicate.

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