3 ms·

That sentence did not contain any reference to Turing machines. "Rule 110" by itself is just a Boolean function, which, as I have mentioned is completely equiv

That sentence did not contain any reference to Turing machines. "Rule 110" by itself is just a Boolean function, which, as I have mentioned is completely equivalent with the pair AND + XOR. By using a suitably initialized memory and an automaton that besides other features that are needed to address the memory (a.k.a. "move the tape", when the memory is modeled as a tape or shift register) is able to compute "Rule 110", it is possible to build the equivalent of a Turing machine. My point is that using "Rule 110" does not bring any simplification or any other advantage instead of just using the pair AND + XOR. The machine using "Rule 110" and which is equivalent with a Turing machine is completely equivalent with an otherwise identical machine, except that the "Rule 110" function is replaced by the AND + XOR pair. The only effect of "Rule 110" is to make the description of the machine more complicated and more obscure and if that machine were implemented in real hardware or software it would be more inefficient, due to redundant gates or computations. Even using the equivalent machine with AND + XOR does not bring any advantage instead of the traditional definition of a Turing machine, which uses higher-level functions, whose implementation details are not relevant for proving Turing completeness.

eigenket 2y ago
Rule 110 is not a simple boolean function. It's a cellular automata. The boolean function is part of its description but not the whole thing. For example if you take the standard rule 110, but run it with a different background pattern (for example the one where every cell is by default in state 0) it isn't Turing complete any more. I suggest you take a look at the proof that 110 is Turing complete (pdf here http://www.complex-systems.com/pdf/15-1-1.pdf http://www.complex-systems.com/pdf/15-1-1.pdf). It doesn't just follow from elementary properties of the boolean gates AND and XOR.
- lupire 2y ago
  To be fair, it's pretty nasty that the Rules are named ambiguously, where a critical part of the "Rule+" of interest is something (the background pattern) in the CA system but outside the Rule system. It's fixable, but still gross, and plays into Wolfram's style of making things seem more profound by hiding the ball.

eigenket 2y ago

Rule 110 is not a simple boolean function. It's a cellular automata. The boolean function is part of its description but not the whole thing. For example if you take the standard rule 110, but run it with a different background pattern (for example the one where every cell is by default in state 0) it isn't Turing complete any more. I suggest you take a look at the proof that 110 is Turing complete (pdf here http://www.complex-systems.com/pdf/15-1-1.pdf http://www.complex-systems.com/pdf/15-1-1.pdf). It doesn't just follow from elementary properties of the boolean gates AND and XOR.

lupire 2y ago
To be fair, it's pretty nasty that the Rules are named ambiguously, where a critical part of the "Rule+" of interest is something (the background pattern) in the CA system but outside the Rule system. It's fixable, but still gross, and plays into Wolfram's style of making things seem more profound by hiding the ball.