In[]:=

NestGraph[nTake[Divisors[n],{2,-2}],81,6,VertexLabelsAutomatic]

Out[]=

Enumerate possible factors; checking takes polynomial time....

NDTM: If any branch gives success on halting, then it is success

Is there is a successful halt?

Is there is a successful halt?

E.g. satisfiability

In[]:=

SatisfiableQ[p&&!(q&&r),{p,q,r}]

Out[]=

True

Anything with more than 1 halting state will not be confluent ...

Let’s say we are trying to build a certain final state.... (or perhaps a certain history)

Trivial way to achieve this: just have all possible histories...

Trivial way to achieve this: just have all possible histories...

#### The case of adding 5

The case of adding 5

In[]:=

Clear[stepfunc]

In[]:=

stepfunc[s[v_,c_]]:={s[v+1,c-1],s[v-1,c-1]}

In[]:=

stepfunc[s[v_,0]]:={}

In[]:=

NestGraph[stepfunc,{s[7,5]},9,VertexLabelsAutomatic]

Out[]=

What would it take to have a NDTM that determines a number is prime?

Halt if it is a power of 2....

In[]:=

NestGraph[If[!NumberQ[#],{},If[#==1,{"Success"},{#/2}]]&,16,8,VertexLabelsAutomatic]

Out[]=

Our goal: take an input and test whether it is valid: e.g. parenthesis language

Trying to reduce to ( )

In[]:=

ResourceFunction["MultiwaySystem"][{"()"""},"(()(())))",5,"StatesGraph"]

Out[]=

In[]:=

ResourceFunction["MultiwaySystem"][{"()"""},"((()(())))",5,"StatesGraph"]

Out[]=

In[]:=

ResourceFunction["MultiwaySystem"][{"()""","()""(|)"},"((()(())))",5,"StatesGraph"]

Out[]=

#### [M Szudzik]

[M Szudzik]

The two different interpretations of universality for multiway systems depend on whether one is thinking of the system as a computation or as an axiom system. Thinking of it as a computation, the initial string specifies a function f and an input x, and the multiway system calculates a string for f(x).

But thinking of the multiway system as an axiom system, one usually starts from a single conventional initial state that cannot be chosen. Instead, starting from that conventional initial state, the multway system calculates strings that represent the equation “f(x)=y” for each possible f and x.

Matthew Szudzik

The two different interpretations of universality for multiway systems depend on whether one is thinking of the system as a computation or as an axiom system. Thinking of it as a computation, the initial string specifies a function f and an input x, and the multiway system calculates a string for f(x).

But thinking of the multiway system as an axiom system, one usually starts from a single conventional initial state that cannot be chosen. Instead, starting from that conventional initial state, the multway system calculates strings that represent the equation “f(x)=y” for each possible f and x.

Matthew Szudzik