Function Repository Resource:

MultiwayRegisterMachine

Simulate a nondeterministic register machine evolution as a multiway system

Contributed by: Pratham Mukewar

ResourceFunction["MultiwayRegisterMachine"][prog,depth,init]

generates the evolution of the multiway register machine according to the instructions in prog, for depth steps starting at state init.

ResourceFunction["MultiwayRegisterMachine"]["Complexity",prog]

determines the complexity of the inputted multiway register machine prog.

ResourceFunction["MultiwayRegisterMachine"]["RulePlot",prog,nreg]

displays a multiway register machine according to the instructions in prog through a RulePlot, with nreg registers.

ResourceFunction["MultiwayRegisterMachine"]["CirclePlot",prog,nreg]

displays a multiway register machine according to the instructions in prog through a circle plot, with nreg registers.

ResourceFunction["MultiwayRegisterMachine"]["EvolveGraph",prog,depth,init,show]

generates all reachable states, displaying the states on the graph according to the boolean show.

ResourceFunction["MultiwayRegisterMachine"]["ProbabilityPlot",prog,depth,init,maxtokens]

displays rows of multiple tables with the first table having columns corresponding to the number of instructions in the register machine and the rest each having maxTokens columns.

Details

The inputs shown above besides prog are all optional. Here are the default values:

depth

init

{1, {0, 0}}

nreg

show

False

maxtokens

A basic register machine is a simple, deterministic abstract model of computation where information is stored in numbered registers that hold non-negative integers. Computation proceeds by executing a sequence of instructions, typically incrementing or decrementing a register and branching depending on whether the register is zero.

A multiway register machine (MRM) is a computational model similar to a standard register machine, but instead of executing a single deterministic path of instructions, it branches nondeterministically whenever there are multiple possible outcomes of an instruction. This branching generates a multiway system of states, where all possible computational paths evolve simultaneously. MRMs are especially useful for modeling probabilistic, nondeterministic or multi-branching processes like the Collatz conjecture or quantum-inspired computations. For more information about MRMs, please visit this Wolfram Community Post: https://community.wolfram.com/groups/-/m/t/3499350?p_p_auth=DQ5Cml4K.

prog takes a list of instructions, each having the form {reg,incdec,{next₁,…},{failnext_i,…}}. Here, reg is an integer indicating which register to modify, incdec is 0 or 1 indicating whether to increment (0) or decrement (1) this register, the next_i are integers indicating the next instructions to complete upon success and fail_i are optional integers for decrement instructions. The fail_i indicate which instructions to move to upon failure when the register cannot be decremented because it is empty.

ResourceFunction["MultiwayRegisterMachine"]["RulePlot",prog,nreg] generates a visualization of a series of instructions, which forms a multiway register machine. Each instruction is represented as a color depicting its type, an arrow depecting an increment or decrement. There are directed edges depicted as arrows connecting various instructions. The edges above the instructions are green, used when it was a success, and the edges below the instruction are red, used when it was a failure.

ResourceFunction["MultiwayRegisterMachine"]["CirclePlot",prog,nreg] generates a visualization of a series of instructions arranged in a circle, where instructions are represented as above, which forms a multiway register machine.

ResourceFunction["MultiwayRegisterMachine"]["Complexity",prog] is defined as how often a multiway register machine creates new branches, or paths, on average. A branch is a possible simulation of the machine with a certain length. A machine with a greater number of directed edges relative to the number of instructions has a higher complexity, and vice versa. A simple machine would have a complexity of less than 1.5 and a complex machine is otherwise.

ResourceFunction["MultiwayRegisterMachine"]["EvolveGraph",prog,depth,init,show] is used to display the evolution of a multiway register machine through a graph with directed edges. Each possible branch represents a path that the register machine could have taken based on its options.

ResourceFunction["MultiwayRegisterMachine"]["ProbabilityPlot",prog,depth,init,maxTokens] outputs multiple tables. Each row of the first table has boxes that represent the instructions of the machine. The opacity of the circle in each box indicates the probability that the machine is currently on that instruction at the given depth. Each of the rest of the tables represents a register, where the opacity of each box in row i and column j represents the probability that the register has a value of at least j at depth i. These probabilities are determined by considering all possible states that the register machine could have reached at every depth.

Examples

Basic Examples (17)

Create a basic multiway register machine:

In[1]:=

Out[1]=

Create a single-way register machine:

In[2]:=

Out[2]=

Create a register machine with 3 registers:

In[3]:=

Out[3]=

Create a basic multiway register machine rule plot:

In[4]:=

Out[4]=

Create a single-way register machine rule plot:

In[5]:=

Out[5]=

Create a register machine's rule plot with 3 registers:

In[6]:=

Out[6]=

Create a basic multiway register machine circle plot:

In[7]:=

Out[7]=

Create a single-way register machine circle plot:

In[8]:=

Out[8]=

Create a register machine's circle plot with 3 registers:

In[9]:=

Out[9]=

Determine the complexity of a basic multiway register machine:

In[10]:=

Out[10]=

Determine the complexity of a single-way register machine:

In[11]:=

Out[11]=

Determine the complexity of a more advanced multiway register machine:

In[12]:=

Out[12]=

Evolution of a basic multiway register machine until depth 5:

In[13]:=

Out[13]=

Evolution of a single-way register machine:

In[14]:=

Out[14]=

Evolution of a complex multiway register machine with maximum depth 10:

In[15]:=

ResourceFunction[
"MultiwayRegisterMachine"]["EvolveGraph", {{1, 0, {2, 3}}, {2, 0, {4, 5}}, {3, 0, {5}}, {1, 1, {1}, {5}}, {2, 1, {1}, {3}}}, 10, {1, {0, 0, 0}}]

Out[15]=

Display the probabilistic behavior of a basic multiway register machine:

In[16]:=

Out[16]=

Display the general behavior of a single-way register machine:

In[17]:=

Out[17]=

Display the general behavior of a complex multiway register machine, with three registers until depth 20:

In[18]:=

ResourceFunction[
"MultiwayRegisterMachine"]["ProbabilityPlot", {{1, 0, {2, 3}}, {2, 0, {4, 5}}, {3, 0, {5}}, {1, 1, {1}, {5}}, {2, 1, {1}, {3}}}, 20, {1, {0, 0, 0}}]

Out[18]=

Scope (6)

Create a multiway register machine that has all instructions connected:

In[19]:=

Out[19]=

Create a multiway register machine's circle plot that has all instructions connected:

In[20]:=

Out[20]=

Determine complexity of a multiway register machine that has all instructions connected:

In[21]:=

Out[21]=

Evolution of a multiway register machine, with states shown:

In[22]:=

ResourceFunction[
"MultiwayRegisterMachine"]["EvolveGraph", {{1, 0, {2, 3}}, {2, 0, {4, 5}}, {3, 0, {5}}, {1, 1, {1}, {5}}, {2, 1, {1}, {3}}}, 5, {1, {0, 0, 0}}, True]

Out[22]=

Evolution of a multiway register machine, with initial state {2, {0, 0, 0}}:

In[23]:=

ResourceFunction[
"MultiwayRegisterMachine"]["EvolveGraph", {{1, 0, {2, 3}}, {2, 0, {4, 5}}, {3, 0, {5}}, {1, 1, {1}, {5}}, {2, 1, {1}, {3}}}, 10, {2, {0, 0, 0}}]

Out[23]=

Display the general behavior of a multiway register machine, with maximum tokens 3:

In[24]:=

Out[24]=

Applications (2)

Create a function that can multiply a number by a scalar k, using the provided registers:

In[25]:=

$scalar[k_ : 3, shift_ : 0, next___ : -1, regs_List : {1, 2}] := Join[{{regs[[1]], 1, {2 + shift}, If[next != -1, {next}, {}]}}, Table[{regs[[2]], 0, {i + 2 + shift}}, {i, k - 1}], {{regs[[2]], 0, {1 + shift}}}]$