Self-reproduction in two- and three-dimensional reversible cellular automata

Morita Kenichi

Imai Katsunobu

Self-reproduction in cellular automaton (CA) was first studied by von Neumann [Neumann, 1966]. Later, Langton proposed a CA in which simple objects called Langton's loop can self-reproduce [Langton, 1984]. Here, we show that Langton's type self-reproduction is possible even in reversible CAs (RCAs). First, a two-dimesional (2-D) RCA SR_2D is given. There, varieties of objects called Worms and Loops of almost any shape can self-reproduce using the shape-encoding method. It is then extended to a 3-D RCA SR_3D. In the 3-D case, there are much more varieties of self-reproducing objects, though the basic method is essentially the same. Examples of movies showing self- reproducing processes in SR_2D and SR_3D are given in this slide.

数学 [ 410 ]

英語

Copyright (c) 2011 Authors

[作成日] 2011-04-25