### Universality of Tag Systems with $\textit{P}$ = 2Universality of Tag Systems with $\textit{P}$ = 2

Access Restriction
Subscribed

 Author Cocke, John ♦ Minsky, Marvin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1964 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1964-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 11 Issue Number 1 Page Count 6 Starting Page 15 Ending Page 20

#### Open content in new tab

Source: ACM Digital Library