Re: Proof by construction, again (was Re: [sl4] prove your source code)

From: Matt Mahoney (
Date: Sat Jul 19 2008 - 17:30:35 MDT

--- On Sat, 7/19/08, Tim Freeman <> wrote:

> From: Tim Freeman <>
> Subject: Re: Proof by construction, again (was Re: [sl4] prove your source code)
> To:
> Date: Saturday, July 19, 2008, 3:29 PM
> --- On Sat, 7/19/08, Tim Freeman <>
> wrote:
> > Entity A could prove to entity B that it has source
> code S by
> > consenting to be replaced by a new entity A' that
> was constructed by a
> > manufacturing process jointly monitored by A and B.
> During this
> > process, both A and B observe that A' is
> constructed to run source
> > code S. After A' is constructed, A shuts down and
> gives all of its
> > resources to A'.
> From: Matt Mahoney <>
> >But A cannot know if S is its own source code. (I
> assume that S
> >includes current state information needed to make a
> copy of
> >itself). If it could know, then A could simulate itself
> (with infinite
> >recursion, which is impossible).
> The above proof technique also leads to the conclusion that
> backing up
> my computer is impossible. My computer cannot possibly
> know all of
> the bits it uses, since if it could, it could simulate
> itself, with
> infinite recursion, which is impossible.

No. The backup disk is part of the computer. Its original contents are lost.

More generally, two machines cannot know each other's states because then each machine would have more information than the other (as measured by Kolmogorov complexity).

-- Matt Mahoney,

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT