Function Repository Resource:

MultiwayGeneralizedShiftGraph

Multiway state graph of a non-deterministic generalized shift

Contributed by: Pavel Hajek

ResourceFunction["MultiwayGeneralizedShiftGraph"][{n,shift,rewrite}, init]

generates a multiway state graph of a generalized shift, defined by non-deterministic shift and rewrite rules on a window of length n over a cyclic tape, starting from the initial condition init.

Details and Options

GeneralizedShift is a stateless machine that operates on a tape; at each step, it rewrites the content of a fixed-length window and shifts it to a new position.

The shift and rewrite operations are specified by lists of rules:

shift

{{p₁,…,p_n}⧴int,…}

rewrite

{{p₁,…,p_n}⧴{r₁,…,r_n},…}

Patterns such as x_, x__, and x___ can be used in place of the symbols p_i, and the bound variable x can be used in place of r_i.

The initial condition init is specified as follows:

{a₁,…,a_k}

cyclic tape of values a_i with the window initially at position 1

{x,{a₁,…,a_k}}

cyclic tape with the window intially at position x

Non-determinism arises from multiple rule matches per window, enumerated by ReplaceList.

Vertices of the multiway state graph represent all distinct states produced by the generalized shift; directed edges denote single computational steps, and branching captures non-determinism.

Besides Graph options, the following are supported:

HaltingStateQ

None

defines halting state

MaxSteps

Infinity

maximum steps pre branch

PruningProbability

controls random pruning of branches

Examples

Basic Examples (2)

Create a multiway state graph of a "universal" non-deterministic generalized shift that computes all binary sequences of length 3:

In[1]:=

$ResourceFunction[ "MultiwayGeneralizedShiftGraph"][{1, {{_} -> 1, {_} -> -1}, {{_} -> {1}, {_} -> {0}}}, {0, 0, 0}]$

Out[1]=

Show a multiway state graph after 3 steps with improved state visualization:

In[2]:=

$ResourceFunction[ "MultiwayGeneralizedShiftGraph"][{2, {{__} -> 1}, {{x_, y_} :> {y, x}, {0, 0} -> {1, 0}}}, {0, 0, 0, 0, 0}, "MaxSteps" -> 3, GraphStyle -> "Basic", VertexLabels -> None, GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Top}, VertexShapeFunction -> ( Inset[ RulePlot[TuringMachine[{1, 1, 2}], {{1, #2[[1, 1]]}, #2[[2]]}, 0, Frame -> False, Mesh -> All], #1, Center, 0.8] &)]$

Out[2]=

Scope (3)

Create a multiway state graph:

In[3]:=

$gr = ResourceFunction[ "MultiwayGeneralizedShiftGraph"][{2, {{_ 1} -> 1, {0, _} -> -1}, {{x_, _} :> {x, 1}, {x_, _} :> {x, 0}, {1, 0} -> {1, 1}}}, {0, 0, 0, 0}]$

Out[3]=

Identify all cyclic computations:

In[4]:=

Out[4]=

Determine the worst-case runtime to reach each state:

In[5]:=

Out[5]=

Options (3)

HaltingStateQ (1)

Terminate the computation at halting states:

In[6]:=

$haltingStateQ[{{pos_, relOrigin_}, tape_}] := Last @ tape === 1; ResourceFunction[ "MultiwayGeneralizedShiftGraph"][{1, {{_} -> 1, {_} -> -1}, {{_} -> {1}, {_} -> {0}}}, {0, 0, 0}, "HaltingStateQ" -> haltingStateQ]$