Turing Machine Enumeration
Turing Machine Enumeration
A Turing machine with possible head states and possible tape colors faces possible situations. Assuming the head can move in different locations, where is most often 2, a Turing machine can produce outputs. There are thus possible Turing machines of this sort.
s
k
sk
r
r
skr
sk
(skr)
This Demonstration shows the enumeration scheme used by Mathematica for describing one-dimensional Turing machines. The top portion of each of the cells in the grid shows the input state of the Turing machine while the bottom portion shows its output. The integer code of the Turing machine being displayed and its associated transition rules are also shown.
sk