From: Nathan Zook <nzook@bga.com>
To: Cypherpunks Mailing List <cypherpunks@toad.com>
Message Hash: 14c70c26a82cbd35bd985eacd0693e48d8dd06eea482e475c71ef245ab0b6fce
Message ID: <Pine.3.89.9508100049.D21852-0100000@maria.bga.com>
Reply To: <9508070918.AA19988@cs.umass.edu>
UTC Datetime: 1995-08-10 05:12:59 UTC
Raw Date: Wed, 9 Aug 95 22:12:59 PDT
From: Nathan Zook <nzook@bga.com>
Date: Wed, 9 Aug 95 22:12:59 PDT
To: Cypherpunks Mailing List <cypherpunks@toad.com>
Subject: Re: There's a hole in your crypto...
In-Reply-To: <9508070918.AA19988@cs.umass.edu>
Message-ID: <Pine.3.89.9508100049.D21852-0100000@maria.bga.com>
MIME-Version: 1.0
Content-Type: text/plain
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
Return to August 1995
Return to “Nathan Zook <nzook@bga.com>”