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:
“The skylines lit up at dead of night, the air- conditioning systems cooling empty hotels in the desert and artificial light in the middle of the day all have something both demented and admirable about them. The mindless luxury of a rich civilization, and yet of a civilization perhaps as scared to see the lights go out as was the hunter in his primitive night.”
—Jean Baudrillard (b. 1929)