> Date: Thu, 23 Sep 1999 18:38:57 -0400 (EDT)
> From: Eli Brandt <[EMAIL PROTECTED]>
>
> Arnold Reinhold wrote:
> > Perry, if you really believe that the question of whether a given
> > lump of object code contains a Thompson Trap is formally undecidable
> > I'd be interested in seeing a proof. Otherwise Herr Goedel has
> > nothing to do with this.
>
> That sure smells undecidable to me. Any non-trivial predicate P on
> Turing machines (non-trivial meaning that both P and not-P are
> non-empty) is undecidable by Rice's Theorem. There are technical
> issues in encoding onto the tape all possible interactions with the
> world -- the theorem doesn't apply if some inputs are deemed illegal
> -- but, hey, it's all countably infinite; re-encode with the naturals.
I don't think Rice's Theorem applies in this case because it's not a
language property. The non-trivial predicate should be on
r.e. languages, not on Turing machines. For example, determining
whether a Turing machine accepts a string consisting of 3 symbols is
undecidable by Rice's Theorem (since some r.e. languages contain
strings of 3 symbols and others don't), but determining whether a
Turing machine has 3 states is not.
That's not to say that it's not undecideable! Just that Rice's
Theorem is insufficient to prove it (unless you can somehow
reformulate it as a language property). Instead you might try
directly reducing some undecideable problem to it.
(For those who don't know the terminology, r.e. = recursively
enumerable = accepted by a Turing machine.)
