Simplicity via Provability for Universal Prefix-free Turing Machines

Details Simplicity via Provability for Universal Prefix-free Turing Machines Simplicity via Provability for Universal Prefix-free Turing Machines

2009-06-17

arxiv.org/abs/0906.3235v1

EPTCS 1, 2009, pp. 16-21

Computer Science

Information Theory

Scientific paper

10.4204/EPTCS.1.2

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.

Affiliated with

Also associated with

No associations

Rating

Simplicity via Provability for Universal Prefix-free Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simplicity via Provability for Universal Prefix-free Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplicity via Provability for Universal Prefix-free Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-223623