11552

The First 1936 Elegant Binary Turing Machines

A simple binary Turing machine (SBTM) is said to be elegant if it halts printing a sequence not printed by a machine of lower number. Because of the undecidability of the halting problem, the list of elegant machines is not computable. However, the beginning of that list is computable. We have predetermined (in C++) the first 1936 elegant machines (all 8 two-state, all 31 three-state, all 283 four-state, and only the first 1614 five-state machines). This Demonstration illustrates their evolution with a self-explanatory picture and a sound file.

DETAILS

The SBTM here have states () and two characters (0 and 1) and they mainly respect the NKS design: a left semi-infinite initially blank tape (full of zeros) and no explicit halting state. The head is initially in state 0 (other states are ), located at the rightmost allowed position. The machine halts when the head tries to enter the forbidden right part of the tape (thus crossing the red line). The sequence printed is read from left to right starting with the greatest position on the left ever attained by the head. Machines are numbered as in NKS with a slight difference. In the instructions table, Table[Doubles->Triples], the doubles are ordered in descending order of both states and characters. The reason is a simplification in theorems like this: "All odd machines halt in one step".
The sound files were constructed as follows: a machine evolution is completely described by the ordered sequence of the activated triples. Coding each triple by an integer in base , one gets an evolution sequence translatable as a set of notes in a chromatic scale centered on middle C. The machine evolution then sounds like a chromatic (atonal) melody. Similar sound files exist in the cases of periodic or nested machines (not considered here).
The Snapshots show machines printing sequences of increasing logical depth.
The natural serial number of a sequence follows the enumeration . SBTM rearrange that list in order of increasing complexity. The process can be viewed as a natural compression method.
The algorithmic complexity of a sequence is equal to the number of significant binary digits of its elegant machine number.
The logical depth of a sequence is equal to the integer , where is the number of steps.
A single instruction, ChangeNumbering[n], permutes our numbering with that used in NKS. It works in both directions.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.