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

*To*: [email protected] (Cypherpunks Mailing List)*Subject*: Re: There's a hole in your crypto...*From*: [email protected] (Futplex)*Date*: Mon, 7 Aug 1995 05:18:21 -0400 (EDT)*In-Reply-To*: <[email protected]> from "Nathan Zook" at Aug 4, 95 11:03:12 pm*Reply-To*: [email protected] (Cypherpunks Mailing List)*Sender*: [email protected]

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

**Follow-Ups**:**Re: There's a hole in your crypto...***From:*[email protected] (Dr. Frederick B. Cohen)

**Re: There's a hole in your crypto...***From:*Nathan Zook <[email protected]>

**References**:**Re: There's a hole in your crypto...***From:*Nathan Zook <[email protected]>

- Prev by Date:
**Quibbling about definitions of "proof"** - Next by Date:
**Re: There's a hole in your crypto...** - Prev by thread:
**There's a hole in your reasonoing** - Next by thread:
**Re: There's a hole in your crypto...** - Index(es):