PostTagSystem 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

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

Title: Automatic
Success rate: 100%
Tests run: 1000
Data not saved. Save now

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}}