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

From: Sam Tobin-Hochstadt (samth at ccs.neu.edu)
Date: Tue May 4 11:48:32 EDT 2010

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

Posted on the users mailing list.