Turing Machine Enumeration: NKS versus Lexicographical
Turing Machine Enumeration: NKS versus Lexicographical
Turing Machines (TMs) are among the simplest computational models that can perform any computational task that can be mechanized. A TM consists of an infinite tape of cells extending both to the left and right, with a head moving over these cells and performing tasks on them. Each cell has a color. The head can be in various states. Depending on the state of the head and the color of the cell under the head, the head performs its task. The task is writing a color on the cell, moving the tape either left or right, and going to a new state (possibly the same as before).
There are various very simple ways to enumerate all possible Turing machines with a given number of states and colors.
Sometimes people get confused by the NKS enumeration, as they would have done the enumeration in a way that is called lexicographical. The only difference between the NKS and lexicographical enumeration is the order in which they enumerate: where the lexicographical enumeration starts with the lowest state and whitest (lowest) color, the NKS enumeration starts with the highest state and the whitest/lowest color.
This Demonstration makes the small difference between NKS coding and lexicographical coding visible.
The so-called changing transitions in this Demonstration are those transitions that will change by increasing the TM code by one, and can be made to light up in pink.