Critical State and Turing Completeness of One-Dimensional Cellular Automata
75
Fig. 4.9 Left: Rule 90, Right: Rule 110
For example, in the world of his “Rule 90,” if only one point is set to •, an evolution
diagram like Fig. 4.9 (left) can be obtained. This is a fractal figure called the famous
Sierpi´ nski triangle, and belongs to class III. On the other hand, “Rule 110” belongs
to class IV, and it evolves over time as shown in Fig. 4.9 (right). We can see that
various triangles of various sizes are generated, and in fact, it has been proved that
this world is Turing-complete [55]. In other words, in this one-dimensional world,
computers can be made. The more detailed explanation by the author of [55] is
available in [56]. Christopher Langton, who is famous for cellular automata called
Langton’s ants, further argues that class IV time evolution corresponds to Turingcompleteness due to its similarity to phase transition phenomena in condensed
matter systems [57]. By the way, in the world we live in there are computers and
they can perform calculation. Does that have anything to do with the physical laws
of the universe? Research may advance, and we may come to answer such a question
in the future.
75
Fig. 4.9 Left: Rule 90, Right: Rule 110
For example, in the world of his “Rule 90,” if only one point is set to •, an evolution
diagram like Fig. 4.9 (left) can be obtained. This is a fractal figure called the famous
Sierpi´ nski triangle, and belongs to class III. On the other hand, “Rule 110” belongs
to class IV, and it evolves over time as shown in Fig. 4.9 (right). We can see that
various triangles of various sizes are generated, and in fact, it has been proved that
this world is Turing-complete [55]. In other words, in this one-dimensional world,
computers can be made. The more detailed explanation by the author of [55] is
available in [56]. Christopher Langton, who is famous for cellular automata called
Langton’s ants, further argues that class IV time evolution corresponds to Turingcompleteness due to its similarity to phase transition phenomena in condensed
matter systems [57]. By the way, in the world we live in there are computers and
they can perform calculation. Does that have anything to do with the physical laws
of the universe? Research may advance, and we may come to answer such a question
in the future.