PostTagSystem State Format
PostTagSystem State Format
Active State Format
Active State Format
Let’s start with an NKS format for the Tag System state:
Out[]=
{1,0,1,0,0,1,1,1,0,0,0}
Note that because the rules read 3 elements at a time, but only depend on the first element, not all of the elements above are active. In the following, active elements are colored red:
Out[]=
{1,0,1,0,0,1,1,1,0,0,0}
Hence, we get the tape of the compressed state:
Out[]=
{1,0,1,0}
That describes completely the elements that will be read (rather than skipped) by the system. However, it does not give us enough information about which just created elements will be active. Consider three different ways uncompressed {1, 1, 0, 1} can be appended to the compressed state above:
Out[]=
{1,_,_,0,_,_,1,_,_,0,1,1,0,1} |
{1,_,_,0,_,_,1,_,_,0,_,1,1,0,1} |
{1,_,_,0,_,_,1,_,_,0,_,_,1,1,0,1} |
In other words, in order to apply the tag system rule, we need to know Mod[Length[nksState], 3], which is called phase.
Out[]=
{1,0,1,0,0,1,1,1,0, phase = 0 |
{1,0,1,0,0,1,1,1,0, 0 phase = 1 |
{1,0,1,0,0,1,1,1,0, 0,0 phase = 2 |
Hence, we now have the conversion function:
In[]:=
nksToActiveState[nksState_] := {Mod[Length[nksState], 3], nksState[[1 ;; -1 ;; 3]]}
In[]:=
nksToActiveState[{1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0}]
Out[]=
{2,{1,0,1,0}}
And also the reverse:
In[]:=
riffle[list : {_}, riffledElement_] := list;riffle[list_, riffledElement_] := Riffle[list, riffledElement];activeToNKSState[{phase_, activeTape_}] := Join[Catenate[riffle[List /@ activeTape, {{_, _}}]], ConstantArray[_, Mod[phase - 1, 3]]];activeToNKSState[{0, {}}] := {};
In[]:=
activeToNKSState[{2, {1, 0, 1, 0}}]
Out[]=
{1,_,_,0,_,_,1,_,_,0,_}
Stephen’s Mod Form
Stephen’s Mod Form
In[]:=
activeStateToModForm[{0, activeTape_}] := {activeTape, {}}
In[]:=
activeStateToModForm[{phase : 1 | 2, activeTape_}] := {Most[activeTape], Join[{Last[activeTape]}, ConstantArray[_, phase - 1]]}
In[]:=
modFormToActiveState[{si_, {}}] := {0, si}
In[]:=
modFormToActiveState[{si_, res : {__}}] := {Length[res], Append[si, First[res]]}
Now, let’s compare:
In[]:=
ToModForm[list_List]:={Take[list,1;;-3;;3],Take[list,-Mod[Length[list],3]]};ToModForm[s:{_}]:={{},s};ToModForm[{}]:={{},{}};TSModStep[{si:{__},res_}]:={Join[Rest[si],First[#]],Last[#]}&[ToModForm[Join[res,{{0,0},{1,1,0,1}}[[1+First[si]]]]]];TSModStep[{{},res_}]:={{},res};TSModEvolve[{si_,res_},t_]:=Nest[TSModStep,{si,res},t];
In[]:=
TSModEvolve[{{0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 1}}, 64]
Out[]=
{{0,0,1,0,1,0,0},{}}
In[]:=
activeStateToModForm[ PostTagSystemFinalState[modFormToActiveState[{{0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 1}}], 64]]
Out[]=
{{0,0,1,0,1,0,0},{}}
And the reverse:
In[]:=
PostTagSystemFinalState[{2, {0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1}}, 64]
Out[]=
{0,{0,0,1,0,1,0,0}}
In[]:=
modFormToActiveState[TSModEvolve[activeStateToModForm[{2, {0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1}}], 64]]
Out[]=
{0,{0,0,1,0,1,0,0}}
Tests
In[]:=
TestReport @ Table[ With[{activeState = {RandomInteger[2], RandomInteger[1, 100]}}, VerificationTest[PostTagSystemFinalState[activeState, 400], modFormToActiveState[TSModEvolve[activeStateToModForm[activeState], 400]]] ], 1000]
Out[]=
TestReportObject
In[]:=
activeStateToModForm /@ { {0, {1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}}, {1, {1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}}, {2, {1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}}} // Column
Out[]=
{{1,1,1,1,1,0,1,1,1,0,1},{}} |
{{1,1,1,1,1,0,1,1,1,0},{1}} |
{{1,1,1,1,1,0,1,1,1,0},{1,_}} |
In[]:=
modFormToActiveState /@ { {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {0}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {1}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {0, 0}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {0, 1}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {1, 0}}, {{1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {1, 1}}} // Column
Out[]=
{0,{1,1,1,1,1,0,1,1,1,0,1}} |
{1,{1,1,1,1,1,0,1,1,1,0,1,0}} |
{1,{1,1,1,1,1,0,1,1,1,0,1,1}} |
{2,{1,1,1,1,1,0,1,1,1,0,1,0}} |
{2,{1,1,1,1,1,0,1,1,1,0,1,0}} |
{2,{1,1,1,1,1,0,1,1,1,0,1,1}} |
{2,{1,1,1,1,1,0,1,1,1,0,1,1}} |