Hacker News Reader

Comment by klyrs | Hacker News Reader

  +[->+]

Turing machines can also eat tape infinitely. If they're allowed such an appetite, why would we forbid it for rule 110?

To be fair I've never been 100% sold on the Turing-completeness of rule 110, but your argument isn't landing with me either.

View on HN

The initial state of a Turing Machine tape is that beyond the finite-length input, all of the rest of the infinite tape is blank.

https://en.wikipedia.org/wiki/Turing_machine#:~:text=Cells%2...

Whereas the Rule 110 Cyclic Tags engine requires the infinite tape to contain infinite repetitions of structured patterns, even in order to simply run "while(true)". That's a key difference.

I also agree with zamadatix's sibling comment.

Oh, I see what you mean. That sounds quite easy to work around, actually. Due to the speed of light, only a section containing the disruptions to the repeated pattern need be considered for the initial state; and then you can compute outward from that.

"Allowed" is probably covering too wide a meaning in your description. Just because something is capable of defining infinite consumption does not mean it was allowed to do so in the proof.

Reply on news.ycombinator.com