2
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by Yuval Filmus, David Richerby, adrianN, Evil, Community Oct 19 '17 at 7:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 Oct 18 '17 at 23:59