WOLFRAM|DEMONSTRATIONS PROJECT

The First 1936 Elegant Binary Turing Machines

​
running elegant machine number
15
natural serial number of the printed sequence
14
algorithmic complexity
3
logical depth
4
actual number of states
3
actual machine number
31672
NKS machine number
2830897
110
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.