From: nzook@math.utexas.edu
Date: Tue, 26 Jul 94 08:24:22 PDT
To: cypherpunks@toad.com
Subject: Re: GUT and P=NP
Message-ID: <9407261520.AA11661@vendela.ma.utexas.edu>
MIME-Version: 1.0
Content-Type: text/plain


>berzerk@xmission.xmission.com writes:
> > One last word on this.  Try and represnet a continum of states by an 
> > infinite turing machene.  Go ahead, I dare you.  You can't.<=big period.

>Could I not let each position on the tape represent a real value in
>[0...1]?

>| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
>| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
>|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

HAHAHAHAHAHAHAHAHAHAHA  ROFL HAHAHAHAHAHAHAHAHAHAHA

Okay.  So I should be so rude.  People please.  When someone, especially
like berzerk or tcmay makes a strongly definitive statement, PLEASE try
not to show your ignorance to the whole group.

Cantor demonstrated, near the turn of the century, that no such system
can represent all reals in [0,1].  Boring technical explanation follows.

Let f be a function from the integers to [0,1].  Note that the Turing
tape has precisely one space for each integer, so this function cooresponds
to your idea.

I claim that f is not onto.  (ie: you cannot represent all reals this way.)
Write a decimal expansion for each elment in the range of f, and order
them as follows:

f(0) = .d(1,1) d(1,2) d(1,3) d(1,4) ....
f(1) = .d(2,1) d(2,2) d(2,3) d(2,4) ....
f(-1)= .d(3,1) d(3,2) d(3,3) d(3,4) ....
f(2) = .d(4,1) d(4,2) d(4,3) d(4,4) ....
f(-2)= .....

construct a, in [0,1], as follows:
let g be a function from {0,1,2,3,4,5,6,7,8,9} to {5,6} s.t. g(x) = 5 if
x>5, g(x) = 6 if x < 6.
Let a = sum for i = 1 to infinity of g(di,i)/10^i.

I claim that a is not in the range of f.
Is f(0) = a?  No, the first digits differ.
Is f(1) = a?  No, the second digits differ.
Is f(-1)= a?  No, the third digits differ.

You get the picture.  There are a couple of small details left out, you
should be able to fill them in.

Historical note:  I believe that is the original construction.
Further historical note:  You can see the germ of Godel's work here.

Nathan