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