On the complex behavior of simple tag systems -- an experimental approach

DOI10.1016/j.tcs.2010.08.026zbMath1207.68139OpenAlexW2090766691MaRDI QIDQ616497

Liesbeth De Mol

Publication date: 10 January 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.026

zbMATH Keywords

universalitydecidabilitycomputer experimentstag systems

Mathematics Subject Classification ID

Related Items (1)

Why Post Did [Not Have Turing’s Thesis]

Uses Software

• Diehard

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Small Turing machines and generalized busy beaver competition
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Small universal Turing machines
• Cellular automata and intermediate degrees.
• Frontier between decidability and undecidability: A survey
• Tag systems and lag systems
• Tag systems and Collatz-like functions
• Small fast universal Turing machines
• Small Weakly Universal Turing Machines
• Closing the Circle: An Analysis of Emil Post's Early Work
• Study of Limits of Solvability in Tag Systems
• Small Semi-weakly Universal Turing Machines
• P-completeness of Cellular Automaton Rule 110
• Small Semi-Weakly Universal Turing Machines
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• Why Gödel didn't have church's thesis
• Emil Post and His Anticipation of Gödel and Turing
• Solvability of the Halting and Reachability Problem for Binary 2-tag Systems
• Computer Studies of Turing Machine Problems
• Universality of Tag Systems with P = 2
• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• The Categorization of Tag Systems in Terms of Decidability
• An Unsolvable Problem of Elementary Number Theory
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Formal Reductions of the General Combinatorial Decision Problem
• Four Small Universal Turing Machines
• Four Small Universal Turing Machines

This page was built for publication: On the complex behavior of simple tag systems -- an experimental approach