> > 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 [EMAIL PROTECTED] 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."