[5748] in cryptography@c2.net mail archive
Re: having source code for your CPU chip -- NOT
daemon@ATHENA.MIT.EDU (Ray Hirschfeld)
Fri Sep 24 09:57:12 1999
Date: Fri, 24 Sep 1999 10:16:45 +0200 (MET DST)
Message-Id: <UTC199909240816.KAA33882.ray@prauw.cwi.nl>
From: Ray Hirschfeld <R.Hirschfeld@cwi.nl>
To: eli+@cs.cmu.edu
Cc: cryptography@c2.net
In-reply-to: <199909232239.PAA13902@blacklodge.c2.net> (message from Eli
Brandt on Thu, 23 Sep 1999 18:38:57 -0400 (EDT))
Reply-To: ray@unipay.nl
> Date: Thu, 23 Sep 1999 18:38:57 -0400 (EDT)
> From: Eli Brandt <eli@v.gp.cs.cmu.edu>
>
> 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.)
