Tag systems and Collatz-like functions

DOI10.1016/J.TCS.2007.10.020MaRDI QIDQ2474075zbMATH OpenOpenAlexFDO

Authors 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

\(3n+1\)-problemCollatz-like functionslimits of solvability and unsolvabilitytag systemsuniversality

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Turing machines and related notions (03D10)

Recommendations

• Study of Limits of Solvability in Tag Systems
• On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results
• Generalized tag systems
• scientific article; zbMATH DE number 5885061
• The Undecidability of the Generalized Collatz Problem

Cites work

• Busy beaver competition and Collatz-like problems
• Closing the Circle: An Analysis of Emil Post's Early Work
• Formal Reductions of the General Combinatorial Decision Problem
• Four Small Universal Turing Machines
• Frontier between decidability and undecidability: A survey
• scientific article; zbMATH DE number 3813599 (Why is no real title available?)
• scientific article; zbMATH DE number 3526785 (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 1839446 (Why is no real title available?)
• scientific article; zbMATH DE number 2123258 (Why is no real title available?)
• scientific article; zbMATH DE number 3211078 (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?)
• P-completeness of Cellular Automaton Rule 110
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Small fast universal Turing machines
• Small Turing machines and generalized busy beaver competition
• Small universal one-state linear operator algorithm
• Small universal Turing machines
• Solvability of the Halting and Reachability Problem for Binary 2-tag Systems
• Study of Limits of Solvability in Tag Systems
• Tag systems and lag systems
• The 3x + 1 Problem and Its Generalizations
• Universality in elementary cellular automata
• Why Gödel didn't have church's thesis

Cited in

(9)

• Generalized tag systems
• An automated approach to the Collatz conjecture
• Problems in number theory from busy beaver competition
• Study of Limits of Solvability in Tag Systems
• On the boundaries of solvability and unsolvability in tag systems. Theoretical and experimental results
• scientific article; zbMATH DE number 7654728 (Why is no real title available?)
• An automated approach to the Collatz conjecture
• On the complex behavior of simple tag systems -- an experimental approach
• The convergence classes of Collatz function

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

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