Von Neumann's 29-state cellular automaton

From Esolang
Jump to navigation Jump to search

Von Neumann's 29-state cellular automaton is a Cellular automaton published in 1966.

The state of the automaton is a square grid filling the whole plane, in which each cell of the grid can have one of a set of 29 states. Each cell is considered to have four neighbors, the ones that are exactly 1 Manhattan distance from it. The state is updated at each clock cycle (generation), in which the state of each cell is replaced simultaneously. The state of the cell is determined by its state and the state of its four neighbors, through a rather complicated rule.

This cellular automaton was deliberately constructed by von Neumann as a Turing-tarpit. (To define it as Turing-complete, we need to restrict starting patterns as finite, but I don't know what finite means in this case.)

The automaton is described in the following book, which is credited as the inspiration for the whole line of research in Game of Life and other Cellular automaton.

von Neumann, J.; Burks, A. W. (1966) Theory of Self-Reproducing Automata (older pdf). No ISBN. WorldCat OCLC number: 7298386.