Rule 110 papers Home

We show as work the cyclic tag systems inside evolution space of Rule 110. The incredible construction (original by Matthew Cook) is reconstructed using our regular language to Rule 110. You can found some differences of Stephen Wolfram book A New Kind of Science, because it has mistakes that they do not allow a good reconstruction. The mistakes were clarified by Cook in November 2002 (personal communication).

You can see the original demonstration and results of:
• Matthew Cook, "Universality in Elementary Cellular Automata," Complex Systems, Volume 15, Number 1, p. 1-40, 2004.
• Stephen Wolfram, A New Kind of Science, Wolfram Media, Inc., Champaign, Illinois, 2002. (ISBN 1-57955-008-8)
other relevant reference from:
• Harold V. McIntosh, "Rule 110 Is Universal!," http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html, June 30, 2002.
• Turlough Neary and Damien Woods, "P-completeness of cellular automaton Rule 110," Lecture Notes in Computer Science 4051, p. 132-143, Venice, July 2006.
(alternative version available from http://www.bcri.ucc.ie/BCRI_52.pdf)
• Kenichi Morita, "Simplifying Universal One-Dimensional Reversible Cellular Automaton on Infinite Configurations," Automata 2006, Hiroshima University, 2006.
(presentation is available from http://www.iec.hiroshima-u.ac.jp/automata2006/files/Morita.pdf)
and all complete details of our reconstruction from our paper:
• "Reproducing the cyclic tag systems developed by Matthew Cook with Rule 110 using the phases fi_1," http://uncomp.uwe.ac.uk/genaro/papers.html, in elaboration.
Figure 1 illustrate the necessary components by package of gliders, each one with a label to our reconstruction. Figure 2 show the schematic diagram to illustrate the transformation of the package of gliders. Figures 3 to 13 show our full simulation step-by-step, each stage/window is showing the exact position (x,y).

Writing the sequence 1110111 on the tape of cyclic tag system and a leader component at the end with two solitons. Our reconstruction is to an evolution space of 56,240 cells to 57,400 generations, i.e., a space of 3,228,176,000 cells with a computer Pentium II to 233 mhz, operating system OpenStep and 256MB of RAM (February 2003). Collaborations of Harold V. McIntosh and Juan C. Seck Tuoh Mora.

Initial condition to reproduce the cyclic tag system, available in a text file ctsR110.txt

Fig. 1 Components to cyclic tag system in Rule 110.

Fig. 2 Schematic diagram.

Fig. 3 Initiating the construction.

Fig. 4 Construction of the element 1Add$\_\bar{E}$ with a primary component.

Fig. 5 4$\_A^{4}$ package of gliders.

Fig. 6 Producing the element 1Ele$\_C_{2}$.

Fig. 7 Producing the element 1Add$\_\bar{E}$.

Fig. 8 Producing the element 0Add$\_\bar{E}$.

Fig. 9 Reading data crossing transformed data.

Fig. 10 Erasing the element 0Ele$\_$C2.

Fig. 11 Erasing unchanged data blocks by the reaction $A^{3} \rightarrow \bar{E}$.

Fig. 12 Final part of the data deleting.

Fig. 13 The last window into of our simulation utilizing 3,228,176,000 cells.