[5752] in cryptography@c2.net mail archive
Re: having source code for your CPU chip -- NOT
daemon@ATHENA.MIT.EDU (Eli Brandt)
Fri Sep 24 12:05:34 1999
Message-Id: <199909241549.IAA18901@blacklodge.c2.net>
To: crypto list <cryptography@c2.net>
Date: Fri, 24 Sep 1999 11:49:10 -0400 (EDT)
From: Eli Brandt <eli@v.gp.cs.cmu.edu>
In-Reply-To: <UTC199909240816.KAA33882.ray@prauw.cwi.nl> from "Ray Hirschfeld" at Sep 24, 99 10:16:45 am
Reply-To: eli+@cs.cmu.edu
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Ray Hirschfeld wrote:
> > 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.
Yeah, I was trying to avoid bringing in the term "recursively
enumerable", and I tripped myself up. The "technical issue" I mumbled
about was supposed to address this, but that reduction is in the wrong
direction: I need to show that if you can answer Thompson(M) you can
answer Thompson'(L), not the other way around. Which, when one stops
waving one's hands and thinks about it, is not going to happen, not
without drawing on some information about Thompson().
--
Eli Brandt | eli+@cs.cmu.edu | http://www.cs.cmu.edu/~eli/
