Re: What is the Result from Invoking this Halt Function?

From: r.e.s. (r.s_at_ZZmindspring.com)
Date: 08/14/04 

Date: Sat, 14 Aug 2004 06:38:42 GMT

">parr(*>" <gniKyruaL@tenretnitb.moc> wrote ...
> For
> machines with <4 states, the 'halting problem' is solvable - Such
> machines are weaker than current computers. With 4 states, the
> 'halting problem' has not yet been analysed to determine whether it
> is solvable or unsolvable. Turing, showed that his proof of
> unsolvability held for machines with 5 or more states, but said "By
> unimportant modifications".

I think you're confusing the number of states in a TM with the
number of quantifiers in a certain logical formula that Turing
associated with the TM. (There exist UTMs with only 2 states!)

--r.e.s.

Quantcast