4 ms·
+[->+] 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
by klyrs 2y ago
+[->+]
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.
- zamadatix 2y ago"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.
- upwardbound 2y agoThe 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%20that%20have%20not%20been%20written%20before%20are%20assumed%20to%20be%20filled%20with%20the%20blank%20symbol 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.
- klyrs 2y agoOh, 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.