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

Also note that rule 110 was proven to be /Turing complete/, not /Turing 
equivalent/.

Post a reply to this message