Small Turing machines and generalized busy beaver competition

DOI10.1016/j.tcs.2004.05.008zbMath1071.68025MaRDI QIDQ703533

Pascal Michel

Publication date: 11 January 2005

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

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

zbMATH Keywords

Turing machines; Collatz problem; Decidability; \(3x+1\) problem; Busy beaver competition

Mathematics Subject Classification ID

11B85: Automata sequences

03D10: Turing machines and related notions

Related Items

Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines, On the complex behavior of simple tag systems -- an experimental approach, The convergence classes of Collatz function, The complexity of small universal Turing machines: A survey, Tag systems and Collatz-like functions, The Complexity of Small Universal Turing Machines: A Survey, HOMOLOGY OF GROUPS AND THIRD BUSY BEAVER FUNCTION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Busy beaver competition and Collatz-like problems
• Castor quadruplorum
• Small universal Turing machines
• Small deterministic Turing machines
• The dynamical system generated by the \(3n+1\) function
• Frontier between decidability and undecidability: A survey
• Solvability of the halting problem for certain classes of Turing machines
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• The 3x + 1 Problem and Its Generalizations
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• On Non-Computable Functions
• Small universal one-state linear operator algorithm
• Computer Studies of Turing Machine Problems