WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

Turing Machine Enumeration

​
fraction of maximum rule number
possible head states
2
3
4
possible tape colors
2
3
4
allow resizing
​
​
rule 596440
{{1,2}{1,1,-1},{1,1}{1,2,-1},{1,0}{2,1,1},{2,2}{1,0,1},{2,1}{2,2,1},{2,0}{1,2,-1}}
​
A Turing machine with
s
possible head states and
k
possible tape colors faces
sk
possible situations. Assuming the head can move in
r
different locations, where
r
is most often 2, a Turing machine can produce
skr
outputs. There are thus
sk
(skr)
possible Turing machines of this sort.
This Demonstration shows the enumeration scheme used by Mathematica for describing one-dimensional Turing machines. The top portion of each of the
sk
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.
Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.