Simplicity via provability for universal prefix-free Turing machines

zbMATH Open1455.03050MaRDI QIDQ5145146FDOQ5145146

Authors: Cristian S. Calude 

Publication date: 20 January 2021

Full work available at URL: http://eptcs.web.cse.unsw.edu.au/paper.cgi?CSP08.2

Recommendations

• Simplicity via provability for universal prefix-free Turing machines
• Universality probability of a prefix-free machine
• On machines, universal by extensions
• The Complexity of Small Universal Turing Machines
• Universal Turing machines with complexity constraint

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cited In (4)

• Deciding Universality of ptNFAs is PSpace-Complete
• In case of interval (or more general) uncertainty, no algorithm can choose the simplest representative
• Universal Turing machines with complexity constraint
• Simplicity via provability for universal prefix-free Turing machines

This page was built for publication: Simplicity via provability for universal prefix-free Turing machines

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