Turing-completeness of m-tag Systems
For each m > 1, the set of m-tag systems is Turing-complete; i.e., for each m > 1, it is the case that for any given Turing machine T, there is an m-tag system that simulates T. In particular, a 2-tag system can be constructed to simulate a Universal Turing machine, as was done by Wang 1963 and by Cocke & Minsky 1964.
Conversely, a Turing machine can be shown to be a Universal Turing Machine by proving that it can simulate a Turing-complete class of m-tag systems. For example, Rogozhin 1996 proved the universality of the class of 2-tag systems with alphabet {a1, ..., an, H} and corresponding productions {ananW1, ..., ananWn-1, anan, H}, where the Wk are nonempty words; he then proved the universality of a very small (4-state, 6-symbol) Turing machine by showing that it can simulate this class of tag systems.
Read more about this topic: Tag System
Famous quotes containing the word systems:
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)