2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A universal Turing machine is a single Turing machine with a fixed set of state transitions. Programming a UTM means providing the program as input to the UTM, i.e. on the initial tape. $\endgroup$ – Derek Elkins left SE Oct 18 '17 at 23:59