Universal computer: Difference between revisions
new page |
mNo edit summary |
||
| Line 1: | Line 1: | ||
{{Glossary}} | |||
A '''universal computer''' in a cellular automaton is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine Turing machine] can compute. A cellular automaton in which such a system exists is called '''universal'''. A universal computer may be either infinite or finite, but when combined with a universal constructor, it is assumed to be finite. | A '''universal computer''' in a cellular automaton is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine Turing machine] can compute. A cellular automaton in which such a system exists is called '''universal'''. A universal computer may be either infinite or finite, but when combined with a universal constructor, it is assumed to be finite. | ||
Revision as of 07:37, 26 March 2009
A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute. A cellular automaton in which such a system exists is called universal. A universal computer may be either infinite or finite, but when combined with a universal constructor, it is assumed to be finite.
In 1982, John Conway proved in Winning Ways that the Game of Life has a (finite) universal computer, as well as a universal constructor.
In 2000, Paul Rendell constructed a direct implementation of a Turing Machine [1]. This computer is infinite, as it requires an infinite length of tape for the Turing Machine.
In 2002, using Dean Hickerson's sliding block memory, Paul Chapman constructed an implementation of a Minsky Register Machine (a machine of the same capability as a Turing Machine), which he extended to a Universal Register Machine, a finite universal computer [2].
References
- ↑ Paul Rendell (April 2, 2000). "A Turing Machine in Conway's Game of Life".
- ↑ Paul Chapman (November 11, 2002). "Life Universal Computer".
External Links
Universal computer at the Life Lexicon.