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?


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