Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 TuringMachineImport

Source Notebook

Import standard Turing machine formats

Contributed by: Nik Murzin

ResourceFunction["TuringMachineImport"][tm]

return explicit Turing machine rules.

ResourceFunction["TuringMachineImport"][tm,form]

return a Turing machine in a specified form.

Details

Following forms are supported:
"Rules"list of explicit rules (default)
"ExtendedRules"list of rules with extra halting state
"Number"a Turing machine number corresponding to the extended rule list
"Table"raw input table of rules
"TableForm"formatted raw input table of rules

Examples

Basic Examples (5) 

Import a standard Turing machine format specified as a string:

In[1]:=
ResourceFunction["TuringMachineImport"]["1RB1LB_1LA0LC_1RH1LD_1RD0RA"]
Out[1]=

Return extended list of rules for the Turing machine:

In[2]:=
ResourceFunction[ "TuringMachineImport"]["1RB1LB_1LA0LC_1RH1LD_1RD0RA", "ExtendedRules"]
Out[2]=

Return a Turing machine number:

In[3]:=
ResourceFunction[ "TuringMachineImport"]["1RB1LB_1LA0LC_1RH1LD_1RD0RA", "Number"]
Out[3]=

Return the raw table of string:

In[4]:=
ResourceFunction[ "TuringMachineImport"]["1RB1LB_1LA0LC_1RH1LD_1RD0RA", "Table"]
Out[4]=

Return a formatted raw table of states and symbols:

In[5]:=
ResourceFunction[ "TuringMachineImport"]["1RB1LB_1LA0LC_1RH1LD_1RD0RA", "TableForm"]
Out[5]=

Scope (1) 

The "ExtendedRules" and "Number" forms assume an extra halting state that runs aways to the right without further modification of tape:

In[6]:=
GraphicsRow[{ RulePlot[ TuringMachine[ ResourceFunction["TuringMachineImport"][ "1RB1LB_1LA1RH"]], {1, {{}, 0}}, 10, PlotLabel -> "Rules"], RulePlot[ TuringMachine[{ResourceFunction["TuringMachineImport"][ "1RB1LB_1LA1RH", "Number"], 2 + 1, 2}], {1, {{}, 0}}, 10, PlotLabel -> "Number"], RulePlot[ TuringMachine[ ResourceFunction["TuringMachineImport"]["1RB1LB_1LA1RH", "ExtendedRules"]], {1, {{}, 0}}, 10, PlotLabel -> "ExtendedRules"] }]
Out[6]=

Neat Examples (1) 

Show evolutions of small Busy Beaver Turing machines up-to their record halting time:

In[7]:=
RulePlot[ TuringMachine[ ResourceFunction["TuringMachineImport"][#1]], {1, {{}, 0}}, #2] & @@@ {{"1RB1LB_1LA1RH", 6}, {"1RB1RH_1LB0RC_1LC1LA", 21}, {"1RB1LB_1LA0LC_1RH1LD_1RD0RA", 107}, {"1RB2LB1RH_2LA2RB1LB", 38}}
Out[7]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 29 April 2024

Related Resources

License Information