From: collins@newton.apple.com (Scott Collins)
Date: Sat, 31 Jul 93 17:47:55 PDT
To: cypherpunks@toad.com
Subject: Re: Programs that prove themselves.
Message-ID: <9308010213.AA26390@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Intuitively, this is akin to Godels incompleteness theorem.

Or read "What is the name of this book?" by Raymond Smulliyan.  A multitude
of interesting problems are posed, around the interaction of Knights,
Knaves and Normals.  Knights always tell the truth.  Knaves always lie. 
Normals sometimes tell the truth and sometimes lie.

A Normal can 'pretend' to be a Knight, because he is not constrained in his
answers, therefore, he can always answer as a Knight would.

Your program might be a Knight (i.e., constrained to always tell the truth)
but a 'Normal' program could always simulate your program.  It would
perform all the functions of your program with stolen code, but inside it
wouln't prove itself to itself.

It is only in the presence of some unforgeable distinguishing
characteristic recognized by a trustworthy *outside* observer, that a
bystander can tell Normal from Knight.

Sign your software and have users check the signature with a trusted
outside signature verification mechanism (e.g. a 'good' copy of PGP, or a
secure operating system).

I know this is not the information you are looking for.  I also know this
is not a pipe.

Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   1 Infinite Loop, MS 301-2C   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024/669687   catalyst@netcom.com