Universality of Tag Systems with P = 2

ABSTRACT

By a simple direct construction it is shown that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post canonical system with some very strong restrictions. This system is monogenic: each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to the “Tag” variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape nonwriting Turing machines. The proof here avoids these otherwise interesting machines and strengthens the main result; obtaining the theorem with a best possible deletion number P = 2. Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems.

REFERENCES

• 1: MINsKY, M. lecursive unsolvability of Post's probleln of Tag and other topics in theory of Turig moehirms. Ann. Math. 7g, 3 (Nov. 1961), 437-455.
• 2: For further results along these lines, see: WANG, HAO. Tag systems and Lag systems. To apper.
• 3: MINgKY, M, Size and sgrtwture of universal Turing machines using Tag systems: a 4-symbol 7-share machine. In Proc. Symposium a Recursive FuncZion Theory, Am. Math. See., Providence, R, I., 1962.
• 4: J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]
• 5: Hao Wang, A Variant to Turing's Theory of Computing Machines, Journal of the ACM (JACM), v.4 n.1, p.63-92, Jan. 1957 [doi>10.1145/320856.320867]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Design, Theory