CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Universal Computation in Simple One-Dimensional Cellular Automata

Kristian Lindgren (Institutionen för fysisk resursteori) ; Mats G. Nordahl (Institutionen för teoretisk fysik)
Complex Systems (0891-2513). Vol. 4 (1990), 3, p. 299-318.
[Artikel, refereegranskad vetenskaplig]

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.

Denna post skapades 2013-05-23.
CPL Pubid: 177274


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för fysisk resursteori (1980-2004)
Institutionen för teoretisk fysik (1900-2003)


Tillämpad matematik

Chalmers infrastruktur