[5750] in cryptography@c2.net mail archive
Re: having source code for your CPU chip -- NOT
daemon@ATHENA.MIT.EDU (Matt Crawford)
Fri Sep 24 10:01:25 1999
Message-Id: <199909241344.IAA26402@gungnir.fnal.gov>
To: crypto list <cryptography@c2.net>
From: "Matt Crawford" <crawdad@fnal.gov>
In-reply-to: Your message of Thu, 23 Sep 1999 18:38:57 EDT.
<199909232239.PAA13902@blacklodge.c2.net>
Date: Fri, 24 Sep 1999 08:44:58 -0500
> > 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.
>
> 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 no Turing machines. Real computers are finite, and real
source codes are finite. I'm sure that if you set a limit on the
length of the source code which is recognized by the supposed trap, a
sufficiently large FSM can decide in a finite time whether there's a
trap.
______________________________________________________________________________
Matt Crawford crawdad@fnal.gov Fermilab
"A5.1.5.2.7.1. Remove all classified and CCI boards from the COMSEC equipment,
thoroughly smash them with a hammer or an ax, and scatter the pieces."
