On the computational power of totalistic cellular automata (Q3763596)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4020486
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the computational power of totalistic cellular automata |
scientific article; zbMATH DE number 4020486 |
Statements
On the computational power of totalistic cellular automata (English)
0 references
1987
0 references
Totalistic cellular automata
0 references
Turing machine
0 references
computation-universal
0 references
0.9118749
0 references
0.9024737
0 references
0.89362437
0 references
0.8910578
0 references
0.8889921
0 references
0.8855935
0 references
0.87933505
0 references
0.87879014
0 references
0.87585896
0 references
Totalistic cellular automata, introduced by S. Wolfram, are cellular automata in which the state transition function depends only on the sum of the states in a cell's neighborhood. Each state is considered as a nonnegative integer and the sum includes the cell's own state. It is shown that one-dimensional totalistic cellular automata can simulate an arbitrary Turing machine in linear time, even when the neighborhood is restricted to one cell on each side. This result settles Wolfram's conjecture that totalistic cellular automata are computation-universal.
0 references