This question already has an answer here:
- How is the rule 110 Turing complete? 2 answers
The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean?
I do know what Turing completeness mean. Roughly speaking a language is Turing complete if any program / algorithm can be expressed using this language.
However, the rule 110 is a fixed set of instructions of how to modify a sequence of zero and ones. So, how can we express any program as a rule 110? If we change the rule 110 it will not be the rule 110 anymore?
I might guess that both the input sequence and the program itself should be encoded into a single sequence of the zeros and ones and then we need to run the rule 110 on it. At some point we will get a sequence that can be interpreted as the output generated by the given program for the given input. Is my interpretation correct?