On 22/12/2010 11:07 PM, Darren New wrote:

> Initializing an infinite tape for a
> turing machine at least makes it more powerful than one with an
> uninitialized tape.

OK.

> And rule 110 needs an infinitely initialized tape.

I'm still not convinced that this is actually necessary.

In other words, I suspect that rule 110 *is* Turing complete, it's just 
that the proof provided is a bit weak.

Post a reply to this message