Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 TagSystemEvolve

Source Notebook

Generate the final outcome of a tag system evolution

Contributed by: Wolfram Research

ResourceFunction["TagSystemEvolve"][rules,init,t]

returns the final state of the tag system initialized with state init and evolved with rules over t steps.

ResourceFunction["TagSystemEvolve"][rules,init]

attempts to return the final state of the tag system initialized with state init and evolved with rules over the number of steps specified by the option MaxSteps.

Details and Options

In a step of evolution of a tag system, a fixed number of elements is deleted from the beginning of the tape. The rules specify a block of digits that should be added to the end of the tape based on the first element that was deleted.
The argument rules should be given as a list of Rule or RuleDelayed elements, such as in the format {{0,_,s___}⧴{s,0,0},{1,0,s___}⧴{s,1},{1,1,s___}⧴{s,0,1}}. Blank elements are used to represent tape elements that do not matter for choosing the block to be added to the end of the tape.
As a special case, the Post tag system can be specified by setting the argument rules to "Post". This is equivalent to giving rules as {{0,_,_,s___}→{s,0,0},{1,_,_,s___}→ {s,1,1,0,1}}.
The argument init can be given either in compressed form (a list of digits such as {1,0,1,0,0,1,1}), or in uncompressed form (a list where the first element is a digit and the second element is a list of digits, such as {1,{1,0,1}}). The resource function TagSystemConvert can be used to interconvert between these forms.
The argument t should be given as an integer.
ResourceFunction["TagSystemEvolve"] accepts two options:
MaxStepsInfinitythe maximum number of steps to be taken in the tag system evolution
MethodAutomaticthe algorithm used internally to compute the tag system evolution
If no value is specified for the MaxSteps option, ResourceFunction["TagSystemEvolve"][rules,init] will attempt to perform a fixed point evolution, which takes the system to the state at which it halts.
If no value is specified for the Method option, then the tag system evolution will be performed using functional iteration in the Wolfram Language. Alternatively, there is a "BitwiseOptimized" method, which can only be used when rules is given as "Post", that uses a faster algorithm written in C++.

Examples

Basic Examples (2) 

Generate the fourth tape state of a Post tag system evolution from an initial condition:

In[1]:=
ResourceFunction[ "TagSystemEvolve"][{{0, _, _, s___} :> {s, 0, 0}, {1, _, _, s___} :> {s, 1, 1, 0, 1}}, {0, 1, 0, 0, 1, 0, 1, 0, 0}, 4]
Out[1]=

Generate the fourth state from an initial condition, using the string shortcut "Post" to specify the tag system rules:

In[2]:=
ResourceFunction[ "TagSystemEvolve"]["Post", {0, 1, 0, 0, 1, 0, 1, 0, 0}, 4]
Out[2]=

Generate the fourth state in the Post tag system evolution from the same initial condition specified in compressed form:

In[3]:=
ResourceFunction["TagSystemEvolve"]["Post", {0, {0, 0, 1}}, 4]
Out[3]=

Return the fixed point of the Post tag system evolution from an initial condition:

In[4]:=
ResourceFunction[ "TagSystemEvolve"]["Post", {0, 1, 0, 0, 1, 0, 1, 0, 0}]
Out[4]=

Return the fixed point of the Post tag system evolution from a compressed initial condition:

In[5]:=
ResourceFunction["TagSystemEvolve"]["Post", {0, {0, 0, 1}}]
Out[5]=

Scope (2) 

Find the twentieth state of a tag system evolution from a specified initial condition with specified rules:

In[6]:=
ResourceFunction[ "TagSystemEvolve"][{{0, _, s___} :> {s, 1}, {1, _, s___} :> {s, 1, 1, 0}}, {1, 0, 1, 1, 0, 0}, 20]
Out[6]=

Find the result of the same evolution, except in compressed form:

In[7]:=
ResourceFunction[ "TagSystemEvolve"][{{0, _, s___} :> {s, 1}, {1, _, s___} :> {s, 1, 1, 0}}, {0, {1, 1, 0}}, 20]
Out[7]=

Return the twentieth result of a generalized tag system evolution (in which the rules do not use Blank elements):

In[8]:=
ResourceFunction[ "TagSystemEvolve"][{{0, 0, s___} :> {s, 0}, {1, 0, s___} :> {s, 1, 0, 1}, {0, 1, s___} :> {s, 0, 0, 0}, {1, 1, s___} :> {s, 0, 1, 1}}, {1, 0, 0, 1}, 20]
Out[8]=

Options (2) 

MaxSteps (1) 

It may not always be feasible the point at which a tag system halts. Setting the MaxSteps option can prevent computationally expensive fixed point evolutions:

In[9]:=
ResourceFunction[ "TagSystemEvolve"][{{0, _, s___} :> {s, 1}, {1, _, s___} :> {s, 1, 1, 0}}, {0, {1, 1, 0}}, MaxSteps -> #] & /@ {500, 1000, 1500}
Out[9]=

Method (1) 

An example comparing the time efficiency of the "BitwiseOptimized" method for a long evolution:

In[10]:=
First[Timing[ ResourceFunction["TagSystemEvolve"][ "Post", {0, {0, 1, 1, 0, 0, 1, 0, 1, 1}}, MaxSteps -> 256000]]]
Out[10]=
In[11]:=
First[Timing[ ResourceFunction["TagSystemEvolve"][ "Post", {0, {0, 1, 1, 0, 0, 1, 0, 1, 1}}, MaxSteps -> 256000, Method -> "BitwiseOptimized"]]]
Out[11]=

Possible Issues (5) 

Note that if the number of evolution steps surpasses the fixed point evolution of the tag system, the association returned will simply contain the amount of steps needed to evolve to the fixed point and the fixed point:

In[12]:=
ResourceFunction[ "TagSystemEvolve"]["Post", {0, 1, 0, 0, 1, 0, 1, 0, 0}, 20]
Out[12]=
In[13]:=
ResourceFunction["TagSystemEvolve"]["Post", {0, {0, 0, 1}}, 20]
Out[13]=

Compressed state representations do not make sense with generalized tag systems, as they require successive tape elements to be specified in order to be evolved correctly:

In[14]:=
ResourceFunction[ "TagSystemEvolve"][{{0, 0, s___} :> {s, 0}, {1, 0, s___} :> {s, 1, 0, 1}, {0, 1, s___} :> {s, 0, 0, 0}, {1, 1, s___} :> {s, 0, 1, 1}}, {0, {1, 0}}, 20]
Out[14]=

Tag system rules must have the head Rule or RuleDelayed:

In[15]:=
ResourceFunction[ "TagSystemEvolve"][{Rule[{0, _, s___}, {s, 1}], Rule[{1, _, s___}, {s, 1, 1, 0}]}, {0, {1, 1, 0}}, 5]
Out[15]=
In[16]:=
ResourceFunction[ "TagSystemEvolve"][{RuleDelayed[{0, _, s___}, {s, 1}], RuleDelayed[{1, _, s___}, {s, 1, 1, 0}]}, {0, {1, 1, 0}}, 5]
Out[16]=
In[17]:=
ResourceFunction[ "TagSystemEvolve"][{List[{0, _, s___}, {s, 1}], List[{1, _, s___}, {s, 1, 1, 0}]}, {0, {1, 1, 0}}, 5]
Out[17]=

The specified rules must reflect how a tag system actually works; in this case, elements should not be added to the beginning of the tape:

In[18]:=
ResourceFunction[ "TagSystemEvolve"][{{0, _, s___} :> {0, s, 1}, {1, _, s___} :> {1, s, 1, 1, 0}}, {0, {1, 1, 0}}, 5]
Out[18]=

TagSystemEvolveList does not support tag systems in which the number of elements to be deleted from the beginning of the tape is not consistent across rules:

In[19]:=
ResourceFunction[ "TagSystemEvolve"][{{0, s___} :> {s, 1}, {1, _, s___} :> {s, 1, 1, 0}}, {0, {1, 1, 0}}, 5]
Out[19]=

Version History

  • 1.0.1 – 12 April 2021
  • 1.0.0 – 19 March 2021

Related Resources

License Information