Simplicity via provability for universal prefix-free Turing machines

MaRDI QIDQ5145146zbMATH OpenFDO

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

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)

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

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)