Simplicity via provability for universal prefix-free Turing machines

DOI10.1016/J.TCS.2010.08.002zbMATH Open1207.68136DBLPjournals/tcs/Calude11arXiv0906.3235OpenAlexW2963427251WikidataQ57001536 ScholiaQ57001536MaRDI QIDQ616504FDOQ616504

Authors: Cristian S. Calude 

Publication date: 10 January 2011

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

Abstract: Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.

Full work available at URL: https://arxiv.org/abs/0906.3235

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

zbMATH Keywords

simplicityprovabilityuniversal Turing machine

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• Universality in elementary cellular automata
• Computability and randomness
• Title not available (Why is that?)
• A Theory of Program Size Formally Identical to Information Theory
• Representation of left-computable \(\varepsilon \)-random reals
• Formal proof -- theory and practice
• Title not available (Why is that?)
• Randomness and recursive enumerability
• Title not available (Why is that?)
• Universal Recursively Enumerable Sets of Strings
• On universal computably enumerable prefix codes
• Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.
• Every computably enumerable random real is provably computably enumerable random
• Title not available (Why is that?)
• Small Semi-weakly Universal Turing Machines
• Title not available (Why is that?)
• Evaluating the complexity of mathematical problems. I
• Turing machines with two letters and two states
• The Complexity of Small Universal Turing Machines
• Four Small Universal Turing Machines

Cited In (2)

• Deciding Universality of ptNFAs is PSpace-Complete
• 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 Q616504)