# [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