From: futplex@pseudonym.com (Futplex)
Date: Mon, 7 Aug 95 02:18:29 PDT
To: cypherpunks@toad.com (Cypherpunks Mailing List)
Subject: Re: There's a hole in your crypto...
In-Reply-To: <Pine.3.89.9508042253.A3820-0100000@jake.bga.com>
Message-ID: <9508070918.AA19988@cs.umass.edu>
MIME-Version: 1.0
Content-Type: text/plain


No crypto/privacy relevance, delete or flame now....

Nathan writes:
> This is why the "not a Turing machine" assertion that the "Professor" is 
> important.  We know that Turing machine is undecidable, so if we want to 
> limit behavior, we can't have one.  BUT---we don't know that being a 
> Turing machine is equivalent to having "unpredictable" behavior.  
> Furthermore, a "proof" of the "not a Turing machine" assertion is going 
> to have to be done by--you guessed it--a computer.  And this computer is 
> running a program which definitely IS a Turing machine, if it is capable 
> of "proving" that other (suitably non-trivial) programs are not Turing 
> machines.

I think this is a bit misguided. The Turing machine (TM) is an extremely general
abstract model of computation. The gargantuan hunk of code that runs the 
Space Shuttle can be viewed as a Turing machine, as can a "Hello world" program
written in Visual BASIC. So, there's not really a question about whether or
not we're talking about Turing machines (unless perhaps you want to discuss
quantum theorem provers and QTMs :) 

Now, Rice's Theorem says that all non-trivial properties of TMs are undecidable.
If I pick a "non-trivial" property, I can't conceivably build a TM ("write a
program", if you like) that, upon input of the specification of an arbitrary TM,
can tell whether or not that TM exhibits the property I picked. This does not
mean that I can't decide whether some particular TMs have that property or not --
I can. I just can't write down a procedure that handles the general case.

Also, this theorem clearly hinges on the meaning of "trivial". From what I've
seen, a very strict interpretation is largely appropriate; nearly everything
except the least exciting of trivial low-level properties of TMs seems to come
out to be "non-trivial" in this regard. The proof of the theorem is more
precise about this, naturally, but I've found this useful as a working
colloquial definition.

-Futplex    
August 7, 1995     "Enola Gay, you should have stayed at home yesterday" -OMD