Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Exploring One-Sided Turing Machines
A one-sided Turing machine reads a non-negative integer off a tape that is infinite in one direction, runs until it halts, and leaves an integer behind as its output. Because every such machine is finite, the whole space of machines with a given number of states and colors can be enumerated and indexed by a single number — the convention used throughout A New Kind of Science. This paclet takes that index, written , as its basic description of a machine and builds the rest of its tools on top of it.
{number,s,k}
Specifying and running a machine
A machine is : its enumeration number, its number of states s, and its number of colors k. runs one for at most a given number of steps and returns the integer value left on the tape.
{number,s,k}
Run the s=3, k=2 rule 600720 on input 1 for at most 32 steps:
In[1]:=
 | OneSidedTuringMachineFunction |
Out[1]=
7
Steps, width, and everything at once
A fourth argument selects a property instead of the value. is how many steps the machine ran before halting:
"Steps"
In[2]:=
| OneSidedTuringMachineFunction |
Out[2]=
5
"Width"
In[3]:=
| OneSidedTuringMachineFunction |
Out[3]=
3
All
{steps,value,width}
In[4]:=
| OneSidedTuringMachineFunction |
Out[4]=
{5,7,3}
A machine that has not halted by reports / for the parts that could not be resolved, so these properties double as a halting test.
maxSteps
Infinity
Undefined
Visualizing the evolution
draws the space-time history — one row per step, with tape cells colored by their symbol value and the head marked in black (its orientation showing the machine's state):
In[5]:=
| OneSidedTuringMachinePlot |
Out[5]=
 |
7 |
Scanning a family of machines at once
Replacing the rule number with evaluates an entire family. Here every s=1, k=2 machine is run on inputs 1 through 8, giving a rule-by-input matrix of outputs ( where a machine did not halt):
All
Undefined
In[6]:=
| OneSidedTuringMachineFunction |
Out[6]=
{{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{0,2,0,4,4,6,0,8},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{3,3,7,5,7,7,15,9},{0,Undefined,2,Undefined,4,Undefined,6,Undefined},{0,2,2,4,4,6,6,8},{0,0,2,0,4,4,6,0},{0,3,2,5,4,7,6,9},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{Undefined,2,Undefined,4,Undefined,6,Undefined,8},{Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined,Undefined},{Undefined,3,Undefined,5,Undefined,7,Undefined,9},{1,Undefined,3,Undefined,5,Undefined,7,Undefined},{1,2,3,4,5,6,7,8},{1,3,3,7,5,7,7,15},{1,3,3,5,5,7,7,9}}
In[7]:=
| TuringMachineRuleCount |
Out[7]=
4096
Finding rules with a given behavior
The inverse question — which machines reproduce a given behavior — is . Given a list of triples it returns every rule of the requested family that matches. Rule 1500's own family contains it, of course, alongside other rules with the same first two outputs:
{input,steps,value}
{s,k}
{2,2}
In[8]:=
MemberQ
[{{1,3,3},{2,1,3}},{2,2}],1500
 | OneSidedTuringMachineFind |
Out[8]=
True
Nondeterministic machines
When a pair is allowed several transitions, the machine becomes multiway: it branches into many possible histories. shows the transition table, where the ambiguous cell carries more than one triple:
{state,color}
In[9]:=
| MultiwayTuringMachineRules |
Out[9]=
{{1,0}{{1,0,-1}},{1,1}{{1,0,-1}},{2,0}{{2,0,-1},{2,0,1}},{2,1}{{1,0,1}}}
From there collects every tape value reachable from a halted branch, counts the branches still waiting to be explored, and tests whether the machine falls into a cycle. Together with the rule-space tabulators (, , , and their combined variants) these cover the everyday loop of enumerating machines, running them, and measuring how they behave.
 |
|
""