Am 04.01.2011 19:47, schrieb Darren New:
> 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.

You just added an oracle.

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

Why not? Both CA and Turing machine are theoretical constructs anyway, 
so you can assume just about anything.

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

Actually you don't even need pre-initialized cells (or infinitely many 
cells, for that matter) any more than you do with a Turing machine, if 
you go for a CA with more than just two states.

All you need is a set of special states to represent some 
"initialization area" which you place on both sides of your "payload 
data", defined in such a way that it moves outward at 1 cell per cycle 
while auto-generating the desired "background pattern".

There - you just eliminated the need for any pre-calculation. As the 
maximum propagation speed of any pattern in a CA is 1 cell per cycle, 
you are guaranteed to have the "background pattern" wherever you need 
it. Flaw fixed.

Post a reply to this message