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:
“What is most original in a man’s nature is often that which is most desperate. Thus new systems are forced on the world by men who simply cannot bear the pain of living with what is. Creators care nothing for their systems except that they be unique. If Hitler had been born in Nazi Germany he wouldn’t have been content to enjoy the atmosphere.”
—Leonard Cohen (b. 1934)