Tag systems and Collatz-like functions

DOI10.1016/j.tcs.2007.10.020zbMath1134.68024OpenAlexW2063470502MaRDI QIDQ2474075

Liesbeth De Mol

Publication date: 5 March 2008

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

Full work available at URL: https://biblio.ugent.be/publication/436211

zbMATH Keywords

universalitytag systems\(3n+1\)-problemCollatz-like functionslimits of solvability and unsolvability

Mathematics Subject Classification ID

Related Items (4)

On the complex behavior of simple tag systems -- an experimental approach ⋮ An automated approach to the Collatz conjecture ⋮ The convergence classes of Collatz function ⋮ An automated approach to the Collatz conjecture

Cites Work

• Busy beaver competition and Collatz-like problems
• 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
• Frontier between decidability and undecidability: A survey
• Tag systems and lag systems
• Small fast universal Turing machines
• Closing the Circle: An Analysis of Emil Post's Early Work
• Study of Limits of Solvability in Tag Systems
• P-completeness of Cellular Automaton Rule 110
• Why Gödel didn't have church's thesis
• The 3x + 1 Problem and Its Generalizations
• Solvability of the Halting and Reachability Problem for Binary 2-tag Systems
• Small universal one-state linear operator algorithm
• Formal Reductions of the General Combinatorial Decision Problem
• Four Small Universal Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tag systems and Collatz-like functions