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