The First 1936 Elegant Binary Turing Machines
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.