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.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


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.
    • 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 »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2017 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+