Universal Computation in Simple One-Dimensional Cellular Automata

• The existence of computation-universal one-dimensional cellular automata with seven states per cell for a transition function depending on the cell itself and its nearest neighbors (r= 1), and four states per cell for r= 2 (when next-nearest neighbors also are included), is shown. It is also demonstrated that a Turing machine with m tape symbols and n internal states can be simulated by a cellular automaton of range r= 1 with m+ n+ 2 states per cell.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Publikations- och innehållstyp

art (ämneskategori)

ref (ämneskategori)