From: nzook@math.utexas.edu

To: cypherpunks@toad.com

Message Hash: b24c6419a8c75e989be25f7e3baae78f718771eba4cea2518eee33c6fc0dda9b

Message ID: <9407261520.AA11661@vendela.ma.utexas.edu>

Reply To: *N/A*

UTC Datetime: 1994-07-26 15:24:22 UTC

Raw Date: Tue, 26 Jul 94 08:24:22 PDT

```
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
```

Return to July 1994

- Return to “hughes@ah.com (Eric Hughes)”
- Return to “m5@vail.tivoli.com (Mike McNally)”
- Return to “nzook@math.utexas.edu”
Return to “tcmay@netcom.com (Timothy C. May)”

- 1994-07-26 (Tue, 26 Jul 94 08:24:22 PDT) - Re: GUT and P=NP -
*nzook@math.utexas.edu*- 1994-07-26 (Tue, 26 Jul 94 08:43:22 PDT) - Re: GUT and P=NP -
*m5@vail.tivoli.com (Mike McNally)*- 1994-07-26 (Tue, 26 Jul 94 11:49:58 PDT) - Re: GUT and P=NP -
*tcmay@netcom.com (Timothy C. May)*

- 1994-07-26 (Tue, 26 Jul 94 11:49:58 PDT) - Re: GUT and P=NP -
- 1994-07-26 (Tue, 26 Jul 94 10:05:00 PDT) - GUT and P=NP -
*hughes@ah.com (Eric Hughes)*

- 1994-07-26 (Tue, 26 Jul 94 08:43:22 PDT) - Re: GUT and P=NP -