## 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[]=