Re: GUT and P=NP

>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

nzook@fireant.ma.utexas.edu writes:
 > 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.

Can you (without being an asshole) explain why exactly each tape
position may contain only a simple integer?  It's perfectly reasonable
to define the tape alphabet to be an arbitrary set; can the set not
be uncountably infinite?  If not, why not?

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

> Can you (without being an asshole) explain why exactly each tape
> position may contain only a simple integer?  It's perfectly reasonable
> to define the tape alphabet to be an arbitrary set; can the set not
> be uncountably infinite?  If not, why not?
> 
> | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |

Sorry for jumping in here, despite promising myself not to. I've been
deleting all of the circular debate on quantum computers, Turing
machines, etc. But for some reason my tape stopped on this one.

Turing machines are what they are: storage for finite symbols on a
tape, read by some gadget that looks at what a storage site has in it
and makes some decision, possibly moving to another site, writing a
new symbol, etc. This, by the way, echoes reality pretty well: all
actual machines store finite symbols in actual locations.

Steven Smale of Berkeley has studied what happens if a machine can
store *real numbers* in the memory locations. Amazing things happen. 

But this ain't the real world.

And it ain't crypto.

--Tim May



-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

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.

Famous last words?

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

I think you've completely missed the point.  The proposed
computational device had as its symbol alphabet an uncountable set.
It's a perfectly good mathematical abstraction.  It's doesn't matter
that it can't be implemented.

And let's not call such a machine a Turing machine, OK?  Turing goes
on at great length in his original paper about how the symbols can't
be too similar to each other.

And to answer the point of another writer, this machine may have only
finitely many states, but the state transition table, being the
cartesian product of the states and the symbols, is also uncountable.
In fact, I would suspect that such a machine only needs a single
state; an interesting bit of research, to be sure.

Eric