clipka wrote:
> Am 23.12.2010 00:07, schrieb Darren New:
> 
>> 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.
> 
> That's not a problem in cellular automata, as they - by definition - 
> have an infinitely initialized "tape" (or, rather, grid of cells).

Well, there's a problem with that, tho. Let's initialize the grid to be 1 if 
the program represented by the X coordinate halts with the input represented 
by the Y coordinate, and 0 if it doesn't. Bingo - just solved the halting 
problem.

I'm not convinced. I'm not sure either way, mind. It just seems flakey and 
not something you can assume.

Yes, a CA does an infinite amount of computation in each step. It's not 
obvious to me that doing an infinite amount of computation before you 
*start* makes it legal. Doing it with a multi-stage CA would work, but then 
it wouldn't be rule 110 any more.

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

Post a reply to this message