Access Restriction

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

   Open content in new tab
Source: ACM Digital Library