Simplicity via Provability for Universal Prefix-free Turing Machines

Cristian S. Calude

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.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 16–21.
Published: 25th June 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.1.2 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org