[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Cypherpunks Mailing List <[email protected]>*Subject*: Re: There's a hole in your crypto...*From*: Nathan Zook <[email protected]>*Date*: Thu, 10 Aug 1995 00:12:50 -0500 (CDT)*In-Reply-To*: <[email protected]>*Sender*: [email protected]

On Mon, 7 Aug 1995, Futplex wrote: > 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 :) If a statement is vacuous, it needs refining :-). If I were to state that "Program X is not a Turing Machine", I would be stating that program X does not model all Turing machines throught its input. It is the ability of some Turing machines to model all Turing machines through their input that makes them undecidable. > 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. The problem here is that it is the interesting cases with which we are concerned. If someone wants to write a computer program to "verify" my proof of the RSA algorithm, fine. But I have to be convinced that there program does what they claim before I care. And since their program takes mathematical theorems as input, it is already demonstrating near-Turing ( :-P) behavior. > 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. I'll buy that. > -Futplex Nathan

**References**:**Re: There's a hole in your crypto...***From:*[email protected] (Futplex)

- Prev by Date:
**Re: Prime Number Gen's.** - Next by Date:
**Re: "S1" encryption system (was: this looked like it might be interesting)** - Prev by thread:
**Re: There's a hole in your crypto...** - Next by thread:
**Re: There's a hole in your crypto...** - Index(es):