http://en.wikipedia.org/wiki/Turing_completeness

"""
A computer with access to an infinite tape of data is sometimes more 
powerful than a Turing machine, because the tape can in principle contain 
the solution to the halting problem, or some other undecidable problem. An 
infinite tape of data is called a Turing oracle. Even a Turing oracle with 
random data is not computable (with probability 1), since there are only 
countably many computations but uncountably many oracles. So a computer with 
a random Turing oracle can compute things that a Turing machine cannot.
"""

Ha! I knew there was a reason I thought the argument that Rule 110 was 
turing complete was a bit flakey.  Initializing an infinite tape for a 
turing machine at least makes it more powerful than one with an 
uninitialized tape. And rule 110 needs an infinitely initialized tape.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message