Small Turing machines and generalized busy beaver competition

DOI10.1016/J.TCS.2004.05.008MaRDI QIDQ703533zbMATH OpenOpenAlexFDO

Authors 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 machinesCollatz problem\(3x+1\) problemDecidabilityBusy beaver competition

Mathematics Subject Classification ID

Automata sequences (11B85) Turing machines and related notions (03D10)

Recommendations

• Busy beaver competition and Collatz-like problems
• Small deterministic Turing machines
• scientific article; zbMATH DE number 8896
• Turing machines with two letters and two states
• scientific article; zbMATH DE number 1114344

Cites work

• scientific article; zbMATH DE number 3813599 (Why is no real title available?)
• scientific article; zbMATH DE number 3664359 (Why is no real title available?)
• scientific article; zbMATH DE number 8896 (Why is no real title available?)
• scientific article; zbMATH DE number 3526785 (Why is no real title available?)
• scientific article; zbMATH DE number 1138300 (Why is no real title available?)
• scientific article; zbMATH DE number 1746682 (Why is no real title available?)
• scientific article; zbMATH DE number 2087234 (Why is no real title available?)
• scientific article; zbMATH DE number 3305022 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Busy beaver competition and Collatz-like problems
• Castor quadruplorum
• Computer Studies of Turing Machine Problems
• Frontier between decidability and undecidability: A survey
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• On non-computable functions
• Small deterministic Turing machines
• Small universal Turing machines
• Small universal one-state linear operator algorithm
• Solvability of the halting problem for certain classes of Turing machines
• The 3x + 1 Problem and Its Generalizations
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• The dynamical system generated by the \(3n+1\) function

Cited in

(10)

• Turing machines with two letters and two states
• The complexity of small universal Turing machines: A survey
• Maurice Margenstern's contributions to the field of small universal Turing machines
• Homology of groups and third busy beaver function
• scientific article; zbMATH DE number 522863 (Why is no real title available?)
• Busy beaver competition and Collatz-like problems
• 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

This page was built for publication: Small Turing machines and generalized busy beaver competition

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