Universality of Tag Systems with P = 2

DOI10.1145/321203.321206MaRDI QIDQ5528151zbMATH OpenOpenAlexFDO

Authors John Cocke, Marvin L. Minsky

Publication date 1964

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321203.321206

zbMATH Keywords

numerical analysis

Cited in

(20)

• Parsimonious computational completeness
• Small universal TVDH and test tube systems
• Universality of graph-controlled leftist insertion-deletion systems with two states
• Small universal devices
• Undecidability in diagonalizable algebras
• Undecidability and nonperiodicity for tilings of the plane
• Non-preserving accepting splicing systems
• Small fast universal Turing machines
• Maurice Margenstern's contributions to the field of small universal Turing machines
• On the complex behavior of simple tag systems -- an experimental approach
• The decision problem for formulas in prenex conjunctive normal form with binary disjunctions
• The Complexity of Small Universal Turing Machines: A Survey
• Undecidability of consequence relation in full non-associative Lambek calculus
• Freezing 1-Tag Systems with States
• Decision problems for tag systems
• ON SMALL UNIVERSAL SPLICING SYSTEMS
• The complexity of small universal Turing machines: A survey
• Context free normal systems and ETOL systems
• The Solvability of the Derivability Problem for One-Normal Systems
• Mechanical mechanism for self-replication

This page was built for publication: Universality of Tag Systems with P = 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5528151)