Definition of universality
Definition of universality
By giving initial conditions, one can set it up so that some history reaches a “success” state.
Can other, incorrect histories also reach success states? What about reaching a success state later?
Can other, incorrect histories also reach success states? What about reaching a success state later?
https://www.wolframscience.com/nks/p759--undecidability-and-intractability/ :
{445,461,1512}
In[]:=
RulePlot[TuringMachine[445],{{1,9},IntegerDigits[11,2,10]},7]
Out[]=
Typical version: there are many possible answers; each “success” history is a valid answer....
Typical version: there are many possible answers; each “success” history is a valid answer....
E.g. factoring:
E.g. success could be recognized by halting....
In general, pick the “success” criterion.... More natural to have halting as a success criterion in an NDTM than a DTM.
In general, pick the “success” criterion.... More natural to have halting as a success criterion in an NDTM than a DTM.
Multispace visualization
Multispace visualization
In[]:=
ResourceFunction["MultispacePlot3D"][ResourceFunction["MultiwayTuringMachine"][{1507,2506,3506},{{1,1,0},{0,1,0,1}},4,##]&,"Graph"]
Out[]=
In[]:=
MultispaceTM[rule_,t_]:=ResourceFunction["MultispacePlot3D"][ResourceFunction["MultiwayTuringMachine"][rule,{{1,t+1,0},Table[0,2t+1]},t,##]&,"Graph"]
In[]:=
MultispaceTM[rule_,t_,case_]:=ResourceFunction["MultispacePlot3D"][ResourceFunction["MultiwayTuringMachine"][rule,{{1,t+1,0},Table[0,2t+1]},t,##]&,case]
In[]:=
MultispaceTM[{{{1,0}{1,0,1}},{{1,0}{1,1,-1}},{{1,1}{1,0,-1}}},10]
Out[]=
