[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