Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer.

I was wondering what specific initial conditions are used to model basic computations. For the sake of specificity, my question is--what initial conditions do I have to give Rule 110 if I want to simulate $1 + 1$?

Note: On page 681, Wolfram provides pictures of "black elements" and "white elements" in Rule 110, but it is hard to tell which initial conditions created them. On page 1116 (in the "Notes" section), he gives Mathematica code to set up the cyclic tag system. But I want to know specifically which initial conditions will simulate the computation $1 + 1$.

share|improve this question
My understanding is that the proof is due to Matthew Cook, and was published without credit by Wolfram. Cook outlines his proof in complex-systems.com/pdf/15-1-1.pdf and he has a more recent paper arxiv.org/abs/0906.3248 that also looks helpful in answering your question. –  David Eppstein Apr 5 '12 at 19:09
Cook provides as stated in the comment a mechanical proof. Converting both data and code to an initial condition for rule 110. –  Sonia Apr 6 '12 at 10:40
add comment

1 Answer

up vote 1 down vote accepted

the rule 110 initial condition constructions are extremely intricate even for simple computations and generally cannot be constructed by hand. one would generally start with a real/concrete TM [turing machine] built to compute your problem, ie the complete state table (TMs are of course alluded to in thousands of TCS papers but rarely actually built directly).

generally the papers build initial conditions using complex algorithmic conversions to tag systems. the cook paper cited by DE in comments above[1] does improve the simulation time by a polynomial instead of exponential construction. in other words, theres more than one way to create suitable initial conditions. another recent construction with emphasis on regular languages by martinez et al can be found[2]. the authors of the papers generally do not seem to release code they used to construct their paper results [scanning the two papers below], a legitimate complaint that could be made of much research papers in TCS which tend to give short shrift to experimental approaches[3] even as they seem to focus on them.

so once you have the TM alphabet and state table one runs the conversion algorithms described but not really explicitly/manifestly implemented in the papers [because no code is given, only a prose description of the algorithm(s)] which take the TM alphabet and state table as input and then output a tag-system setup and 110 initial tape conditions that simulates the TM. my understanding is that in some cases, an infinite periodic starting "tape" pattern may be required.

in their papers they do not even seem to mention what coding languages they use for their simulations/experiments. they might release code if you contact them directly. therefore wolframs release/publishing of some mathematica code you mention above [nice but now rather dated based on later developments in the area] seems to be an exception in this area. therefore to actually independently construct concrete machines built using these techniques a researcher might have to reimplement the algorithms described in the papers.

footnote: the exact TM problem must be defined with some care because in your case, does a TM that simply erases and outputs 2 to its tape compute 1+1? you probably want a TM that computes $a+b$ and starts with input 1,1 on the tape.

[1] A concrete view of rule 110 computation by matthew cook

[2] Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases fi_1 by Martinez et al

[3] Is"Experimental Complexity Theory" being used to solve open problems?

share|improve this answer
on further thought this response should be clarified. there are other conversions of misc (arbitrary) TMs to tag systems [which are proven turing-complete] that are not covered in these papers. these papers give algorithms to convert from a tag system to rule 110 initial conditions. in the question, a reference is given to wolfram's code that converts a tag system to rule 110 starting conditions. if one wanted to code the a+b algorithm in a tag system and avoid the TM construction step, that would be possible, but few papers seem to construct tag system machines/algorithms from scratch. –  vzn Jun 10 '12 at 16:17
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.