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?

Improve this question
$\endgroup$
1
  • 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, 2017 at 23:59

0

Reset to default