After 100 Years, Can We Finally Crack Post’s Problem of Tag?

“[Despite] Appreciable Effort… [It Proved] Intractable”

Within the early years of the 20th century it seemed as if—if solely the correct strategy could possibly be discovered—all of arithmetic may by some means systematically be solved. In 1910 Whitehead and Russell had revealed their monumental Principia Mathematica displaying (fairly awkwardly) how all types of arithmetic could be represented in terms of logic. However Emil Post needed to go additional. In what appears now like a fairly fashionable concept (with sure similarities to the core construction of the Wolfram Language, and really very like the string multiway systems in our Physics Project), he needed to characterize the logic expressions of Principia Mathematica as strings of characters, after which have attainable operations correspond to transformations on these strings.

In the summertime of 1920 it was all going fairly effectively, and Emil Put up as a freshly minted math PhD from Columbia arrived in Princeton to take up a prestigious fellowship. However there was one ultimate downside. Having transformed every part to string transformations, Put up wanted to have a concept of what such transformations may do.

He progressively simplified issues, till he reached what he referred to as the issue of “tag”. Take a string of 0s and 1s. Drop its first ν components. Have a look at the primary dropped ingredient. If it’s a 0 add a sure block of components on the finish of the string, and if it’s a 1 add one other block. Put up solved a number of circumstances of this downside.

However then he got here throughout the one he described as 000, 11101 with ν=3. Right here’s an instance of its habits:

Style
&#10005
Type[Text[
  Column[Row /@ 
    NestList[
     Replace[#, {{0, _, _, s___} -> {s, 0, 0}, {1, _, _, s___} -> {s, 
          1, 1, 0, 1}}] &, IntegerDigits[5, 2, 3], 10], 
   Spacings -> .2]], FontFamily -> "Roboto"]

After just a few steps it simply leads to a easy loop, alternating endlessly between two strings. Right here’s one other instance, beginning now from a special string:

Style
&#10005
Type[Text[
  Column[Row /@ 
    NestList[
     Replace[#, {{0, _, _, s___} -> {s, 0, 0}, {1, _, _, s___} -> {s, 
          1, 1, 0, 1}}] &, IntegerDigits[18, 2, 5], 30]]], 
 FontFamily -> "Roboto"]

Once more this leads to a loop, now involving 6 attainable strings.

However what occurs normally? To Put up, fixing this downside was a seemingly easy stepping stone to his program of fixing all of arithmetic. And he started on it within the early summer time of 1921, little doubt anticipating that such a simple-to-state downside would have a correspondingly easy resolution.

However fairly than discovering a easy resolution, he as a substitute found that he may make little actual progress. And after months of labor he lastly determined that the issue was in truth, as he later stated, “hopeless”—and consequently, he concluded, so was his complete strategy to “fixing arithmetic”.

What had occurred? Effectively, Put up had seen a glimpse of a very unanticipated however basic function of what we now name computation. A decade later what was happening grew to become a bit of clearer when Kurt Gödel found Gödel’s theorem and undecidability. (As Put up later put it: “I might have found Gödel’s theorem in 1921—if I had been Gödel.”) Then because the years glided by, and Turing machines and other kinds of computational systems have been launched, tag methods started to look extra about computation than about arithmetic, and in 1961 Marvin Minsky proved that in truth a suitably constructed tag system could be made to do any computation that any Turing machine may do.

However what about Put up’s specific, quite simple tag system? It nonetheless appeared very shocking that one thing so easy may behave in such sophisticated methods. However sixty years after Put up’s work, once I started to systematically explore the computational universe of simple programs, it started to look so much much less shocking. For—as my Principle of Computational Equivalence implies—all through the computational universe, above some very low threshold, even in methods with quite simple guidelines, I used to be seeing the phenomenon of computational irreducibility, and nice complexity of habits.

However now a century has handed since Emil Put up battled along with his tag system. So armed with all our discoveries—and all our fashionable instruments and know-how—what can we now say about it? Can we lastly crack Put up’s downside of tag? Or—easy as it’s—will it use the drive of computational irreducibility to withstand all our efforts?

That is the story of my current efforts to wage my very own battle in opposition to Put up’s tag system.

The Primary Setup

The Wolfram Language may be seen partially as a descendent of Put up’s concept of representing every part when it comes to transformation guidelines (although for symbolic expressions fairly than strings). So it’s no shock that Put up’s downside of tag is very simple to set up in the Wolfram Language:

NestList
&#10005
NestList[Replace[{
    {0, _, _, s___} -> {s, 0, 0},
    {1, _, _, s___} -> {s, 1, 1, 0, 1}
    }], {1, 0, 0, 1, 0}, 10] // Column

NestList

Given the preliminary string, the whole habits is at all times decided. However what can occur? Within the examples above, what we noticed is that after some “transient” the system falls right into a cycle which repeats endlessly.

Right here’s a plot for all attainable preliminary strings as much as size 7. In every case there’s a transient and a cycle, with lengths proven within the plot (with cycle size stacked on prime of transient size):

With
&#10005
With[{list = Catenate[Table[Tuples[{0, 1}, n], {n, 7}]]}, 
 ListStepPlot[
  Transpose[((Length /@ 
        FindTransientRepeat[
         ResourceFunction["TagSystemEvolveList"]["Post", #, 1000], 
         4]) & /@ checklist)], Heart, PlotRange -> {0, 28}, 
  PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
  PlotLayout -> "Stacked", Joined -> True, Filling -> Automated, 
  Body -> True, AspectRatio -> 1/5, 
  FrameTicks -> {, {Extract[
      MapThread[
       List[#1, 
         Rotate[
          Style[StringJoin[ToString /@ #2], FontFamily -> "Roboto", 
           Small], 90 Diploma]] &, Vary[0, 253], checklist], 
      Place[list, 
       Alternatives @@ 
        Select[list, 
         IntegerExponent[FromDigits[#, 2], 2] > Size[#]/2 && 
           Size[#] > 1 &]]], None}}]]

(Notice that if the system reaches 00—or one other string with lower than 3 characters—one can both say that it has a cycle of size 1, or that it stops fully, successfully with a cycle of size 0.) For preliminary strings as much as size 7, the nontrivial cycles noticed are of lengths 2 and 6.

Ranging from 10010 as above, we are able to present the habits straight—or we are able to attempt to compensate for the removing of components from the entrance at every step by rotating at every step:

MapIndexed
&#10005
MapIndexed[
 With[{func = #1, ind = #2}, 
   ArrayPlot[
    MapIndexed[func, 
     PadRight[
      ResourceFunction["TagSystemEvolveList"]["Post", {1, 0, 0, 1, 0},
        40], If[First[ind] == 1, Automated, 17, Automated], .25]], 
    Mesh -> True, MeshStyle -> GrayLevel[0.75, 0.75], Body -> False, 
    ImageSize -> Automated, 240]] &, {# &, 
  RotateLeft[#, 3 (First[#2] - 1)] &}]

We will additionally present solely successive “generations” during which the rule has successfully “gone by means of the entire string”:

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  NestList[
   Last[ResourceFunction["TagSystemEvolveList"]["Post", #, 
      Quotient[Length[#], 3]]] &, {1, 0, 0, 1, 0}, 30], Automated, 
   17, .25], Mesh -> True, MeshStyle -> GrayLevel[0.75, .75], 
 Body -> False, ImageSize -> ]

Let’s proceed to longer preliminary sequences. Listed below are the lengths of transients and cycles for preliminary sequences as much as size 12:

With
&#10005
With[{list = Catenate[Table[Tuples[{0, 1}, n], {n, 12}]]}, 
 ListStepPlot[
  Transpose[((Length /@ 
        FindTransientRepeat[
         ResourceFunction["TagSystemEvolveList"]["Post", #, 1000], 
         4]) & /@ checklist)], Heart, PlotRange -> All, 
  PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
  PlotLayout -> "Stacked", Joined -> True, Filling -> Automated, 
  Body -> True, AspectRatio -> 1/6, 
  FrameTicks -> {, {Extract[
      MapThread[
       List[#1, 
         Rotate[
          Style[StringJoin[ToString /@ #2], FontFamily -> "Roboto", 
           Small], 90 Diploma]] &, Vary[0, 8189], checklist], 
      Place[list, 
       Alternatives @@ 
        Select[list, 
         IntegerExponent[FromDigits[#, 2], 2] > Size[#]/1.3 && 
           Size[#] > 7 &]]], None}}]]

All of the cycles are fairly quick—in truth they’re all of lengths 0, 2, 4, 6 or 10. And for preliminary strings as much as size 11, the transients (which we are able to consider as “halting instances”) are at most of size 28. However at size 12 the string 100100100000 immediately offers a transient of size 419, earlier than lastly evolving to the string 00.

Right here’s a plot of the sequence of lengths of intermediate strings produced on this case (the utmost size is 56):

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction["TagSystemEvolveList"][
  "Post", {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 501, 1, "Lengths"], 
 Filling -> Axis, Body -> True, AspectRatio -> 1/3, 
 PlotStyle -> Hue[0.07, 1, 1]]

And, by the way in which, this provides a sign of why Put up referred to as this the “downside of tag” (on the suggestion of his colleague Bennington Gill). Parts carry on getting faraway from the “head” of the string, and added to its “tail”. However will the top meet up with the tail? When it does, it’s like somebody profitable a game of tag, by with the ability to “attain the final individual”.

Right here’s an image of the detailed habits within the case above:

(Row
&#10005
(Row[ArrayPlot[#, ImageSize -> {100, Automatic}] & /@ 
     Partition[
      MapIndexed[#, 
       PadRight[
        ResourceFunction["TagSystemEvolveList"][
         "Post", {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 501], 
        Automated, .25]], UpTo[210]]]) & /@ {# &, 
  RotateLeft[#, 3 (First[#2] - 1)] &}

And right here’s the “generational” plot, now flipped round to go from left to proper:

ArrayPlot
&#10005
ArrayPlot[
 [email protected]
  [email protected]
   PadRight[
    NestList[
     Last[
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Quotient[Length[#], 3]]] &, {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 
      0}, 50], Automated, 58, .25], Mesh -> True, 
 MeshStyle -> GrayLevel[0.75, .75], Body -> False]

By the way in which, we are able to characterize the whole historical past of the tag system simply by concatenating the unique string with all of the blocks of components which are added to it, by no means eradicating blocks of components initially. On this case that is the length-1260 string we get:

Style
&#10005
TSDirectEvolveSequence[init_, t_] := 
 First[NestWhile[{Join[
      First[#], {{0, 0}, {1, 1, 0, 1}}[[1 + #[[1]][[#[[2]]]]]]], #[[
       2]] + 3} &, {init, 1}, Size[First[#]] >= #[[2]] &, 1, t]]
Type[StringJoin[
  ToString /@ 
   TSDirectEvolveSequence[{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 440]],
  FontFamily -> "Roboto", 9]

Plotting the “stroll” obtained by going up at every 1 and down at every 0 we get (and never surprisingly, that is mainly the identical curve because the sequence of complete string lengths above):

ListLinePlot
&#10005
TSDirectEvolveSequence[init_, t_] := 
 First[NestWhile[{Join[
      First[#], {{0, 0}, {1, 1, 0, 1}}[[1 + #[[1]][[#[[2]]]]]]], #[[
       2]] + 3} &, {init, 1}, Size[First[#]] >= #[[2]] &, 1, t]]
ListLinePlot[
 Accumulate[
  2 TSDirectEvolveSequence[{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 
     440] - 1], Body -> True, AspectRatio -> 1/3, 
 PlotStyle -> Hue[0.07, 1, 1]]

How “random” is the sequence of 0s and 1s? There are a complete of 615 1s and 645 0s in the entire sequence—so roughly equal. For length-2 blocks, there are solely about 80% as many 01s and 10s as 00s and 11s. For length-3 blocks, the disparities are bigger, with solely 30% as many 001 blocks occurring as 000 blocks.

After which at size 4, there’s something new: not one of the blocks

Text
&#10005
TSDirectEvolveSequence[init_, t_] := 
 First[NestWhile[{Join[
      First[#], {{0, 0}, {1, 1, 0, 1}}[[1 + #[[1]][[#[[2]]]]]]], #[[
       2]] + 3} &, {init, 1}, Size[First[#]] >= #[[2]] &, 1, t]]
Textual content[Row /@ 
  Complement[Tuples[{1, 0}, 4], 
   Union[
    Partition[
     TSDirectEvolveSequence[{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 
      450], 4, 1]]]]

ever seem in any respect, and 0010 seems solely twice, each initially of the sequence. Trying on the rule, it’s simple to see why, for instance, 1111 can by no means happen—as a result of no sequence of the 00s and 1101s inserted by the rule can ever produce it. (We’ll talk about block occurrences extra beneath.)

OK, so we’ve discovered some pretty sophisticated habits even with preliminary strings of size 12. However what about longer strings? What can occur with them? Earlier than exploring this, it’s helpful to look in a bit of extra element on the construction of the underlying downside.

The Area of Potential States

To seek out out what can occur in our tag system, we’ve enumerated all attainable preliminary strings as much as sure lengths. Nevertheless it seems that there’s lots of redundancy on this—as our plots of “halting instances” above may counsel. And the reason being that the way in which the tag system operates, solely each third ingredient within the preliminary string truly ever issues. So far as the rule is worried we are able to simply fill in _ for the opposite components:

Style
&#10005
CloudGet["https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Programs-01.wl"];
						Type[Text[
  Column[Row /@ 
    NestList[
     Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[
        1 + First[#]]]] &, {0, _, _, 1, _, _, 1, _, _, 1, _, _, 
      1, _, _}, 10]]], FontFamily -> "Roboto"]

The _’s will steadily be “eaten up”, and whether or not they have been initially crammed in with 0s or 1s won’t ever matter. So given this, we don’t lose any data through the use of a compressed illustration of the strings, during which we specify solely each third ingredient:

Style
&#10005
CloudGet["https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Programs-01.wl"];
						Type[Text[
  Grid[[email protected]{Row /@ (MapAt[
          Style[#1, Bold] &, #, {1 ;; -1 ;; 3}] & /@ 
        NestList[
         Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[
            1 + First[#]]]] &, {0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1,
           0, 0}, 10]), 
     Row[{Style[Row[Take[#, 1 ;; -1 ;; 3]], Daring], 
         Type[Row[{Style[":", Gray], Mod[Length[#], 3]}], 
          Small]}] & /@ 
      NestList[
       Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[1 + First[#]]]] &, {0,
         0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0}, 10]}, 
   Dividers -> Heart, FrameStyle -> LightGray, Alignment -> Left]], 
 FontFamily -> "Roboto"]

However truly this isn’t fairly sufficient. We additionally have to say the “part” of the top of the string: the variety of trailing components after the final block of three components (i.e. the size of the unique string mod 3).

So now we are able to begin enumerating non-redundant attainable preliminary strings, specifying them within the compressed illustration:

Grid
&#10005
PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

EnumerateInits[n_] := 
 Catenate[
  Table[{p, IntegerDigits[i, 2, n]}, {i, 0, 2^n - 1}, {p, 0, 2}]]

Grid[[email protected]
  Partition[
   Text[Style[#, FontFamily -> "Roboto"]] & /@ 
    PhasedStringForm /@ EnumerateInits[3], 6], Spacings -> {1.5, .2}]

Given a string in compressed type, we are able to explicitly compute its evolution. The efficient guidelines are a bit of extra sophisticated than for the underlying uncompressed string, however for instance the next will apply one step of evolution to any compressed string (represented within the type ):

Replace
&#10005
Substitute[
 {{0, {0, s___}} -> {2, {s, 0}}, {0, {1, s___}} -> {1, {s, 1, 1}},
  {1, {0, s___}} -> {0, {s}}, {1, {1, s___}} -> {2, {s, 0}},
  {2, {0, s___}} -> {1, {s, 0}}, {2, {1, s___}} -> {0, {s, 1}}}]

Can we reconstruct an uncompressed string from a compressed one? Effectively, no, not uniquely. As a result of the “intermediate” components that will probably be ignored by the rule aren’t specified within the compressed type. Given, say, the compressed string 10:2 we all know the uncompressed string have to be of the shape 1__0_ however the _’s aren’t decided. Nevertheless, if we truly run the rule, we get

Style
&#10005
Type[Text[
  Column[
   Row /@ 
    ResourceFunction["TagSystemEvolveList"]["Post", {1, _, _, 0, _}, 
     3]]], FontFamily -> "Roboto"]

in order that the blanks in impact rapidly resolve. (By the way in which, given a compressed string s:0 the uncompressed one is __, for s:1 it’s simply , and for s:2 it’s , with the uncompressed string size mod 3 being equal to the part.)

So taking all compressed strings as much as size 4 right here is the sequence of transient and cycle lengths obtained:

ListStepPlot
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

ListStepPlot[
 Transpose[((Length /@ 
       FindTransientRepeat[
        ResourceFunction["TagSystemEvolveList"]["Post", #, 1000], 
        4]) & /@ Catenate[Table[DistinctInits[i], {i, 4}]])], Heart, 
 PlotRange -> , PlotLayout -> "Stacked", 
 PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
 Joined -> True, Filling -> Automated, Body -> True, 
 AspectRatio -> 1/5]

The primary case that’s minimize off within the plot has halting time 419; it corresponds to the compressed string 1110:0.

We will consider compressed strings as equivalent to attainable non-redundant “states” of the tag system. After which we are able to characterize the worldwide evolution of the system by establishing a state transition graph that connects every state to its successor within the evolution. Right here is the consequence ranging from distinct length-3 strings (right here proven in uncompressed type; the scale of every node displays the size of the string):

With
&#10005
With[{g = 
   VertexDelete[
    NestGraph[
     Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] &, {{0, 
       0, 0}, {1, 0, 0}}, 400], {0, 1}]}, 
 HighlightGraph[
  Graph[g, VertexSize -> (# -> .1 Sqrt[Length[#]] & /@ VertexList[g]),
    VertexStyle -> Hue[0.58, 0.65, 1], 
   EdgeStyle -> Hue[0.58, 1, 0.7000000000000001], 
   VertexLabels -> (# -> Positioned[Row[#], Above] & /@ 
      VertexList[g])], {Type[
    Subgraph[g, FindCycle[g, {1, Infinity}, All]], Thick, Hue[
    0.02, 0.92, 0.8200000000000001]], 
   Decide[VertexList[g], VertexOutDegree[g], 0]}]]

There’s a length-2 cycle, indicated in pink, and in addition a “terminating state” indicated in yellow. Right here’s the state transition graph beginning with all length-1 compressed strings (i.e. non-redundant uncompressed strings with lengths between 3 and 5)—with nodes now labeled simply with the (uncompressed) size of the string that they characterize:

With
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

With[{g = 
   VertexDelete[
    NestGraph[
     Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] &, 
     DistinctInits[1], 400], {0, 1}]}, 
 HighlightGraph[
  Graph[g, VertexSize -> (# -> .1 Sqrt[Length[#]] & /@ VertexList[g]),
    VertexStyle -> Hue[0.58, 0.65, 1], 
   EdgeStyle -> Hue[0.58, 1, 0.7000000000000001], 
   VertexLabels -> (# -> Positioned[Length[#], Above] & /@ 
      VertexList[g])], {Type[
    Subgraph[g, FindCycle[g, {1, Infinity}, All]], Thick, Hue[
    0.02, 0.92, 0.8200000000000001]], 
   Decide[VertexList[g], VertexOutDegree[g], 0]}]]

We see the identical length-2 cycle and terminating state as we noticed earlier than. However now there’s additionally a length-6 cycle. The unique “feeder” for this length-6 cycle is the string 10010 (compressed: 11:2), which takes 16 steps to achieve the cycle.

Listed below are the corresponding outcomes for compressed preliminary strings as much as successively better lengths n, with the lengths of cycles labeled:

GraphicsRow
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

GraphicsRow[
 Table[Labeled[
   Framed[
    Show[
     With[{g = 
        VertexDelete[
         NestGraph[
          Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] &, 
          Catenate[Table[DistinctInits[i], {i, n}]], 700], {0, 1}]}, 
      With[{c = FindCycle[g, {1, Infinity}, All]}, 
       HighlightGraph[
        Graph[g, 
         VertexLabels -> 
          Join[(#[[1, 1]] -> 
               Positioned[
                Style[Length[#], 11, 
                 Darker[Hue[
                  0.02, 0.92, 0.8200000000000001], .2]], ] & /@ 
             c), # -> Type[1, 11, Darker[Yellow, .4]] & /@ 
            Decide[VertexList[g], VertexOutDegree[g], 0]], 
         VertexSize -> (# -> .3 Sqrt[Length[#]] & /@ VertexList[g]), 
         VertexStyle -> Hue[0.58, 0.65, 1], 
         EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], Type[
          Subgraph[g, c], Thick, Hue[0.02, 0.92, 0.8200000000000001]],
          Decide[VertexList[g], VertexOutDegree[g], 0]]]], 
     ImageSize -> {UpTo[250], UpTo[250]}], FrameStyle -> LightGray], 
   Type[
    Text[Row[{Style["n", Italic], " \[LessEqual] ", ToString[n]}]], 
    10]], {n, 2, 3}]]
GraphicsColumn
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

GraphicsColumn[
 Table[Labeled[
   Framed[
    Show[
     With[{g = 
        VertexDelete[
         NestGraph[
          Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] &, 
          Catenate[Table[DistinctInits[i], {i, n}]], 700], {0, 1}]}, 
      With[{c = FindCycle[g, {1, Infinity}, All]}, 
       HighlightGraph[
        Graph[g, VertexStyle -> Hue[0.58, 0.65, 1], 
         EdgeStyle -> Hue[0.58, 1, 0.7000000000000001], 
         VertexLabels -> 
          Be a part of[(#[[1, 1]] -> 
               Positioned[
                Style[Length[#], 11, 
                 Darker[Hue[
                  0.02, 0.92, 0.8200000000000001], .2]], {After, 
                 Above}] & /@ 
             c), # -> Type[1, 11, Darker[Yellow, .4]] & /@ 
            Decide[VertexList[g], VertexOutDegree[g], 0]], 
         VertexSize -> (# -> .6 Sqrt[Length[#]] & /@ VertexList[g]), 
         GraphStyle -> "Default"], Type[Subgraph[g, c], Thick, Purple],
          Decide[VertexList[g], VertexOutDegree[g], 0]]]], 
     ImageSize -> {UpTo[500], UpTo[200]}], FrameStyle -> LightGray], 
   Type[
    Text[Row[{Style["n", Italic], " \[LessEqual] ", ToString[n]}]], 
    10]], {n, 4, 5}], ImageSize -> 550, Automated]

A notable function of those graphs is that at compressed size 4, a protracted “freeway” seems that goes for about 400 steps. The freeway mainly represents the lengthy transient first seen for the preliminary string 11:2. There’s one “on-ramp” for this string, however then there’s additionally a tree of different states that enter the identical freeway.

Why is there a “freeway” within the first place? Mainly as a result of the length-419 transient entails strings which are lengthy in comparison with any we’re ranging from—so nothing can feed into it after the start, and it mainly simply has to “work itself by means of” till it reaches no matter cycle it leads to.

Once we enable preliminary strings with compressed size as much as 6 a brand new freeway seems, dwarfing the earlier one (by the way in which, a lot of the wiggliness we see is an artifact of the graph structure):

With
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]
With[{n = 6}, 
 Labeled[
  Framed[
   With[{g = 
      VertexDelete[
       NestGraph[
        Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] &, 
        Catenate[Table[DistinctInits[i], {i, n}]], 20000], {0, 1}]}, 
    With[{c = FindCycle[g, {1, Infinity}, All]}, 
     HighlightGraph[
      Graph[g, VertexStyle -> Hue[0.58, 0.65, 1], 
       EdgeStyle -> Hue[0.58, 1, 0.7000000000000001], 
       VertexLabels -> 
        Be a part of[(#[[1, 1]] -> 
             Positioned[
              Style[Length[#], 11, 
               Darker[Hue[
                0.02, 0.92, 0.8200000000000001], .2]], ] & /@ 
           c), # -> Type[1, 11, Darker[Yellow, .4]] & /@ 
          Decide[VertexList[g], VertexOutDegree[g], 0]], 
       VertexSize -> (# -> .6 Sqrt[Length[#]] & /@ VertexList[g]), 
       GraphStyle -> "Default"], ]]], 
   FrameStyle -> LightGray], 
  Type[Text[
    Row[{Style["n", Italic], " \[LessEqual] ", ToString[n]}]], 10]]]

The primary preliminary state to achieve this freeway is 111010:0 (uncompressed: 100100100000100000)—which after 2141 steps evolves to a cycle of size 28. Listed below are the lengths of the intermediate strings alongside this freeway (word the cycle on the finish):

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction["TagSystemEvolveList"][
  "Post", {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, 
  2300, 1, "Lengths"], Filling -> Axis, Body -> True, 
 AspectRatio -> 1/3, PlotStyle -> Hue[0.07, 1, 1]]

And listed below are the “generational states” reached (word that trying solely at generations makes the ultimate 28-cycle present up as a 1-cycle):

ArrayPlot
&#10005
ArrayPlot[
 [email protected]
  [email protected]
   PadRight[
    NestList[
     Last[
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Quotient[Length[#], 3]]] &, {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 
      0, 1, 0, 0, 0, 0, 0}, 80], , .25], 
 Body -> False]

Or “compressed strings” (i.e. together with solely each third ingredient of every string):

ArrayPlot
&#10005
ArrayPlot[
 [email protected]
  [email protected]
   PadRight[
    Last /@ 
     NestList[
      Last[
        ResourceFunction["TagSystemEvolve"]["Post", #, 
         Length[Last[#]]]] &, {0, {1, 1, 1, 0, 1, 0}}, 
      80], , .25], Body -> False]

If we think about all preliminary strings as much as compressed size 6, we get the next transient+cycle lengths:

Transpose
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

ListStepPlot[
 Transpose[
  ResourceFunction["ParallelMapMonitored"][
   Length /@ 
     FindTransientRepeat[
      ResourceFunction["TagSystemEvolveList"]["Post", #, 2400], 4] &, 
   Catenate[Table[DistinctInits[i], {i, 6}]]]], Heart, 
 PlotRange -> {0, All}, 
 PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
 PlotLayout -> "Stacked", Joined -> True, Filling -> Automated, 
 Body -> True, AspectRatio -> 1/4]

And what we see is that there are specific lengths of transients—equivalent to the highways within the state transition graph above—to which sure strings evolve. If we plot the distribution of halting (i.e. transient) instances for all of the strings we discover, then, as anticipated, it peaks across the lengths of the principle highways:

Histogram
&#10005
DistinctInits[n_] := 
 First /@ 
  GatherBy[Catenate[Table[Tuples[{0, 1}, 3 n + p], {p, 0, 2}]], 
   ResourceFunction["TagSystemConvert"][#] &]

Histogram[
 Total /@ 
  ResourceFunction["ParallelMapMonitored"][
   Length /@ 
     FindTransientRepeat[
      ResourceFunction["TagSystemEvolveList"]["Post", #, 2400], 4] &, 
   Catenate[Table[DistinctInits[i], {i, 6}]]], {1}, "Log", "Depend", 
 PlotRange -> All, Body -> True, AspectRatio -> 1/3, 
 ChartStyle -> Hue[0.07, 1, 1]]

So given a specific “on-ramp to a freeway”—or, for that matter, a state on a cycle—what states will evolve to it? On the whole there’ll be a tree of states within the state transition graph which are the “predecessors” of a given state—in impact forming its “basin of attraction”.

For any specific string the rule offers a singular successor. However we are able to additionally think about “working the rule backwards”. And if we do that, it seems that any given compressed string can have 0, 1 or 2 speedy predecessors. For instance, 000:0 has the distinctive predecessor 0000:1. However 001:0 has each 0001:1 and 100:2 as predecessors. And for instance 001:1 has no predecessors. (For uncompressed strings, there are at all times both 0 or 4 speedy predecessors.)

Any state that has no predecessors can happen solely because the preliminary string; it may well by no means be generated within the evolution. (There are comparable outcomes for substrings, as we’ll talk about later.)

And if we begin from a state that does have at the least one predecessor, we are able to normally assemble a complete tree of “successively additional again” predecessors. Right here, for instance, is the 10-step tree for 000:2:

With
&#10005
PhaseStepBackwards[{phase_, state_}] :=
 Module[{s1, s2},
  s1 = Last[state];
  s2 = Take[state, -2] == {1, 1};
  Swap[phase,
   0, If[
    s1 == 
     1, {{1, Join[{0}, state]}, {2, Be a part of[{1}, Most[state]]}}, {{1, 
      Be a part of[{0}, state]}}],
   1, If[
    s1 == 0 || 
     s2, {If[
      s2, {0, Join[{1}, Drop[state, -2]]}, {2, 
       Be a part of[{0}, Most[state]]}]}, Nothing],
   2, If[
    s1 == 
     0, {{0, Join[{0}, Most[state]]}, {1, Be a part of[{1}, Most[state]]}}, 
    Nothing]]]

PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

With[{g = 
   Graph[# -> 
       Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] & /@ 
     Union[
      Flatten[
       NestList[
        Flatten[PhaseStepBackwards[#] & /@ #, 1] &, {{0, {0, 0, 0}}}, 
        10], 1]]]}, 
 Graph[g, 
  VertexLabels -> (# -> PhasedStringForm[#] & /@ VertexList[g]), 
  AspectRatio -> 1, VertexStyle -> Hue[0.58, 0.65, 1], 
  EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]]]

Right here it’s after 30 steps, in two completely different renderings:

With
&#10005
PhaseStepBackwards[{phase_, state_}] :=
 Module[{s1, s2},
  s1 = Last[state];
  s2 = Take[state, -2] == {1, 1};
  Swap[phase,
   0, If[
    s1 == 
     1, {{1, Join[{0}, state]}, {2, Be a part of[{1}, Most[state]]}}, {{1, 
      Be a part of[{0}, state]}}],
   1, If[
    s1 == 0 || 
     s2, {If[
      s2, {0, Join[{1}, Drop[state, -2]]}, {2, 
       Be a part of[{0}, Most[state]]}]}, Nothing],
   2, If[
    s1 == 
     0, {{0, Join[{0}, Most[state]]}, {1, Be a part of[{1}, Most[state]]}}, 
    Nothing]]]

PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

With[{g = 
   Graph[# -> 
       Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] & /@ 
     Union[
      Flatten[
       NestList[
        Flatten[PhaseStepBackwards[#] & /@ #, 1] &, {{0, {0, 0, 0}}}, 
        30], 1]]]}, 
 Graph[g, VertexStyle -> Hue[0.58, 0.65, 1], 
  EdgeStyle -> Hue[0.58, 1, 0.7000000000000001], 
  GraphLayout -> "LayeredDigraphEmbedding", AspectRatio -> 1/2]]
With
&#10005
PhaseStepBackwards[{phase_, state_}] :=
 Module[{s1, s2},
  s1 = Last[state];
  s2 = Take[state, -2] == {1, 1};
  Swap[phase,
   0, If[
    s1 == 
     1, {{1, Join[{0}, state]}, {2, Be a part of[{1}, Most[state]]}}, {{1, 
      Be a part of[{0}, state]}}],
   1, If[
    s1 == 0 || 
     s2, {If[
      s2, {0, Join[{1}, Drop[state, -2]]}, {2, 
       Be a part of[{0}, Most[state]]}]}, Nothing],
   2, If[
    s1 == 
     0, {{0, Join[{0}, Most[state]]}, {1, Be a part of[{1}, Most[state]]}}, 
    Nothing]]]

PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

With[{g = 
   Graph[# -> 
       Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] & /@ 
     Union[
      Flatten[
       NestList[
        Flatten[PhaseStepBackwards[#] & /@ #, 1] &, {{0, {0, 0, 0}}}, 
        30], 1]]]}, 
 Graph[g, VertexStyle -> Hue[0.58, 0.65, 1], 
  EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]]]

If we proceed this specific tree we’ll mainly get a state transition graph for all states that finally terminate. Not surprisingly, there’s appreciable complexity on this tree—although the variety of states after t steps does develop roughly exponentially (apparently like ):

ListStepPlot
&#10005
PhaseStepBackwards[{phase_, state_}] :=
 Module[{s1, s2},
  s1 = Last[state];
  s2 = Take[state, -2] == {1, 1};
  Swap[phase,
   0, If[
    s1 == 
     1, {{1, Join[{0}, state]}, {2, Be a part of[{1}, Most[state]]}}, {{1, 
      Be a part of[{0}, state]}}],
   1, If[
    s1 == 0 || 
     s2, {If[
      s2, {0, Join[{1}, Drop[state, -2]]}, {2, 
       Be a part of[{0}, Most[state]]}]}, Nothing],
   2, If[
    s1 == 
     0, {{0, Join[{0}, Most[state]]}, {1, Be a part of[{1}, Most[state]]}}, 
    Nothing]]]

ListStepPlot[
 Length /@ 
  NestList[
   Flatten[PhaseStepBackwards[#] & /@ #, 1] &, {{0, {0, 0, 0}}}, 
   100], Heart, Body -> True, Filling -> Axis, 
 ScalingFunctions -> "Log", AspectRatio -> 1/3, 
 PlotStyle -> Hue[0.07, 1, 1]]

By the way in which, there are many states which have finite predecessor timber. For instance 1100:0 yields a tree which grows just for 21 steps, then stops:

Rotate
&#10005
PhaseStepBackwards[{phase_, state_}] :=
 Module[{s1, s2},
  s1 = Last[state];
  s2 = Take[state, -2] == {1, 1};
  Swap[phase,
   0, If[
    s1 == 
     1, {{1, Join[{0}, state]}, {2, Be a part of[{1}, Most[state]]}}, {{1, 
      Be a part of[{0}, state]}}],
   1, If[
    s1 == 0 || 
     s2, {If[
      s2, {0, Join[{1}, Drop[state, -2]]}, {2, 
       Be a part of[{0}, Most[state]]}]}, Nothing],
   2, If[
    s1 == 
     0, {{0, Join[{0}, Most[state]]}, {1, Be a part of[{1}, Most[state]]}}, 
    Nothing]]]

PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

Rotate[With[{g = 
    Graph[# -> 
        Last[ResourceFunction["TagSystemEvolve"]["Post", #, 1]] & /@ 
      Union[
       Flatten[
        NestList[
         Flatten[PhaseStepBackwards[#] & /@ #, 
           1] &, {{0, {1, 1, 0, 0}}}, 21], 1]]]}, 
  Graph[g, GraphLayout -> "LayeredDigraphEmbedding", 
   VertexStyle -> Hue[0.58, 0.65, 1], 
   EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]]], 90 Diploma]

The Cycle Construction

A minimum of in all of the circumstances we’ve seen to this point, our tag system at all times evolves to a cycle (or terminates in a trivial state). However what cycles are attainable? In impact any cycle state S have to be an answer to a “tag eigenvalue equation” of the shape S = S for some p, the place T is the “tag evolution operator”.

Beginning with compressed strings of size 1, just one cycle can ever be reached:

First
&#10005
AllInits[count_] := 
  Tuples[Range[0, 2], 
    IntegerDigits[#, 2, count] & /@ Vary[0, 2^count - 1]];

FindCycleStructure[len_, labels_] := 
 With[{v = 
    Map[{#, 
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Method -> "BitwiseOptimized", MaxSteps -> 1000]} &, 
     AllInits[len]]},
  With[{g = 
     FindCycle[
      SimpleGraph[
       DirectedEdge[#, 
          ResourceFunction["TagSystemEvolve"]["Post", #, 1][
           "FinalState"]] & /@ 
        Be a part of @@ (Be a part of @@ 
             FindTransientRepeat[#, 
              2] & /@ (ResourceFunction["TagSystemEvolveList"][
               "Post", 
               ResourceFunction["TagSystemConvert"][#[[1]]], #[[2, 
                "EventCount"]]] & /@ v))], {1, Infinity}, All]}, 
   Desk[
    Graph[g[[i]], 
     VertexLabels -> (# -> labels[#] & /@ VertexList[g[[i]]]), 
     VertexStyle -> Hue[0.58, 0.65, 1], 
     EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], i, 
     Vary[Length[g]]]
   ]
  ]

First[FindCycleStructure[1, Placed[Row[#], Above] &]]

Beginning with compressed strings of size 2 a 6-cycle seems (right here proven labeled respectively with uncompressed and with compressed strings):

{Last
&#10005
AllInits[count_] := 
  Tuples[Range[0, 2], 
    IntegerDigits[#, 2, count] & /@ Vary[0, 2^count - 1]];

PhasedStringForm[{p_Integer, s_List}] := 
 Row[{Row[s], Type[Row[{Style[":", Gray], p}], Small]}]

FindCycleStructure[len_, labels_] := 
 With[{v = 
    Map[{#, 
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Method -> "BitwiseOptimized", MaxSteps -> 1000]} &, 
     AllInits[len]]},
  With[{g = 
     FindCycle[
      SimpleGraph[
       DirectedEdge[#, 
          ResourceFunction["TagSystemEvolve"]["Post", #, 1][
           "FinalState"]] & /@ 
        Be a part of @@ (Be a part of @@ 
             FindTransientRepeat[#, 
              2] & /@ (ResourceFunction["TagSystemEvolveList"][
               "Post", 
               ResourceFunction["TagSystemConvert"][#[[1]]], #[[2, 
                "EventCount"]]] & /@ v))], {1, Infinity}, All]}, 
   Desk[
    Graph[g[[i]], 
     VertexLabels -> (# -> labels[#] & /@ VertexList[g[[i]]]), 
     VertexStyle -> Hue[0.58, 0.65, 1], 
     EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], i, 
     Vary[Length[g]]]
   ]
  ]

No new cycles seem till one has preliminary strings of compressed size 4, however then one will get (the place now the states are labeled with their uncompressed lengths):

With
&#10005
AllInits[count_] := 
  Tuples[Range[0, 2], 
    IntegerDigits[#, 2, count] & /@ Vary[0, 2^count - 1]];

FindCycleStructure[len_, labels_] := 
 With[{v = 
    Map[{#, 
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Method -> "BitwiseOptimized", MaxSteps -> 1000]} &, 
     AllInits[len]]},
  With[{g = 
     FindCycle[
      SimpleGraph[
       DirectedEdge[#, 
          ResourceFunction["TagSystemEvolve"]["Post", #, 1][
           "FinalState"]] & /@ 
        Be a part of @@ (Be a part of @@ 
             FindTransientRepeat[#, 
              2] & /@ (ResourceFunction["TagSystemEvolveList"][
               "Post", 
               ResourceFunction["TagSystemConvert"][#[[1]]], #[[2, 
                "EventCount"]]] & /@ v))], {1, Infinity}, All]}, 
   Desk[
    Graph[g[[i]], 
     VertexLabels -> (# -> labels[#] & /@ VertexList[g[[i]]]), 
     VertexStyle -> Hue[0.58, 0.65, 1], 
     EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], i, 
     Vary[Length[g]]]
   ]
  ]

Framed[GraphicsRow[
  Sort[FindCycleStructure[4, Placed[Length[#], Above] &]]], 
 FrameStyle -> LightGray]

The precise cycles are as follows

With
&#10005
AllInits[count_] := 
  Tuples[Range[0, 2], 
    IntegerDigits[#, 2, count] & /@ Vary[0, 2^count - 1]];

FindCycleStructure[len_, labels_] := 
 With[{v = 
    Map[{#, 
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Method -> "BitwiseOptimized", MaxSteps -> 1000]} &, 
     AllInits[len]]},
  With[{g = 
     FindCycle[
      SimpleGraph[
       DirectedEdge[#, 
          ResourceFunction["TagSystemEvolve"]["Post", #, 1][
           "FinalState"]] & /@ 
        Be a part of @@ (Be a part of @@ 
             FindTransientRepeat[#, 
              2] & /@ (ResourceFunction["TagSystemEvolveList"][
               "Post", 
               ResourceFunction["TagSystemConvert"][#[[1]]], #[[2, 
                "EventCount"]]] & /@ v))], {1, Infinity}, All]}, 
   Desk[
    Graph[g[[i]], 
     VertexLabels -> (# -> labels[#] & /@ VertexList[g[[i]]]), 
     VertexStyle -> Hue[0.58, 0.65, 1], 
     EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], i, 
     Vary[Length[g]]]
   ]
  ]

ArrayPlot[
   PadRight[ResourceFunction["CanonicalListRotation"][#], 
    Automated, .25], Mesh -> True, 
   MeshStyle -> GrayLevel[0.75, 0.75], 
   ImageSize -> Automated, Size[#] 11] & /@ (VertexList /@ 
   FindCycleStructure[4, Placed[Row[#], Above] &])

whereas those from length-5 preliminary strings are:

With
&#10005
AllInits[count_] := 
  Tuples[Range[0, 2], 
    IntegerDigits[#, 2, count] & /@ Vary[0, 2^count - 1]];

FindCycleStructure[len_, labels_] := 
 With[{v = 
    Map[{#, 
       ResourceFunction["TagSystemEvolve"]["Post", #, 
        Method -> "BitwiseOptimized", MaxSteps -> 1000]} &, 
     AllInits[len]]},
  With[{g = 
     FindCycle[
      SimpleGraph[
       DirectedEdge[#, 
          ResourceFunction["TagSystemEvolve"]["Post", #, 1][
           "FinalState"]] & /@ 
        Be a part of @@ (Be a part of @@ 
             FindTransientRepeat[#, 
              2] & /@ (ResourceFunction["TagSystemEvolveList"][
               "Post", 
               ResourceFunction["TagSystemConvert"][#[[1]]], #[[2, 
                "EventCount"]]] & /@ v))], {1, Infinity}, All]}, 
   Desk[
    Graph[g[[i]], 
     VertexLabels -> (# -> labels[#] & /@ VertexList[g[[i]]]), 
     VertexStyle -> Hue[0.58, 0.65, 1], 
     EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], i, 
     Vary[Length[g]]]
   ]
  ]

ArrayPlot[
   PadRight[ResourceFunction["CanonicalListRotation"][#], 
    Automated, .25], Mesh -> True, 
   MeshStyle -> GrayLevel[0.75, 0.75], 
   ImageSize -> ] & /@ (VertexList /@ 
   FindCycleStructure[5, Placed[Row[#], Above] &])

What bigger cycles can happen? It’s pretty simple to see {that a} compressed string consisting of any sequence of the blocks 01 and 1100 will yield a state on a cycle. To seek out out about uncompressed strings on cycles, we are able to simply apply the rule 000, 11101, with the consequence that we conclude that any sequence of the length-6 and length-12 blocks 001101 and 110111010000 will give a state on a cycle.

If we plot the durations of cycles in opposition to the lengths of their “seed” strings, we get:

ListPlot
&#10005
ListPlot[
 Style[Catenate[
   Table[ & /@ 
     Tuples[{{0, 0, 1, 1, 0, 1}, {1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 
        0}}, n], {n, 10}]], Hue[0.02, 0.92, 0.8200000000000001]], 
 Body -> True, PlotStyle -> PointSize[.02]]

If we generate cycles from sequences of, say, b of our 01, 1100 blocks, how most of the cycles we get will probably be distinct? Listed below are the durations of the distinct cycles for successive b:

Text
&#10005
Type[Text[
  Grid[Table[{b, 
     Length /@ 
      Union[
       ResourceFunction["CanonicalListRotation"][
          FindRepeat[
           ResourceFunction["TagSystemEvolveList"]["Post", Flatten[#],
             1000]]] & /@ 
        Tuples[{{0, 0, 1, 1, 0, 1}, {1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 
           0}}, b]]}, {b, 6}], Body -> All, FrameStyle -> Grey]], 12]

The overall variety of cycles seems to be:

DivisorSum
&#10005
DivisorSum[n, k |-> EulerPhi[k] 2^(n/ok)]/n
Table
&#10005
Desk[DivisorSum[n, k |-> EulerPhi[k] 2^(n/ok)]/n, {n, 15}]

We will additionally ask an inverse query: of all 2n (uncompressed) strings of size n, what number of of them lie on cycles of the sort we have now recognized? The reply is identical because the variety of distinct “cyclic necklaces” with n beads, every 0 or 1, with no pair of 0s adjoining:

DivisorSum
&#10005
DivisorSum[n, k |-> EulerPhi[n/k] LucasL[k]]/n
Table
&#10005
CloudGet["https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Programs-01.wl"];
					Desk[DivisorSum[n, k |-> EulerPhi[n/k] LucasL[k]]/n, {n, 20}]

Asymptotically that is about —implying that of all strings of size n, solely a fraction of them will probably be on cycles, in order that for big n the overwhelming majority of strings is not going to be on cycles, at the least of this sort.

However are there other forms of cycles? It turns on the market are, although they don’t appear to be frequent or plentiful. One household—at all times of interval 6—are seeded by strings obtained from 00111(000111m) by making use of the rule 0 → 00, 1 → 1101 (with size 16 + 18m):

ArrayPlot
&#10005
ArrayPlot[PadRight[#, Automatic, .25], Mesh -> True, 
   MeshStyle -> GrayLevel[0.75, 0.75], 
   ImageSize -> Automated, Size[#] 8] & /@ 
 Desk[FindRepeat[
   ResourceFunction["TagSystemEvolveList"]["Post", 
    Flatten[
     Flatten[{{0, 0, 1, 1, 1}, 
        Table[{0, 0, 0, 1, 1, 1}, m]}] /. {1 -> {1, 1, 0, 1}, 
       0 -> {0, 0}}], 100]], {m, 3}]

However there are different circumstances too. The primary instance seems with preliminary compressed strings of size 9. The length-13 compressed string 0011111110100 (with uncompressed size 39) yields the period-40 cycle (with uncompressed string lengths between 37 and 44):

ArrayPlot
&#10005
ArrayPlot[PadRight[#, Automatic, .25], Mesh -> True, 
   MeshStyle -> GrayLevel[0.75, 0.75], 
   ImageSize -> ] &[
 FindRepeat[
  ResourceFunction["TagSystemEvolveList"][
   "Post", {0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 
    0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}, 
   400]]]

The subsequent instance happens with an preliminary compressed string of size 15, and a compressed “seed” of size 24—and has interval 282:

ArrayPlot
&#10005
ArrayPlot[PadRight[#, Automatic, .25], Body -> False] &[
 FindRepeat[
  ResourceFunction["TagSystemEvolveList"]["Post", 
   Flatten[{0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 
      1, 1, 1, 0, 0} /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}], 1000]]]

And I’ve discovered yet one more instance (that arises from an preliminary compressed string of size 18) and has interval 66:

ArrayPlot
&#10005
ArrayPlot[PadRight[#, Automatic, .25], Body -> False] &[
 FindRepeat[
  ResourceFunction["TagSystemEvolveList"]["Post", 
   Flatten[{0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 
      0, 0, 1, 1} /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}], 1000]]]

If we take a look at these cycles in “generational” phrases, they’re of lengths 3, 11 and 14, respectively (word that the second two footage above begin with “incomplete generations”):

ArrayPlot
&#10005
ArrayPlot[PadRight[#, Automatic, .25], Body -> False, 
     ImageSize -> ] &[
   NestList[
    Last[
      ResourceFunction["TagSystemEvolve"]["Post", #, 
       Quotient[Length[#], 3]]] &, #, 
    60]] & /@ ((First[Last[#]] &@
      FindTransientRepeat[
       NestList[
        Last[
          ResourceFunction["TagSystemEvolve"]["Post", #, 
           Quotient[Length[#], 3]]] &, #, 100], 3]) & /@ {{0, 0, 0, 0,
      0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 
     1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}, 
    Flatten[{0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 
       1, 1, 1, 0, 0} /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}], 
    Flatten[{0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 
       0, 0, 1, 1} /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}]})

Exploring Additional

I don’t know the way far Emil Put up bought in exploring his tag system by hand a century in the past. And I fairly suspect that we’ve already gone so much additional right here than he ever did. However what we’ve seen has simply deepened the thriller of what tag methods can do. To date, each preliminary string we’ve tried has developed to a cycle (or simply terminated). However will this at all times occur? And the way lengthy can it take?

To date, the longest transient we’ve seen is 2141 steps—from the length-6 compressed string 111010:0. Size-7 and length-8 strings at most simply “observe the identical freeway” within the state transition graph, and don’t give longer transients. However at size 9 one thing completely different occurs: 111111010:0 takes 24,552 steps to evolve a 6-cycle (with string size 12), with the lengths of intermediate (compressed) strings being:

ListStepPlot
&#10005
PuffOut[list : {__Integer}] := 
 Flatten[list /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}]

ListStepPlot[
 Quotient[
  ResourceFunction["TagSystemEvolveList"]["Post", 
   PuffOut[{1, 1, 1, 1, 1, 1, 0, 1, 0}], 25300, 1, "Lengths"], 
  3], Heart, Body -> True, Filling -> Axis, AspectRatio -> 1/3, 
 PlotStyle -> Hue[0.07, 1, 1], MaxPlotPoints -> 4000]

Plotting (from left to proper) the precise components in compressed strings in every “era” this exhibits in additional element what’s “happening inside”:

ArrayPlot
&#10005
PuffOut[list : {__Integer}] := 
 Flatten[list /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}]

ArrayPlot[
 [email protected]
  Transpose[
   PadRight[
    Last /@ 
     NestList[
      Last[
        ResourceFunction["TagSystemEvolve"]["Post", #, 
         Length[Last[#]]]] &, 
      ResourceFunction["TagSystemConvert"][
       PuffOut[{1, 1, 1, 1, 1, 1, 0, 1, 0}]], 400], , .25]], Body -> False]

In systematically exploring what can occur in tag methods, it’s handy to specify preliminary compressed strings by changing their sequences of 1s and 0s to decimal numbers—however as a result of our strings can have main 0s we have now to incorporate the size, say as a prefix. So with this setup our length-9 “halting time winner” 111111010:0 turns into 9:506:0.

The subsequent “winner” is 12:3962:0, which takes 253,456 steps to evolve to a 6-cycle:

ListStepPlot
&#10005
ListStepPlot[
 Transpose[{Table[i, {i, 0, 253456 + 100, 100}], 
   ResourceFunction["TagSystemEvolveList"][
    "Post", {0, {1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0}}, 253456 + 100, 
    100, "Lengths", Method -> "BitwiseOptimized"]}], Heart, 
 Body -> True, Filling -> Axis, AspectRatio -> 1/3, 
 PlotStyle -> Hue[0.07, 1, 1]]

In generational type the specific evolution on this case is:

ArrayPlot
&#10005
PuffOut[list : {__Integer}] := 
 Flatten[list /. {1 -> {1, 1, 0, 1}, 0 -> {0, 0}}]

ArrayPlot[
 [email protected]
  Transpose[
   PadRight[
    Last /@ 
     NestList[
      Last[
        ResourceFunction["TagSystemEvolve"]["Post", #, 
         Length[Last[#]]]] &, 
      ResourceFunction["TagSystemConvert"][
       PuffOut[{1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0}]], 950], 
    Automated, .25]], Body -> False]

The primary case to take over 1,000,000 steps is 15:30166:0—which terminates after 20,858,103 steps:

Show
&#10005
Present[ListStepPlot[
  Transpose[{Range[Length[#]] 4000/(10^6), #} &[
    ResourceFunction["TagSystemEvolveList"][
     "Post", {0, IntegerDigits[30166, 2, 15]}, 20858103, 4000, 
     "Lengths", Methodology -> "BitwiseOptimized"]]], Body -> True, 
  AspectRatio -> 1/3, Filling -> Axis, PlotStyle -> Hue[0.07, 1, 1]], 
 FrameTicks -> {Automated, 
    None, {Thread[{Range[0, 20][[1 ;; -1 ;; 5]], 
      Append[Range[0, 15][[1 ;; -1 ;; 5]], "20 million"]}], None}}]

The primary case to take over a billion steps is 20:718458:0—which results in a 6-cycle after 2,586,944,112 steps:

Show
&#10005
Present[ListStepPlot[
  Transpose[{Range[Length[#]] 1000000/(10^6), #} &[
    ResourceFunction["TagSystemEvolveList"][
     "Post", {0, IntegerDigits[718458, 2, 20]}, 2586944112, 1000000, 
     "Lengths", Methodology -> "BitwiseOptimized"]]], Body -> True, 
  AspectRatio -> 1/3, Filling -> Axis, PlotStyle -> Hue[0.07, 1, 1]], 
 FrameTicks -> {Automated, 
    None, {Thread[{Range[0, 2500][[1 ;; -1 ;; 500]], 
      Append[Range[0, 2000][[1 ;; -1 ;; 500]], "2500 million"]}], 
    None}}]

Right here’s desk of all of the “longest-so-far” winners by means of compressed preliminary length-28 strings (i.e. protecting all  2 × 1025 strange preliminary strings as much as size 84):

Text
&#10005
DecimalStringForm[{n_Integer, {p_Integer, i_Integer}}] := 
 Row[{n, Style[":", Gray], i, 
   Type[Row[{Style[":", Gray], p}], Small]}]

Textual content[Grid[
  Prepend[{DecimalStringForm[{First[#], #[[2, 1]]}], #[[2, 2, 1]], 
      If[# == 0, Style[#, Gray], #] &[#[[2, 2, 2]]]} & /@ {{4, {0, 
        14} -> {419, 0}}, {6, {0, 58} -> {2141, 28}}, {9, {0, 
        506} -> {24552, 6}}, {12, {0, 3962} -> {253456, 6}}, {13, {0, 
        5854} -> {341992, 6}}, {15, {0, 16346} -> {20858069, 
        0}}, {15, {0, 30074} -> {357007576, 6}}, {20, {0, 
        703870} -> {2586944104, 6}}, {22, {0, 3929706} -> {2910925472,
         6}}, {24, {0, 12410874} -> {50048859310, 0}}, {25, {0, 
        33217774} -> {202880696061, 
        6, {0, {0, 1, 1, 1, 0, 0}}}}, {27, {0, 
        125823210} -> {259447574536, 
        6, {0, {0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1}}}}, {28, {2, 
        264107671} -> {643158954877, 
        10, {0, {0, 1, 1, 1, 0, 0, 1, 1, 0, 0}}}}}, 
   Type[#, Italic] & /@ "preliminary state", "steps", "cycle size"], 
  Body -> All, Alignment -> , 
  FrameStyle -> GrayLevel[.7], Background -> {None, {GrayLevel[.9]}}]]

And listed below are their “measurement traces”:

GraphicsGrid
&#10005
GraphicsGrid[
 Partition[
  ResourceFunction["ParallelMapMonitored"][
   Show[ListStepPlot[
      If[#[[1]]  "BitwiseOptimized"]]]]], 
      Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
      PlotStyle -> Hue[0.07, 1, 1]], 
     FrameTicks -> 
      None] &, {{4, {0, 14} -> {419, 0}}, {6, {0, 58} -> {2141, 
       28}}, {9, {0, 506} -> {24552, 6}}, {12, {0, 3962} -> {253456, 
       6}}, {13, {0, 5854} -> {341992, 6}}, {15, {0, 
       16346} -> {20858069, 0}}, {15, {0, 30074} -> {357007576, 
       6}}, {20, {0, 703870} -> {2586944104, 6}}, {22, {0, 
       3929706} -> {2910925472, 6}}, {24, {0, 
       12410874} -> {50048859310, 0}}, {25, {0, 
       33217774} -> {202880696061, 6}}, {27, {0, 
       125823210} -> {259447574536, 6}}, {28, {2, 
       264107671} -> {643158954877, 10}}}], UpTo[3]]]

One notable factor right here—that we’ll come again to—is that after the primary few circumstances, it’s very tough to inform the general scale of those footage. On the primary row, the longest x axis is about 20,000 steps; on the final row it’s about 600 billion.

However most likely probably the most exceptional factor is that we now know that for all (uncompressed) preliminary strings as much as size 75, the system at all times finally evolves to a cycle (or terminates).

Are They Like Random Walks?

Might the sequences of lengths in our tag system be like random walks? Clearly they’ll’t strictly be random walks as a result of given an preliminary string, every complete “stroll” is totally decided, and nothing probabilistic or random is launched.

However what if we take a look at a big assortment of preliminary circumstances? Might the ensemble of noticed walks by some means statistically be like random walks? From the essential development of the tag system we all know that at every step the (uncompressed) string both will increase or decreases in size by one ingredient relying on whether or not its first ingredient is 1 or 0.

But when we simply picked enhance or lower at random listed below are two typical examples of strange random walks we’d get:

(SeedRandom
&#10005
(SeedRandom[#]; 
   ListStepPlot[Accumulate[RandomChoice[{-1, 1}, 2000]], 
    Body -> True, Filling -> Axis, AspectRatio -> 1/3, 
    ImageSize -> 300, PlotStyle -> Hue[0.07, 1, 1]]) & /@ {3442, 3447}

One very apparent distinction from our tag system case is these walks can go beneath 0, whereas within the tag system case as soon as one’s reached one thing at the least near 0 (equivalent to a cycle), the stroll stops. (In a market analogy, the time sequence ends if there’s “chapter” the place the worth hits 0.)

An essential reality about random walks (at the least in a single dimension) is that with probability 1 they always eventually reach any specific worth, like 0. So if our tag system behaved sufficient like a random stroll, we’d have an argument that it should “terminate with likelihood 1” (no matter which may imply given its discrete set of attainable preliminary circumstances).

However how comparable can the sequence generated by a tag system truly be to an strange random stroll? An essential reality is that—past its preliminary situation—any tag system sequence should at all times consist purely of concatenations of the blocks 00 and 1101, or in different phrases, the sequence have to be outlined by a path by means of the finite automaton:

And from this we are able to see that—whereas all 2-grams and 3-grams can happen—the 4-grams 1111,1100, 0101 and 0010 can by no means happen. As well as, if we assume that 0s and 1s happen with equal likelihood initially of the string, then the blocks 00 and 1101 happen with equal likelihood, however the 3-grams 000, 011 happen with double the chances of the others.

On the whole the numbers of attainable m-grams for successive m are 2, 4, 8, 12, 15, 20, 25, 33, 41, … or for all m ≥ 3:

5 + \!\(\*UnderoverscriptBox
&#10005
Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{
    UnderoverscriptBox["\[Sum]", "i", "m"], 
    RowBox[{"Fibonacci", "[", 
     RowBox[{"Ceiling", "[", 
      RowBox[{
       FractionBox["i", "2"], "+", "2"}], "]"}], "]"}]}], " ", "+", 
   " ", "5"}], " ", "=", " ", 
  RowBox[{
   RowBox[{"If", "[", 
    RowBox[{
     RowBox[{"EvenQ", "[", "m", "]"}], ",", " ", 
     RowBox[{"2", " ", 
      RowBox[{"Fibonacci", "[", 
       RowBox[{
        RowBox[{"m", "/", "2"}], " ", "+", " ", "4"}], "]"}]}], ",", 
     " ", 
     RowBox[{"Fibonacci", "[", 
      RowBox[{
       RowBox[{"(", 
        RowBox[{"m", " ", "+", " ", "11"}], ")"}], "/", "2"}], 
      "]"}]}], "]"}], " ", "-", " ", "1"}]}]], "Enter",
 CellChangeTimes->{{3.8238085885516872`*^9, 3.823808588554865*^9}, {
  3.8238090925602207`*^9, 3.823809095107518*^9}},
 CellID->378316299]

Asymptotically that is —implying a limiting set entropy of per ingredient. The relative frequencies of m-grams that seem (aside from 0000…) are at all times of the shape . The next lists for every m the variety of m-grams that seem at given multiplicities (as obtained from Flatten[DeBruijnSequence[{{0,0},{1,1,0,1}},m]]):

(This suggests a “p log p” measure entropy of beneath 0.1.)

So what occurs in precise tag system sequences? As soon as away from the preliminary circumstances, they appear to fairly precisely observe these probabilistic (“mean-field theory”) estimates, although with numerous fluctuations. On the whole, the outcomes are fairly completely different from a pure strange random stroll with each ingredient unbiased, however in settlement with the estimates for a “00, 1101 random stroll”.

One other distinction from an strange random stroll is that our walks finish each time they attain a cycle—and we noticed above that there are an infinite variety of cycles, of progressively better sizes. However the density of such “lure” states is small: amongst all size-n strings, solely maybe of them lie on cycles.

The usual concept of random walks says, nonetheless, that within the restrict of infinitely massive strings and lengthy walks, if there’s certainly a random course of beneath, this stuff is not going to matter: we’ll have one thing that’s in the identical universality class because the strange ±1 random stroll, with the identical large-scale statistical properties.

However what about our tag methods that survive billions of steps earlier than hitting 0? Might real random walks plausibly survive that lengthy? The standard theory of first passage times (or “stopping instances”) tells us that the likelihood for a random stroll beginning at 0 to first attain x (or, equivalently, for a stroll beginning at x to achieve 0) at time t is:

P(t) = (x exp(-(x^2/(2 t))))/Sqrt
&#10005
P(t) = (x exp(-(x^2/(2 t))))/Sqrt[2 \[Pi] t^3]

This exhibits the likelihood of ranging from x and first reaching 0 as a operate of the variety of steps:

Off
&#10005
Off[General::munfl]; Plot[

 Evaluate[Table[
   If[x < 4, Callout, #1 &][(E^(-(x^2/(2 t))) x)/(
    Sqrt[2 \[Pi]] Sqrt[t^3]), x], {x, 5}]], {t, 0, 1000}, 
 ScalingFunctions -> {"Log", "Log"}, AspectRatio -> 1/3, 
 Body -> True, Axes -> False]

The probably stopping time is , however there’s a lengthy tail, and the likelihood of surviving for a time longer than t is:

erf(x/Sqrt
&#10005
erf(x/Sqrt[2 t]) \[TildeTilde] Sqrt[2/(\[Pi] t)] x

How does this probably apply to our methods? Assume we begin from a string of (compressed) size n. This suggests that the likelihood to outlive for t steps (earlier than “reaching x = 0”) is about . However there are 3 × 2n attainable strings of size n. So we are able to roughly estimate that considered one of them may survive for about steps, or at the least plenty of steps that will increase roughly exponentially with n.

And our outcomes for “longest-so-far winners” above do in truth present roughly exponential enhance with n (the dotted line is ):

Show
&#10005
Present[ListPlot[{{4, 419}, {6, 2141}, {9, 24552}, {12, 253456}, {13, 
    341992}, {15, 20858069}, {15, 357007576}, {20, 2586944104}, {22, 
    2910925472}, {24, 50048859310}, {25, 202880696061}}, 
  ScalingFunctions -> "Log", Frame -> True], 
 Plot[4^(.75 n), {n, 1, 25}, ScalingFunctions -> "Log", 
  PlotStyle -> Directive[LightGray, Dotted]]]

We will do a extra detailed comparability with random walks by trying on the full distribution of halting (AKA stopping) instances for tag methods. Listed below are the outcomes for all n = 15 and 25 preliminary strings:

GraphicsRow

Plotting these on a log scale we get

GraphicsRow
&#10005
consequence[15] = 
  CloudImport[
   "https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Data/\
Results-1/15.wxf"];

hist15 = 
  HistogramList[Log10[N[#[[2, 1]]]] & /@ consequence[15], 
   200, "Log", "Depend"];

GraphicsRow[
 ListStepPlot[Transpose[{Most[#1], #2} & @@ #2], Body -> True, 
    Filling -> Axis, ScalingFunctions -> "Log", 
    PlotRange -> {{1, #1}, Automated}, PlotStyle -> Hue[0.07, 1, 1], 
    FrameTicks -> {{None, 
       None}, {Thread[{Range[2, 10, 
          2], {"\!\(\*SuperscriptBox[\(10\), \(2\)]\)", 
          "\!\(\*SuperscriptBox[\(10\), \(4\)]\)", 
          "\!\(\*SuperscriptBox[\(10\), \(6\)]\)", 
          "\!\(\*SuperscriptBox[\(10\), \(8\)]\)",  
          "\!\(\*SuperscriptBox[\(10\), \(10\)]\)"}}], 
       None}}] & @@@ {{5, 
    hist15}, {9, {{
     9/10, 23/25, 47/50, 24/25, 49/50, 1, 51/50, 26/25, 53/50, 27/25, 
      11/10, 28/25, 57/50, 29/25, 59/50, 6/5, 61/50, 31/25, 63/50, 32/
      25, 13/10, 33/25, 67/50, 34/25, 69/50, 7/5, 71/50, 36/25, 73/50,
       37/25, 3/2, 38/25, 77/50, 39/25, 79/50, 8/5, 81/50, 41/25, 83/
      50, 42/25, 17/10, 43/25, 87/50, 44/25, 89/50, 9/5, 91/50, 46/25,
       93/50, 47/25, 19/10, 48/25, 97/50, 49/25, 99/50, 2, 101/50, 51/
      25, 103/50, 52/25, 21/10, 53/25, 107/50, 54/25, 109/50, 11/5, 
      111/50, 56/25, 113/50, 57/25, 23/10, 58/25, 117/50, 59/25, 119/
      50, 12/5, 121/50, 61/25, 123/50, 62/25, 5/2, 63/25, 127/50, 64/
      25, 129/50, 13/5, 131/50, 66/25, 133/50, 67/25, 27/10, 68/25, 
      137/50, 69/25, 139/50, 14/5, 141/50, 71/25, 143/50, 72/25, 29/
      10, 73/25, 147/50, 74/25, 149/50, 3, 151/50, 76/25, 153/50, 77/
      25, 31/10, 78/25, 157/50, 79/25, 159/50, 16/5, 161/50, 81/25, 
      163/50, 82/25, 33/10, 83/25, 167/50, 84/25, 169/50, 17/5, 171/
      50, 86/25, 173/50, 87/25, 7/2, 88/25, 177/50, 89/25, 179/50, 18/
      5, 181/50, 91/25, 183/50, 92/25, 37/10, 93/25, 187/50, 94/25, 
      189/50, 19/5, 191/50, 96/25, 193/50, 97/25, 39/10, 98/25, 197/
      50, 99/25, 199/50, 4, 201/50, 101/25, 203/50, 102/25, 41/10, 
      103/25, 207/50, 104/25, 209/50, 21/5, 211/50, 106/25, 213/50, 
      107/25, 43/10, 108/25, 217/50, 109/25, 219/50, 22/5, 221/50, 
      111/25, 223/50, 112/25, 9/2, 113/25, 227/50, 114/25, 229/50, 23/
      5, 231/50, 116/25, 233/50, 117/25, 47/10, 118/25, 237/50, 119/
      25, 239/50, 24/5, 241/50, 121/25, 243/50, 122/25, 49/10, 123/25,
       247/50, 124/25, 249/50, 5, 251/50, 126/25, 253/50, 127/25, 51/
      10, 128/25, 257/50, 129/25, 259/50, 26/5, 261/50, 131/25, 263/
      50, 132/25, 53/10, 133/25, 267/50, 134/25, 269/50, 27/5, 271/50,
       136/25, 273/50, 137/25, 11/2, 138/25, 277/50, 139/25, 279/50, 
      28/5, 281/50, 141/25, 283/50, 142/25, 57/10, 143/25, 287/50, 
      144/25, 289/50, 29/5, 291/50, 146/25, 293/50, 147/25, 59/10, 
      148/25, 297/50, 149/25, 299/50, 6, 301/50, 151/25, 303/50, 152/
      25, 61/10, 153/25, 307/50, 154/25, 309/50, 31/5, 311/50, 156/25,
       313/50, 157/25, 63/10, 158/25, 317/50, 159/25, 319/50, 32/5, 
      321/50, 161/25, 323/50, 162/25, 13/2, 163/25, 327/50, 164/25, 
      329/50, 33/5, 331/50, 166/25, 333/50, 167/25, 67/10, 168/25, 
      337/50, 169/25, 339/50, 34/5, 341/50, 171/25, 343/50, 172/25, 
      69/10, 173/25, 347/50, 174/25, 349/50, 7, 351/50, 176/25, 353/
      50, 177/25, 71/10, 178/25, 357/50, 179/25, 359/50, 36/5, 361/50,
       181/25, 363/50, 182/25, 73/10, 183/25, 367/50, 184/25, 369/50, 
      37/5, 371/50, 186/25, 373/50, 187/25, 15/2, 188/25, 377/50, 189/
      25, 379/50, 38/5, 381/50, 191/25, 383/50, 192/25, 77/10, 193/25,
       387/50, 194/25, 389/50, 39/5, 391/50, 196/25, 393/50, 197/25, 
      79/10, 198/25, 397/50, 199/25, 399/50, 8, 401/50, 201/25, 403/
      50, 202/25, 81/10, 203/25, 407/50, 204/25, 409/50, 41/5, 411/50,
       206/25, 413/50, 207/25, 83/10, 208/25, 417/50, 209/25, 419/50, 
      42/5, 421/50, 211/25, 423/50, 212/25, 17/2, 213/25, 427/50, 214/
      25, 429/50, 43/5, 431/50, 216/25, 433/50, 217/25, 87/10, 218/25,
       437/50, 219/25, 439/50, 44/5, 441/50, 221/25, 443/50, 222/25, 
      89/10, 223/25, 447/50, 224/25, 449/50, 9, 451/50, 226/25, 453/
      50, 227/25, 91/10, 228/25, 457/50, 229/25, 459/50, 46/5, 461/50,
       231/25, 463/50, 232/25, 93/10, 233/25, 467/50, 234/25, 469/50, 
      47/5, 471/50, 236/25, 473/50, 237/25, 19/2, 238/25, 477/50, 239/
      25, 479/50, 48/5, 481/50, 241/25, 483/50, 242/25, 97/10, 243/25,
       487/50, 244/25, 489/50, 49/5, 491/50, 246/25, 493/50, 247/25, 
      99/10, 248/25, 497/50, 249/25, 499/50, 10, 501/50, 251/25, 503/
      50, 252/25, 101/10, 253/25, 507/50, 254/25, 509/50, 51/5, 511/
      50, 256/25, 513/50, 257/25, 103/10, 258/25, 517/50, 259/25, 519/
      50, 52/5, 521/50, 261/25, 523/50, 262/25, 21/2, 263/25, 527/50, 
      264/25, 529/50, 53/5, 531/50, 266/25, 533/50, 267/25, 107/10, 
      268/25, 537/50, 269/25, 539/50, 54/5, 541/50, 271/25, 543/50, 
      272/25, 109/10, 273/25, 547/50, 274/25, 549/50, 11, 551/50, 276/
      25, 553/50, 277/25, 111/10, 278/25, 557/50, 279/25, 559/50, 56/
      5, 561/50, 281/25, 563/50, 282/25, 113/10, 283/
      25}, CompressedData["
1:eJy1lA9M1VUUxz+/3+893ns8eLwHjz8PQ0IQSERE/mhRSZIbkoBCjAmYoEli
yr/+MCij1Yp0hlRzmYvVzCZOoiFDUsM2/2xRNDbX2qxgZRTFmkZJw0zWeTwI
yIJq82xn53vPPfecc8+554ZsLMsqVQCTCksN/G8KD5jdZlPu3+s/bbpRV7Nv
+vq7wUmcskf5E9fnq3iILN2v8YHcYYM71C3TcT4WzHfpGXpE5JNu3J1g4K2t
CtVXDHS+ZuRCiEpvi4ltI+5cjDRT0KFhHzUzt8qT/Lct7Kjwou6YFa3Cxqmi
AD5aaGVJhJWj7RayVD9GVlloeMyH5DPehP/swaNtPszts+OGnUPXfLi804Yj
w0ZmsC/2Z228UOLLyVgbxa/7M/iSP4nzAjjSEkBJYhBDvg5sNYFkmQI4/oQf
jjw7gf2+LG21US74jbAQIrIdRHTYKWidQ/AhB8832Sh8z8b2TE+CVptxHDST
0+SBbchMaqMHC1oE/24i189A9eNGmqwGFg8YCb9sZt8KMzsq3Xg63sCZAQc1
70Sxck4woSkOBmK9eE4z0RdgJKhfx6VXNKqbVCri3DjRYySpS8fhKCN8pmev
WePooMbnpSpfr9BIeEoj6rRGfafGlVA9frUqKQMKZbUKqWtViqIVfjQoeI/K
8SAdbiUW3vzWnTWvqjTnKVgrTVikn/pl4i9cYXWoQrf07NY6hej3pbdtCpYN
0H1WZbgTrq9SuTRfY1GmRu1v0HhSeuylYItT+GodbI2BvoMKOYIr71RJ74Fr
aQodD8OvF+D0ehjNgOYcUOMhOx+WLwEfPzgufg4sgC+3Qbmc/zBRoTZP7OdD
tEyMPhUiz8F2k4LPYYWuEDhxj9gHwSJ5g01V4icJPjZDifi86gZpVvhlWEdB
FOR6wu5I2Fyl0L5Q8rLLDIbBQ1U6NkncbxYrxEgMPy/IkLyPXdXxiZwZkae/
fjOs84Y7TJAsrUgrBIfE2r8Rzop9sSbrPdAgMRPErqQXvpcZGZJ1lgVWip9z
kmOgc67k/oE6KBS/2emwU2aoWfSSFveLbJW5bhdcL7hyDfSL75dvYWzmtoht
ieydF5wjuXzh/Adk3SicKnF2yf5u4SQ99Eq8taIXNQekJvLExmie6EKdMYXf
lZxvFxkn+lPCRcIXpSaFkl+5YIHcJxwzPvvXbXBEzncJ/kFkmOTlL7YvCt4r
OgnLxE+hjeOJdYOwhGKX8E+yuUVkj861myU88RUmC0ubaBd+RjjR3aV3Wjrz
DFNccYqd9V3u8ukkueJYjZx2Vib1U76xaeSsg/uEYyZjTOTuJP9xee/4nq/w
bX/xUzYu5QlhnKJ/8B/iOik+ehIbp6dwAw1rrjw8p+geUFz3ktKTPsPhNFw9
jJ3B/1TSjUv9FF2bxyTuVpmVZrrLfyVtdpObTv+2djeDnLX8A7Tp63c=
"]}}}]

displaying at the least a tough approximation to the habits anticipated for a random stroll.

In making distributions like these, we’re placing collectively all of the preliminary strings of size n, and asking in regards to the statistical properties of this ensemble. However we are able to additionally think about seeing whether or not preliminary strings with specific properties persistently behave in another way from others. This exhibits the distribution of halting instances as a operate of the variety of 1s within the preliminary string; no robust correlations are seen (right here for n = 20), despite the fact that at the least initially the presence of 1s results in progress:

data20 = Import

Analogies & Expectations

How ought to we take into consideration what we’re seeing? To me it in some ways simply appears a typical manifestation of the ever present phenomenon of computational irreducibility. Loads of methods present what looks like random stroll habits. Even in rule 30, for instance, the dividing line between regularity and randomness seems to follow a (biased) random walk:

data = CloudGet
ListStepPlot

If we modified the preliminary circumstances, we’d get a special random stroll. However in all circumstances, we are able to consider the evolution of rule 30 as intrinsically producing obvious randomness, “seeded” by its preliminary circumstances.

Much more straight analogous to our tag system are mobile automata whose boundaries show apparent randomness. An instance is the k = 2, r = 3/2 rule 7076:

ArrayPlot
&#10005
ArrayPlot[CellularAutomaton[{7076, 2, 3/2}, {{1}, 0}, #], 
   ImageSize -> 300] & /@ {100, 400}
LHEdge

Will this sample go on rising endlessly, or will it will definitely develop into very slim, and both enter a cycle or terminate completely? That is analogous to asking whether or not our tag system will halt.

There are different mobile automata that present much more apparent examples of those sorts of questions. Take into account the ok = 3, r = 1 totalistic code 1329 cellular automaton. Right here is its habits for a sequence of easy preliminary circumstances. In some circumstances the sample dies out (“it halts”); in some circumstances it evolves to a (fairly elaborate) period-78 cycle. And in a single case right here it evolves to a period-7 cycle:

GraphicsRow
&#10005
GraphicsRow[
 Table[ArrayPlot[
   CellularAutomaton[{1329, {3, 1}, 1}, {IntegerDigits[i, 3], 
     0}, {220, {-13, 13}}], 
   ColorRules -> {0 -> White, 1 -> Hue[.03, .9, 1], 
     2 -> Hue[.6, .9, .7]}], {i, 1, 64, 3}]]

However is that this mainly all that may occur? No. Here are the various persistent structures that happen with the primary 10,000 preliminary circumstances—and we see that along with getting strange “cycles”, we additionally get “shift cycles”:

Row
&#10005
Row[ArrayPlot[CellularAutomaton[{1329, {3, 1}, 1}, {#Cells, 0}, 200], 
    ImageSize -> , 
    ColorRules -> {0 -> White, 1 -> Hue[.03, .9, 1], 
      2 -> Hue[.6, .9, .7]}] & /@ 
  Regular[Take[ResourceData["728d1c07-8892-4673-bab3-d889cc6c4623"], 
    7]], Spacer[7]]

But when we go a bit of additional, there’s one other shock: initial condition 54,889 results in a construction that simply retains rising endlessly—whereas initial condition 97,439 additionally does this, however in a way more trivial means:

GraphicsRow
&#10005
GraphicsRow[
 ArrayPlot[
    CellularAutomaton[{1329, {3, 1}, 1}, {IntegerDigits[#, 3], 0}, 
     1000], ColorRules -> {0 -> White, 1 -> Hue[.03, .9, 1], 
      2 -> Hue[.6, .9, .7]}, 
    ImageSize -> ] & /@ {54889, 97439}]

In our tag system, the analog of those may be specific strings that produce patterns that “clearly develop endlessly”.

One may suppose that there could possibly be a basic distinction between a mobile automaton and a tag system. In a mobile automaton the foundations function in parallel, in impact connecting a complete grid of neighboring cells, whereas in a tag system the foundations solely particularly function on the very starting and finish of every string.

However to see a more in-depth analogy we are able to think about each replace within the tag system as an “occasion”, then draw a causal graph that exhibits the relationships between these occasions. Right here is an easy case:

With
&#10005
With[{evol = 
   ResourceFunction["TagSystemEvolveList"]["Post", 
    IntegerDigits[18464, 2, 15], 25]},
 Present[
  ArrayPlot[PadRight[evol, Automatic, .1], Mesh -> True, 
   Body -> False, MeshStyle -> GrayLevel[0.9, 0.9], 
   ColorRules -> {0 -> White, 1 -> GrayLevel[.5]}], 
  Graphics[{Hue[0, 1, 0.56], Opacity[0.2], 
    Rectangle[{0, 1}, {3, Length[evol]}]}],
  MapIndexed[Graphics[{FaceForm[Opacity[0]], EdgeForm[
Hue[0.11, 1, 0.97]], 
      Rectangle[{0, First[Length[evol] - #2 + 1]}, {1, 
        First[Length[evol] - #2]}]}] &, Most[evol]],
  Relaxation[MapIndexed[
    Graphics[{FaceForm[Opacity[0]], 
       EdgeForm[Directive[Thick, Hue[0.11, 1, 0.97]]], 
       Rectangle[If[Quiet[First[First[evol[[#2 - 1]]]] == 0], 
          Size[#1] - 2, Size[#1] - 4], 
         First[Length[evol] - #2 + 1], ]}] &, evol]],
  Module[{quo, rem, src},
   {quo, rem} = 
    Transpose[QuotientRemainder[(Length[#] - 3), 3] & /@ evol];
   MapIndexed[If[First[#1] === 1, 
      Swap[First[rem[[#2]]],
        0, 
       Graphics[{Hue[0, 1, 0.56], Thick, Arrowheads[Small],
         
         If[First[Length[evol] - (#2 + 1) + .5 - quo[[#2]]] > 0, 
          Arrow[{{Length[#1] - 3, 
             First[Length[evol] - (#2 + 1) + 0.5]}, {1, 
             First[Length[evol] - (#2 + 1) + 0.5 - quo[[#2]]]}}], 
          Nothing], 
         
         If[First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]] > 0, 
          Arrow[{{Length[#1] - 3, 
             First[Length[evol] - (#2 + 1) + 0.5]}, {1, 
             First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]]}}], 
          Nothing]}], 
       1 | 2, 
       Graphics[{Hue[0, 1, 0.56], Thick, Arrowheads[Small],
         
         If[First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]] > 0, 
          Arrow[{{Length[#1] - 3, 
             First[Length[evol] - (#2 + 1) + 0.5]}, {1, 
             First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]]}}], 
          Nothing]}]], 
      Swap[First[rem[[#2]]], 
       0,
       If[First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]] > 0, 
        Graphics[{Hue[0, 1, 0.56], Thick, Arrowheads[Small], 
          Arrow[{{Length[#1] - 3, 
             First[Length[evol] - (#2 + 1) + 0.5]}, {1, 
             First[Length[evol] - (#2 + 1) + 0.5 - quo[[#2]]]}}]}], 
        Nothing], 
       1, Nothing, 
       2, Graphics[{Hue[0, 1, 0.56], Thick, Arrowheads[Small],
         
         If[First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]] > 0, 
          Arrow[{{Length[#1] - 3, 
             First[Length[evol] - (#2 + 1) + 0.5]}, {1, 
             First[Length[evol] - (#2 + 1) - 0.5 - quo[[#2]]]}}], 
          Nothing]}]]]
     &, evol]],
  MapIndexed[
   Graphics[{Hue[0, 1, 0.56], Thick, Arrowheads[Small], 
      Arrow[{{1, 
         First[Length[evol] + 0.5 - #2]}, }]}] &, 
   Most[evol]]
  ]]

Extracting the pure causal graph we get:

Graph
&#10005
edges = Catenate[{DirectedEdge[#, # + 1] & /@ Vary[1, 26], 
    With[{evol = 
       ResourceFunction["TagSystemEvolveList"]["Post", 
        IntegerDigits[18464, 2, 15], 25]}, 
     Catenate[MapIndexed[
       If[Length @@ evol[[#2]] >= 3 && (First[#2] + 1  "LayeredDigraphEmbedding", 
 AspectRatio -> 1.4, 
 ResourceFunction["WolframPhysicsProjectStyleData"]["CausalGraph", 
  "Options"]]

For the string 4:14:0 which takes 419 steps to terminate, the causal graph is:

ggg = TagSystemCausalGraph @ With
&#10005
edges = Catenate[{DirectedEdge[#, # + 1] & /@ Vary[1, 419], 
    With[{evol = 
       ResourceFunction["TagSystemEvolveList"]["Post", 
        ResourceFunction["TagSystemConvert"][{0, 
          IntegerDigits[14, 2, 4]}, "PaddingElement" -> 0], 418]}, 
     Catenate[MapIndexed[
       If[Length @@ evol[[#2]] >= 3 && (First[#2] + 1 

Or laid out in another way, and marking growth (11101) and contraction (000) occasions with pink and blue:

Graph
&#10005
edges = Catenate[{DirectedEdge[#, # + 1] & /@ Vary[1, 419], 
    With[{evol = 
       ResourceFunction["TagSystemEvolveList"]["Post", 
        ResourceFunction["TagSystemConvert"][{0, 
          IntegerDigits[14, 2, 4]}, "PaddingElement" -> 0], 418]}, 
     Catenate[MapIndexed[
       If[Length @@ evol[[#2]] >= 3 && (First[#2] + 1  (MapIndexed[First[#2] -> If[# == 1, Red, Blue] &, 
    First /@ 
     ResourceFunction["TagSystemEvolveList"][
      "Post", {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 450]]), 
 VertexSize -> 8, GraphLayout -> "LayeredDigraphEmbedding", 
 AspectRatio -> 1]

Right here is the causal graph for the 2141-step evolution of 6:58:0

ggg = TagSystemCausalGraph @ With
&#10005
edges = Catenate[{DirectedEdge[#, # + 1] & /@ Vary[1, 2141], 
    With[{evol = 
       ResourceFunction["TagSystemEvolveList"]["Post", 
        ResourceFunction["TagSystemConvert"][{0, 
          IntegerDigits[58, 2, 6]}, "PaddingElement" -> 0], 2140]}, 
     Catenate[MapIndexed[
       If[Length @@ evol[[#2]] >= 3 && (First[#2] + 1 

and what’s notable is that regardless of the “spatial localization” of the underlying operation of the tag system, the causal graph in impact connects occasions in one thing nearer to a uniform mesh.

Connecting to Quantity Principle

When Emil Put up was first learning tag methods 100 years in the past he noticed them because the final hurdle to find a scientific option to “remedy all of arithmetic”, and specifically to resolve all issues in quantity concept. After all, they turned out to be a really large hurdle. However having now seen how complicated tag methods may be, it’s attention-grabbing to return and join once more with quantity concept.

It’s simple to transform a tag system into one thing extra clearly quantity theoretical. For instance, if one represents every string of size n by a pair of integers {n,i} during which the binary digits of i give the weather of the string, then every step within the evolution may be obtained from:

TagStep
&#10005
TagStep[{n_, i_}] :=
 
 With[{j = 2^(n - 1) FractionalPart[(8 i)/2^n]}, 
  If[i < 2^(n - 1), {n - 1, j}, {n + 1, 4 j + 13}]]

Ranging from the 4:14:0 preliminary situation (right here represented in uncompressed type by {12, 2336}) the primary few steps are then:

NestList
&#10005
NestList[TagStep, {12, 2336}, 10]

For compressed strings, the corresponding type is:

TagStep
&#10005
TagStep[{n_, i_, p_}] := 
 With[{j = 2^n FractionalPart[i/2^(n - 1)]}, 
  If[i < 2^(
     n - 1), {{n, j, 2}, {n - 1, j/2, 0}, {n, j, 1}}, {{n + 1, 
      2 j + 3, 1}, {n, j, 2}, {n, j + 1, 0}}][[p + 1]]]

There are completely different quantity theoretical formulations one can think about, however a core function is that at every step the tag system is making a alternative between two arithmetic varieties, primarily based on some primarily arithmetic property of the quantity obtained to this point. (Notice that the kind of situation we have now given right here may be additional “compiled” into “pure arithmetic” by extracting it as a solution to a Diophantine equation.)

A extensively studied system just like that is the Collatz or 3n + 1 problem, which generates successive integers by making use of the operate:

n |-> If
&#10005
n |-> If[EvenQ[n], n/2, 3 n + 1]

Beginning, say, from 27, the sequence of numbers obtained is 27, 82, 41, 124, 62, 31, …

ListStepPlot
&#10005
ListStepPlot[
 NestList[n |-> If[EvenQ[n], n/2, 3 n + 1], 27, 120], Heart, 
 Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
 PlotRange -> All, PlotStyle -> Hue[0.07, 1, 1]]

the place after 110 steps the system reaches the cycle 4, 2, 1, 4, 2, 1, …. As a more in-depth analog to the plots for tag methods that we made above we are able to as a substitute plot the lengths of the successive integers, represented in base 2:

ListStepPlot
&#10005
ListStepPlot[
 IntegerLength[#, 2] & /@ 
  NestList[n |-> If[EvenQ[n], n/2, 3 n + 1], 27, 130], Heart, 
 Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
 PlotRange -> All, PlotStyle -> Hue[0.07, 1, 1]]

The state transition graph ranging from integers as much as 10 is

With
&#10005
With[-> If[EvenQ[n], n/2, 3 n + 1], Vary[10], 50],
  HighlightGraph[
  Graph[g, VertexLabels -> Automatic, 
   VertexStyle -> Hue[0.58, 0.65, 1], 
   EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], {Type[
    Subgraph[g, FindCycle[g, {1, Infinity}, All]], Thick, Hue[
    0.02, 0.92, 0.8200000000000001]], 
   Decide[VertexList[g], VertexOutDegree[g], 0]}]]

and as much as 1000 it’s:

With
&#10005
With[-> If[EvenQ[n], n/2, 3 n + 1], Vary[1000], 10000, 
    VertexStyle -> Hue[0.58, 0.65, 1], 
    EdgeStyle -> Hue[0.58, 1, 0.7000000000000001]], 
 HighlightGraph[
  g, {Style[Subgraph[g, FindCycle[g, {1, Infinity}, All]], 
    Thickness[.01], Hue[0.02, 0.92, 0.8200000000000001]], 
   Decide[VertexList[g], VertexOutDegree[g], 0]}]]

Not like for Put up’s tag system, there is just one linked part (and one ultimate cycle), and the “highways” are a lot shorter. For instance, among the many first billion preliminary circumstances, the longest transient is simply 986 steps. It happens for the preliminary integer 670617279—which yields the next sequence of integer lengths:

ListStepPlot
&#10005
ListStepPlot[
 IntegerLength[#, 2] & /@ 
  NestList[n |-> If[EvenQ[n], n/2, 3 n + 1], 670617279, 1100], Heart,
  Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
 PlotRange -> All, PlotStyle -> Hue[0.07, 1, 1]]

Regardless of a good quantity of investigation because the Nineteen Thirties, it’s nonetheless not identified whether or not the threen + 1 downside at all times terminates on its customary cycle—although that is identified to be the case for all integers as much as .

For Put up’s tag system the obvious probabilistic estimate means that the sequence of string lengths ought to observe an unbiased random stroll. For the threen + 1 downside, an analogous evaluation suggests a random stroll with a median bias of binary digits per step, as advised by this assortment of walks from preliminary circumstances + ok:

ListStepPlot
&#10005
ListStepPlot[
 Table[IntegerLength[#, 2] & /@ 
   NestList[n |-> If[EvenQ[n], n/2, 3 n + 1], 10^8 + i, 200], {i, 0, 
   40}], Heart, Body -> True, AspectRatio -> 1/3, PlotRange -> All]

The rule (discussed in A New Kind of Science)

n |-> If
&#10005
n |-> If[EvenQ[n], n/2, 5 n + 1]

as a substitute implies a bias of +0.11 digits per step, and certainly most preliminary circumstances result in progress:

Function
&#10005
Operate[{i}, 
  ListStepPlot[
   IntegerLength[#, 2] & /@ 
    NestList[n |-> If[EvenQ[n], n/2, 5 n + 1], i, 200], Heart, 
   Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
   PlotRange -> All, Epilog -> Inset[i, Scaled[{.1, .8}]], 
   PlotStyle -> Hue[0.07, 1, 1]]] /@ {7, 37}

However there are nonetheless some that—despite the fact that they develop for some time—have “fluctuations” that trigger them to “crash” and find yourself in cycles:

Function
&#10005
Operate[{i}, 
  ListStepPlot[
   IntegerLength[#, 2] & /@ 
    NestList[n |-> If[EvenQ[n], n/2, 5 n + 1], i, 100], Heart, 
   Body -> True, AspectRatio -> .45, Filling -> Axis, 
   PlotRange -> All, Epilog -> Inset[i, Scaled[{.9, .8}]], 
   PlotStyle -> Hue[0.07, 1, 1]]] /@ {181, 613, 9818}

What’s the “most unbiased” a n + b system? If we think about mod 3 as a substitute of mod 2, we have now methods like:

n |-> \!\(\*SubscriptBox
&#10005
n |-> 
\!\(\*SubscriptBox[\({n, 
\*SubscriptBox[\(a\), \(1\)] n + 
\*SubscriptBox[\(b\), \(1\)], 
\*SubscriptBox[\(a\), \(2\)] n + 
\*SubscriptBox[\(b\), \(2\)]}\), \(\([\)\(\([\)\(Mod[n, 3] + 
    1\)\(]\)\)\(]\)\)]\)/3

We want to be divisible by 3 when n = i mod 3. In our approximation, the bias will probably be . That is closest to zero (with worth +0.05) when ai are 4 and seven. An instance of a attainable iteration is then:

n |-> 
\!\(\*SubscriptBox
&#10005
n |-> 
\!\(\*SubscriptBox[\({n, 4  n + 2, 
    7  n + 1}\), \(\([\)\(\([\)\(Mod[n, 3] + 1\)\(]\)\)\(]\)\)]\)/3

Ranging from a sequence of preliminary circumstances this clearly exhibits much less bias than the threen + 1 case:

ListStepPlot
&#10005
ListStepPlot[Table[IntegerLength[#, 2] & /@ NestList[n |-> 
\!\(\*SubscriptBox[\({n, 4  n + 2, 
        7  n + 1}\), \(\([\)\(\([\)\(Mod[n, 3] + 1\)\(]\)\)\(]\)\)]\)/
      3, 10^8 + i, 100], {i, 0, 40}], Heart, Body -> True, 
 AspectRatio -> 1/3, PlotRange -> All]

Listed below are the halting instances for preliminary circumstances as much as 1000:

ListStepPlot
&#10005
ListStepPlot[
 Transpose[
  ParallelTable[Length /@ FindTransientRepeat[NestList[n |-> 
\!\(\*SubscriptBox[\({n, 4  n + 2, 
          7  n + 1}\), \(\([\)\(\([\)\(Mod[n, 3] + 
          1\)\(]\)\)\(]\)\)]\)/3, i, 5000], 3], {i, 1000}]], Heart, 
 PlotRange -> {0, 4000}, PlotLayout -> "Stacked", Joined -> True, 
 Filling -> Automated, Body -> True, AspectRatio -> 1/4, 
 PlotStyle -> Hue[0.1, 1, 1]]

Most preliminary circumstances rapidly evolve to cycles of size 5 or 20. However preliminary situation 101 takes 2604 steps to achieve the 20-cycle:

Function
&#10005
Operate[{i}, ListStepPlot[IntegerLength[#, 2] & /@ NestList[n |-> 
\!\(\*SubscriptBox[\({n, 4  n + 2, 
         7  n + 1}\), \(\([\)\(\([\)\(Mod[n, 3] + 
         1\)\(]\)\)\(]\)\)]\)/3, i, 3000], Heart, Body -> True, 
   AspectRatio -> 1/3, Filling -> Axis, PlotRange -> All, 
   Epilog -> Inset[i, Scaled[{.06, .9}]], 
   PlotStyle -> Hue[0.07, 1, 1]]] /@ {101, 469}

And preliminary situation 469 doesn’t seem to achieve a cycle in any respect—and as a substitute seems to systematically develop at about 0.018 bits per step:

ListStepPlot
&#10005
ListStepPlot[
 MapIndexed[{1 + (First[#2] - 1)*1000, #} &, (IntegerLength[#, 2] & /@
     NestList[Nest[n |-> 
\!\(\*SubscriptBox[\({n, 4  n + 2, 
           7  n + 1}\), \(\([\)\(\([\)\(Mod[n, 3] + 
           1\)\(]\)\)\(]\)\)]\)/3, #, 1000] &, 469, 1000])], Heart, 
 Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
 PlotRange -> All, PlotStyle -> Hue[0.07, 1, 1]]

In different phrases, in contrast to the threen + 1 downside—or our tag system—this iteration often results in a cycle, however simply typically seems to “escape” and proceed to extend, presumably endlessly.

(On the whole, for modulus m, the minimal bias will sometimes be , and the “smoothest” iterations will probably be ones whose multipliers contain similar-sized components of numbers near . For m = 4, for instance, {n, 3n – 3, 5n – 2, 17n + 1} is the very best.)

One may surprise how comparable our tag system—or the threen + 1 problem—is to basic unsolved issues in quantity concept, just like the Riemann Hypothesis. In essence the Riemann Speculation is an assertion in regards to the statistical randomness of primes, usually said when it comes to complicated zeroes of the Riemann zeta operate, or equivalently, that every one the maxima of RiemannSiegelZ[t] (for any worth of t) lie above the axis:

Plot
&#10005
Plot[RiemannSiegelZ[t], {t, 0, 400}, Body -> True, 
 AspectRatio -> 1/6, PlotPoints -> 500, PlotStyle -> Hue[0.07, 1, 1]]

Nevertheless it’s identified (due to extensive work by Yuri Matiyasevich) that an equal—rather more clearly integer-related—assertion is that

(2 n + 3)!!/15 - (2 n - 2)!! PrimePi
&#10005
(2 n + 3)!!/15 - (2 n - 2)!! PrimePi[
   n]^2 ((BitLength[Fold[LCM, Range[n]]] - 1) \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(ok = 1\), \(n - 1\)]\(
\*SuperscriptBox[\((\(-1\))\), \(k + 1\)] 
\*SuperscriptBox[\(k\), \(-1\)]\)\) - n)

is constructive for all constructive n. And this then seems to be equal to the surprisingly easy assertion that the iteration

NestWhile
&#10005
NestWhile[x |-> {2 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(1\)\(\
\[RightDoubleBracket]\)\)]\) - 4 (-1)^x[[2]] 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(5\)\(\
\[RightDoubleBracket]\)\)]\), 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 1, (
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 1) 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(3\)\(\
\[RightDoubleBracket]\)\)]\)/GCD[
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 1, 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(3\)\(\
\[RightDoubleBracket]\)\)]\)], If[GCD[
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 1, 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(3\)\(\
\[RightDoubleBracket]\)\)]\)] == 1, 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(4\)\(\
\[RightDoubleBracket]\)\)]\) + 1, 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(4\)\(\
\[RightDoubleBracket]\)\)]\)], 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(6\)\(\
\[RightDoubleBracket]\)\)]\), (2 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 2) 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(6\)\(\
\[RightDoubleBracket]\)\)]\), (2 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(2\)\(\
\[RightDoubleBracket]\)\)]\) + 5) 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(7\)\(\
\[RightDoubleBracket]\)\)]\)}, {1, 1, 1, 0, 0, 1, 1}, x |-> 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(7\)\(\
\[RightDoubleBracket]\)\)]\) > 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(4\)\(\
\[RightDoubleBracket]\)\)]\)^2 (
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(1\)\(\
\[RightDoubleBracket]\)\)]\) (BitLength[
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(3\)\(\
\[RightDoubleBracket]\)\)]\)] - 1) - 
\!\(\*SubscriptBox[\(x\), \(\(\[LeftDoubleBracket]\)\(6\)\(\
\[RightDoubleBracket]\)\)]\))]

won’t ever terminate.

For successive n the amount above is given by:

Table
&#10005
Desk[(2 n + 3)!!/
  15 - (2 n - 2)!! PrimePi[
    n]^2 ((BitLength[Fold[LCM, Range[n]]] - 1) \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(ok = 1\), \(n - 1\)]\(
\*SuperscriptBox[\((\(-1\))\), \(k + 1\)] 
\*SuperscriptBox[\(k\), \(-1\)]\)\) - n), {n, 10}]

A minimum of initially the numbers are undoubtedly constructive, because the Riemann Speculation would counsel. But when we ask in regards to the long-term habits we are able to see one thing of the complexity concerned by trying on the variations in successive ratios:

GraphicsRow
&#10005
GraphicsRow[
 ListStepPlot[
    Differences[
     Ratios[Table[(2 n + 3)!!/
        15 - (2 n - 2)!! PrimePi[
          n]^2 ((BitLength[Fold[LCM, Range[n]]] - 1) \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(ok = 1\), \(n - 1\)]\(
\*SuperscriptBox[\((\(-1\))\), \(k + 1\)] 
\*SuperscriptBox[\(k\), \(-1\)]\)\) - n), {n, #}]]], Body -> True, 
    PlotStyle -> Hue[0.07, 1, 1], AspectRatio -> 1/3] & /@ {100, 
   1000}]

The Riemann Speculation successfully says that there aren’t too many destructive variations right here.

Different Tag Methods

To date we’ve been speaking particularly about Emil Put up’s specific 00, 1101 tag system. However as Put up himself noticed, one can outline loads of different tag methods—together with ones that contain not simply 0 and 1 however any variety of attainable components (Put up referred to as the variety of attainable components μ, however I’ll name it ok), and delete not simply 3 however any variety of components at every step (Put up referred to as this ν, however I’ll name it r).

It’s simple to see that guidelines which delete just one ingredient at every step (r = 1) can’t contain actual “communication” (or causal connections) between completely different elements of the string, and have to be equal to neighbor-independent substitution systems—in order that they both have trivial habits, or develop with out certain to provide at most extremely common nested sequences. (001, 110 will generate the Thue–Morse string, whereas 001, 10 will generate the Fibonacci string.)

Issues instantly get extra sophisticated when two components are deleted at every step (r = 2). Put up accurately noticed that with simply 0 and 1 (ok = 2) there are not any guidelines that present the sort of sometimes-expanding, sometimes-contracting habits of his 00, 1101 rule. However again in 2007—as part of a live experiment at our annual Summer School—I seemed on the r = 2 rule 01, 1110. Right here’s what it does beginning with 10:

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
      s___} :> {s, 1, 1, 0}}, {1, 0}, 25], Automated, .25], 
 Mesh -> True, MeshStyle -> GrayLevel[0.75, 0.75]]

And right here’s how the sequence of string lengths behaves:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
     s___} :> {s, 1, 1, 0}}, {1, 0}, 60, 1, "Lengths"], Heart, 
 AspectRatio -> 1/3, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

If we assume that 0 and 1 seem randomly with sure chances, then a easy calculation exhibits that 1 ought to happen about instances as usually as 0, and the string ought to develop a median of components at every step. So “detrending” by this, we get:

ListStepPlot
&#10005
ListStepPlot[
 MapIndexed[# - (Sqrt[2] - 1) First[#2] &, 
  ResourceFunction[
    "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
      s___} :> {s, 1, 1, 0}}, {1, 0}, 300, 1, "Lengths"]], Heart, 
 AspectRatio -> 1/4, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

Persevering with for extra steps we see an in depth approximation to a random stroll:

ListStepPlot
&#10005
ListStepPlot[
 MapIndexed[# - (Sqrt[2] - 1) First[#2] &, 
  ResourceFunction[
    "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
      s___} :> {s, 1, 1, 0}}, {1, 0}, 10000, 1, "Lengths", 
   Method -> "BitwiseOptimized"]], Heart, AspectRatio -> 1/4, 
 Filling -> Axis, Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

So similar to with Put up’s 00, 1101 rule—and, after all, with rule 30 and all types of different methods within the computational universe—we have now right here a very deterministic system that generates what looks like randomness. And certainly amongst tag methods of the kind we’re discussing right here this seems to be the very easiest rule that exhibits this type of habits.

However does this rule present the identical sort of progress from all preliminary circumstances? It will possibly present completely different random sequences, for instance right here for preliminary circumstances 5:17 and seven:80:

ListStepPlot
&#10005
ListStepPlot[
   MapIndexed[# - (Sqrt[2] - 1) First[#2] &, 
    ResourceFunction[
      "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
        s___} :> {s, 1, 1, 0}}, #, 300, 1, "Lengths"]], Heart, 
   AspectRatio -> 1/4, Filling -> Axis, Body -> True, 
   PlotStyle -> Hue[0.07, 1, 1]] & /@ {IntegerDigits[17, 2, 5], 
  IntegerDigits[80, 2, 7]}

And typically it simply instantly enters a cycle. Nevertheless it has some “surprises” too. Like with preliminary situation 9:511 (i.e. 111111111) it grows not linearly, however like (proven right here with none detrending):

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
     s___} :> {s, 1, 1, 0}}, {1, 1, 1, 1, 1, 1, 1, 1, 1}, 150, 1, 
  "Lengths"], Heart, AspectRatio -> 1/4, Filling -> Axis, 
 Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

However what a couple of tag system that doesn’t appear to “sometimes develop endlessly”? Once I was engaged on A New Kind of Science I studied generalized tag systems that don’t just look at their first elements, however as a substitute use the entire block of components they’re deleting to find out what components so as to add on the finish (and so work in a considerably extra “cellular-automaton-style” means).

One specific rule that I confirmed in A New Form of Science (as case (c) on page 94) is:

Text
&#10005
CloudGet["https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Programs-01.wl"];
						Textual content[Map[Row, {{0, 0} -> {0}, {1, 0} -> {1, 0, 1}, {0, 1} -> {0, 0, 
     0}, {1, 1} -> {0, 1, 1}}, {2}]]

Beginning with 11 this rule offers

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{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, 1}, 25], Automated, .25], 
 Mesh -> True, MeshStyle -> GrayLevel[0.75, 0.75]]

and grows for some time—however then terminates after 289 steps:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{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, 1}, 300, 1, "Lengths"], Heart, 
 AspectRatio -> 1/4, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1], PlotRange -> Full]

The corresponding generational evolution is:

ArrayPlot
&#10005
ArrayPlot[
 [email protected]
  Transpose[
   PadRight[
    NestList[
     Last[
       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}}, #, 
        Quotient[Length[#], 2]]] &, {1, 1}, 35], , .25]], Mesh -> True, MeshStyle -> GrayLevel[.75, .75], 
 Body -> False]

(Notice that the sort of “part decomposition” that we did for Put up’s tag system doesn’t make sense for a block tag system like this.)

Listed below are the lengths of the transients+cycles for attainable preliminary circumstances as much as measurement 7:

With
&#10005
With[{list = Catenate[Table[Tuples[{0, 1}, n], {n, 7}]]}, 
 ListStepPlot[
  Transpose[((Length /@ 
        FindTransientRepeat[
         ResourceFunction[
           "TagSystemEvolveList"][{{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}}, #, 1000], 4]) & /@ checklist)], 
  Heart, 
  PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
  PlotRange -> {0, 800}, PlotLayout -> "Stacked", Joined -> True, 
  Filling -> Automated, Body -> True, AspectRatio -> 1/5, 
  FrameTicks -> {, {Extract[
      MapThread[
       List[#1, 
         Rotate[
          Style[StringJoin[ToString /@ #2], FontFamily -> "Roboto", 
           Small], 90 Diploma]] &, Vary[0, 253], checklist], 
      Place[list, 
       Alternatives @@ 
        Select[list, 
         IntegerExponent[FromDigits[#, 2], 2] > Size[#]/2 && 
           Size[#] > 1 &]]], None}}]]

This appears to be like extra irregular—and “livelier”—than the corresponding plot for Put up’s tag system, however not essentially completely different. At measurement 5 the preliminary string 11010 (denoted 5:12) yields

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{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, 1, 0, 1, 0}, 800, 1, 
  "Lengths"], Heart, AspectRatio -> 1/4, Filling -> Axis, 
 Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

which terminates after 706 steps in a length-8 cycle. Going additional one sees a sequence of progressively longer transients:

Text
&#10005
Textual content[Grid[
  Prepend[{Row[{#[[1, 1]], ":", #[[1, 2]]}], #[[2, 1]], #[[2, 
       2]]} & /@ {{2, 3} -> {288, 1}, {5, 12} -> {700, 8}, {6, 
       62} -> {4184, 1}, {8, 175} -> {20183, 8}, {9, 345} -> {26766, 
       1}, {9, 484} -> {51680, 8}, {10, 716} -> {100285, 1}, {10, 
       879} -> {13697828, 8}, {13, 7620} -> {7575189088, 1}, {17, 
       85721} -> {14361319032, 8}}, 
   Type[#, Italic] & /@ "preliminary state", "steps", "cycle size"], 
  Body -> All, Alignment -> , 
  FrameStyle -> GrayLevel[.7], Background -> {None, {GrayLevel[.9]}}]]
xevollist

However like with Put up’s tag system, the system at all times finally reaches a cycle (or terminates)—at the least for all preliminary strings as much as measurement 17. However what is going to occur for the longest preliminary strings is just not clear, and the better “liveliness” of this method relative to Put up’s means that if unique habits happens, it’s going to probably accomplish that for smaller preliminary strings than in Put up’s system.

One other option to generalize Put up’s 00, 1101 tag system is to think about not simply components 0, 1, however, say, 0, 1, 2 (i.e. ok = 3). And on this case there’s already complicated habits even with guidelines that think about simply the primary ingredient, and delete two components at every step (r = 2).

For instance, think about the rule:

#1 -> Row
&#10005
CloudGet["https://www.wolframcloud.com/obj/sw-blog/PostTagSystem/Programs-01.wl"];
						#1 -> Row[#2] & @@@ 
 Thread[Range[0, 2] -> TakeList[IntegerDigits[76, 3, 6], {1, 2, 3}]]

Beginning, say, with 101 this provides

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
      s___} :> {s, 0, 2}, {2, _, s___} :> {s, 2, 1, 1}}, 
   IntegerDigits[10, 3, 3], 20], Automated, .25], Mesh -> True, 
 MeshStyle -> GrayLevel[.85, .75], 
 ColorRules -> {0 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], -1 -> GrayLevel[.85]}]

which terminates after 74 steps:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
     s___} :> {s, 0, 2}, {2, _, s___} :> {s, 2, 1, 1}}, 
  IntegerDigits[10, 3, 3], 250, 1, "Lengths"], Heart, 
 AspectRatio -> 1/4, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

Listed below are the lengths of transients+cycles for this rule as much as length-6 preliminary (ternary) strings:

With
&#10005
With[{list = 
   Catenate[
    Table[IntegerDigits[i, 3, n],  {n, 1, 6}, {i, 0, 3^n - 1}]]}, 
 ListStepPlot[
  Transpose[
   Last /@ 
    Monitor[
     Flatten[
      Table[
       ParallelTable[{n, i} -> 
         Length /@ 
          FindTransientRepeat[
           ResourceFunction[
             "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
               s___} :> {s, 0, 2}, {2, _, s___} :> {s, 2, 1, 1}}, 
            IntegerDigits[i, 3, n], 1000, 1, "Lengths"], 10], {i, 0, 
         3^n - 1}], {n, 6}]], n]], Heart, PlotRange -> {0, 125}, 
  PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
  PlotLayout -> "Stacked", Joined -> True, Filling -> Automated, 
  Body -> True, AspectRatio -> 1/5, 
  FrameTicks -> {, {Extract[
      MapThread[
       List[#1, 
         Rotate[
          Style[StringJoin[ToString /@ #2], FontFamily -> "Roboto", 
           Small], 90 Diploma]] &, ], 
      Place[list, 
       Alternatives @@ 
        Select[list, 
         IntegerExponent[FromDigits[#, 3], 3] > Size[#]/2 && 
           Size[#] =!= 3 && Size[#] > 1 &]]], None}}]]

The preliminary string 202020 (denoted 6:546, the place now this means ternary fairly than binary) terminates after 6627 steps

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
     s___} :> {s, 0, 2}, {2, _, s___} :> {s, 2, 1, 1}}, 
  IntegerDigits[546, 3, 6], 10000, 1, "Lengths"], Heart, 
 AspectRatio -> 1/4, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

with (phase-reduced) generational evolution:

ArrayPlot
&#10005
ArrayPlot[
 [email protected]
  Transpose[
   PadRight[
    Last[ResourceFunction["TagSystemConvert"][#, 2]] & /@ 
     NestList[
      Last[
        ResourceFunction[
          "TagSystemEvolve"][{{0, _, s___} :> {s, 0}, {1, _, 
            s___} :> {s, 0, 2}, {2, _, s___} :> {s, 2, 1, 1}}, #, 
         Quotient[Length[#], 2]]] &, IntegerDigits[546, 3, 6], 
      180], , .25]], Body -> False, 
 ColorRules -> {0 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], -1 -> GrayLevel[.85]}]

And as soon as once more, the general options of the habits are similar to Put up’s system, with the longest halting instances seen as much as strings of size 14 being:

Text
&#10005
DecimalStringForm[{n_Integer, {p_Integer, i_Integer}}] := 
 Row[{n, Style[":", Gray], i, 
   Type[Row[{Style[":", Gray], p}], Small]}]

Textual content[Grid[
  Prepend[{DecimalStringForm[{#[[1, 1]], #[[1, 2]]}], #[[2, 1]], 
      If[# == 0, Style[#, Gray], #] &@#[[2, 2]]} & /@ {{3, {0, 
        10}} -> {74, 0}, {5, {0, 91}} -> {122, 
       0}, {6, {0, 546}} -> {6627, 0}, {9, {0, 499}} -> {9353, 
       0}, {9, {0, 610}} -> {12789, 0}, {9, {0, 713}} -> {20175, 
       0}, {9, {0, 1214}} -> {175192, 0}, {9, {0, 18787}} -> {336653, 
       0}, {10, {0, 17861}} -> {519447, 
       0}, {10, {0, 29524}} -> {21612756, 
       6}, {10, {0, 52294}} -> {85446023, 
       0}, {11, {0, 93756}} -> {377756468, 
       6}, {12, {0, 412474}} -> {30528772851, 0}}, 
   Type[#, Italic] & /@ "preliminary state", "steps", "cycle size"], 
  Body -> All, Alignment -> , 
  FrameStyle -> GrayLevel[.7], Background -> {None, {GrayLevel[.9]}}]]

However what about different attainable guidelines? For instance, we are able to take a look at all 90 attainable ok = 3, r = 2 guidelines of the shape 0_, 1__, 2___ during which the right-hand sides are “balanced” within the sense that in complete all of them comprise two 0s, 1s and 2s. This exhibits the evolution (for 100 steps) for every of those guidelines that has the longest transient for any preliminary string with lower than 7 components:

GraphicsGrid
&#10005
GraphicsGrid[
 Partition[
  ParallelMap[
   ListStepPlot[
     ResourceFunction[
       "TagSystemEvolveList"][{{0, _, s___} :> {s, 
           Splice[#[[1]]]}, {1, _, s___} :> {s, 
           Splice[#[[2]]]}, {2, _, s___} :> {s, Splice[#[[3]]]}} &[
       TakeList[IntegerDigits[#[[1]], 3, 6], {1, 2, 3}]], 
      IntegerDigits[#[[2, 2]], 3, #[[2, 1]]], 100, 1, "Lengths"], 
     Heart, PlotRange -> {{0, 100}, Automated}, AspectRatio -> 1/3, 
     Filling -> Axis, Body -> True, FrameTicks -> False, 
     PlotStyle -> Hue[0.07, 1, 1]] &, {44 -> {5, 182}, 50 -> {6, 492},
     52 -> {3, 20}, 68 -> {2, 6}, 70 -> {5, 19}, 76 -> {6, 546}, 
    98 -> {3, 20}, 104 -> {3, 2}, 106 -> {5, 182}, 116 -> {5, 182}, 
    128 -> {6, 492}, 132 -> {5, 182}, 140 -> {6, 540}, 
    142 -> {5, 181}, 146 -> {4, 60}, 150 -> {5, 163}, 154 -> {3, 10}, 
    156 -> {5, 100}, 176 -> {6, 270}, 178 -> {6, 540}, 
    184 -> {6, 270}, 194 -> {5, 173}, 196 -> {6, 57}, 200 -> {5, 182},
     204 -> {6, 543}, 208 -> {5, 173}, 210 -> {6, 486}, 
    220 -> {5, 91}, 226 -> {5, 100}, 228 -> {5, 91}, 260 -> {5, 182}, 
    266 -> {6, 492}, 268 -> {5, 182}, 278 -> {5, 182}, 
    290 -> {6, 492}, 294 -> {5, 164}, 302 -> {6, 519}, 304 -> {6, 30},
     308 -> {6, 492}, 312 -> {6, 489}, 316 -> {6, 546}, 
    318 -> {6, 546}, 332 -> {6, 540}, 344 -> {6, 492}, 
    348 -> {5, 182}, 380 -> {6, 519}, 384 -> {6, 270}, 
    396 -> {6, 276}, 410 -> {5, 101}, 412 -> {6, 543}, 
    416 -> {6, 543}, 420 -> {6, 57}, 424 -> {6, 489}, 426 -> {5, 164},
     434 -> {6, 273}, 438 -> {6, 513}, 450 -> {6, 543}, 
    460 -> {6, 516}, 462 -> {5, 99}, 468 -> {6, 30}, 500 -> {6, 546}, 
    502 -> {5, 181}, 508 -> {6, 6}, 518 -> {5, 99}, 520 -> {6, 516}, 
    524 -> {6, 543}, 528 -> {5, 99}, 532 -> {3, 9}, 534 -> {6, 546}, 
    544 -> {5, 181}, 550 -> {6, 519}, 552 -> {5, 181}, 
    572 -> {6, 540}, 574 -> {5, 181}, 578 -> {3, 10}, 582 -> {5, 172},
     586 -> {6, 546}, 588 -> {6, 513}, 596 -> {5, 180}, 
    600 -> {5, 18}, 612 -> {6, 546}, 622 -> {6, 519}, 624 -> {6, 513},
     630 -> {6, 519}, 652 -> {6, 270}, 658 -> {5, 19}, 
    660 -> {6, 540}, 676 -> {6, 57}, 678 -> {6, 297}, 
    684 -> {6, 30}}], 6]]

Many lead rapidly to cycles or termination. Others after 100 steps appear to be rising irregularly, however all the particular evolutions proven right here finally halt. There are peculiar circumstances, like 00, 102, 2112 which exactly repeats the preliminary string 20 after 18,255 steps:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 
       Splice[#[[1]]]}, {1, _, s___} :> {s, Splice[#[[2]]]}, {2, _, 
       s___} :> {s, Splice[#[[3]]]}} &[
   TakeList[IntegerDigits[68, 3, 6], {1, 2, 3}]], 
  IntegerDigits[6, 3, 2], 40000, 1, "Lengths"], Heart, 
 AspectRatio -> 1/5, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

After which there are circumstances like 00, 101, 2212, say ranging from 200020, which both halt rapidly, or generate strings of ever-increasing size (right here like ) and may simply be seen by no means to halt:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 
       Splice[#[[1]]]}, {1, _, s___} :> {s, Splice[#[[2]]]}, {2, _, 
       s___} :> {s, Splice[#[[3]]]}} &[
   TakeList[IntegerDigits[50, 3, 6], {1, 2, 3}]], 
  IntegerDigits[492, 3, 6], 100, 1, "Lengths"], Heart, 
 AspectRatio -> 1/3, Filling -> Axis, Body -> True, 
 PlotStyle -> Hue[0.07, 1, 1]]

(By the way in which, the state of affairs with “non-balanced” ok = 3 guidelines is just not essentially completely different from balanced ones; 00, 122, 2102, for instance, exhibits very “Put up-like” habits.)

The tag methods we’ve been discussing are fairly easy. However a fair less complicated model considered in A New Kind of Science are what I called cyclic tag systems. In a cyclic tag system one removes the primary ingredient of the string at every step. On successive steps, one cycles by means of a set of attainable blocks so as to add, including one if the deleted ingredient was a 1 (and in any other case including nothing).

If the attainable blocks so as to add are 111 and 0, then the habits ranging from the string 1 is as follows

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction["CyclicTagSystemEvolveList"][{{1, 1, 1}, {0}}, {1},
    25], Automated, 18, .25], Mesh -> True, 
 MeshStyle -> GrayLevel[0.75, 0.75]]

with the lengths “detrended by t/2” behaving as soon as once more like an approximate random stroll:

ListStepPlot
&#10005
ListStepPlot[
 MapIndexed[# - First[#2]/2 &, 
  Size /@ 
   ResourceFunction[
     "CyclicTagSystemEvolveList"][{{1, 1, 1}, {0}}, {1}, 
    20000]], Heart, AspectRatio -> 1/4, Filling -> Axis, 
 Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

With cycles of simply 2 blocks, one sometimes sees both fast biking or termination, or what looks like apparent infinite progress. But when one permits a cycle of three blocks, extra sophisticated halting habits turns into attainable.

Take into account for instance 01, 0, 011. Ranging from 0111 one will get

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "CyclicTagSystemEvolveList"][{{0, 1}, {0}, {0, 1, 1}}, {0, 1, 1, 
    1}, 20], , .25], Mesh -> True, 
 MeshStyle -> GrayLevel[0.75, 0.75]]

with the system halting after 169 steps:

ListStepPlot
&#10005
ListStepPlot[
 Length /@ 
  ResourceFunction[
    "CyclicTagSystemEvolveList"][{{0, 1}, {0}, {0, 1, 1}}, {0, 1, 1, 
    1}, 200], Heart, AspectRatio -> 1/4, Filling -> Axis, 
 Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

Listed below are the transient+cycle instances for preliminary strings as much as measurement 8 (the system often simply terminates, however for instance 001111 goes right into a cycle of size 18):

With
&#10005
With[{list = 
   Catenate[
    Table[IntegerDigits[i, 2, n],  {n, 1, 8}, {i, 0, 2^n - 1}]]}, 
 ListStepPlot[
  Transpose[
   Last /@ 
    Monitor[
     Flatten[
      Table[
       ParallelTable[{n, i} -> 
         Length /@ 
          FindTransientRepeat[
           Length /@ 
            ResourceFunction[
              "CyclicTagSystemEvolveList"][{{0, 1}, {0}, {0, 1, 1}}, 
             IntegerDigits[i, 2, n], 800], 3], {i, 0, 2^n - 1}], {n, 
        8}]], n]], Heart, PlotRange -> {0, 500}, 
  PlotStyle -> {Hue[0.1, 1, 1], Hue[0.02, 0.92, 0.8200000000000001]}, 
  PlotLayout -> "Stacked", Joined -> True, Filling -> Automated, 
  Body -> True, AspectRatio -> 1/5, 
  FrameTicks -> {, {Extract[
      MapThread[
       List[#1, 
         Rotate[
          Style[StringJoin[ToString /@ #2], FontFamily -> "Roboto", 
           Small], 90 Diploma]] &, Vary[0, 509], checklist], 
      Place[list, 
       Alternatives @@ 
        Select[list, 
         IntegerExponent[FromDigits[#, 2], 2] > Size[#]/1.5 && 
           Size[#] > 2 &]]], None}}]]

The habits of the longest-to-halt-so-far “winners” are once more just like what we have now seen before—except maybe for the fairly enormous soar in halting time at size 13—that isn’t surpassed till measurement 16:

Text
&#10005
ctevollist[{n_, i_} -> len_] := 
 ListStepPlot[
  Length /@ 
   ResourceFunction[
     "CyclicTagSystemEvolveList"][{{0, 1}, {0}, {0, 1, 1}}, 
    IntegerDigits[i, 2, n], Ceiling[(len*1.05)]], Body -> True, 
  AspectRatio -> 1/3, Filling -> Axis, Ticks -> None, 
  FrameTicks -> None, MaxPlotPoints -> 1000, 
  PlotStyle -> Hue[0.07, 1, 1]]

GraphicsGrid[
 Partition[
  Append[
   ctevollist /@ {{1, 1} -> 59, {4, 7} -> 170, {5, 21} -> 
      1259, {7, 126} -> 6470, {10, 687} -> 134318}, 
   ListStepPlot[CompressedData["
1:eJytl4d/z1cXxz9Hqio1G7MiqC32amxBCGLEiC1CYjW1a+8IosjyaFEREVSs
xowQpRr1pA2pIiLakloh9qgRPO+88i88v9frvu793XvuuZ/zOeee+z1VRk7s
M8EkeX0gzSouTXeSmnwqudAqNJK+pflUkLrWYt5TWjFQyuknteks3aG9aC3N
c5dutpdC+kphXpJrgJQwmL3IRg2VvOlH+EvJU6ShgVLpsZL/cOlxf+lRb+ll
Rym8jzRytDTsCymAfv84qRNyGWM4A31/jZdi2HtgkLRqADroi3FeezBM6yCt
ZX96OykRjOGdpF3d6Zsz11Ty44x1HlI8mPrQXLylCHBu8ZXcwRAFtjK92IPe
IHQW8JPOIOdF/xFznTg/aJIUO1Equ1SaMV/qFgrOydLluXDGXFCEVC8au+Kk
RbQKiVLnw9L1rVI1xrnfS5GMK+6T5sZLt49ImfR1DsLlT9KDX6R9/0jbbkrr
r0tHGb96JZ1/JjnRnpY2JdLmlzNlljCN/9R02MWUW9fkXNPUuqLJg7UP6L1q
mZq4mnY7m6wZ4+am19VNs+n9PEw5DU13Wpp82LehgelGbVMke2agy7+y6WgZ
00DOalDJdI75Nex9V8p0qpppRAXTIv4XaWyq39qU9LnpNP9LoNOtpGkxcgEF
TDXAEsN+L+a8WQ9hfSzn/Aqe6Eacg95lyBzDlsrIRX5mugbmiuASOAe7m54g
m1DVNIC93eqYkpl73NHUa4jpYE/Tc2xxb2HKYk9UP2QGmwoNMKWxPqq/6RX9
VOaL9jI5dDHdBW94U1OfJpyJ7mD2eWNTQ2yuxBnZ4AplLcPNFFHe1PkT02U4
vg/uqFZgZT69PfbWAye6hnia/kbHWXRv7It/OO+8j6n8cNOYUcjTNo4EY3c4
6cpZyDmA+xt01aB91w7+O8AFWJLRd6K36b23KQy9ceC/jX2z25hKIpsBJ5mM
p3UzecLDWGRKovMlMv9l/ynwNwRLa8YHapiawe8OWt36ppXYXIj5RPYEsX8g
+GLAWn+MaRDt5AhwDYMfWij4q/uaHrD+HEwRnN0QjM/Yt5PzfeGyJFh6cl5Z
/DqSGNrKeQvxw+/MpTB3DD7ncmYP8DQhTm7CX2M4Gwa/r5FzgMOWtEB8eRRc
bdFflzgajv5zcLydcV32+KO7A/HkWAxO3pOkiKsAYjqYuDnP2I1zLhCz14mb
ZWDoTOz7Mj7E+skipkb4sA06Eomd4/BQEAwxJfL1PULmN7AlYuMd/PK4h6lT
Z+IF/jNoveHKY6hpCi0bP0YTW33hbfQM07bpYJ1MrM8k/meZnGZj8yrThGhT
se2mWVtMV3bgu02mjmGmPUH4NhDfwLUH+9InmXaxtzT71pJ9g2jr5pvuTTPF
Ml8CmctTwTaWOB8NR/hiFmc362M6A/8B8HYXzM7EVgzYctnz8QpTUzBMDeYe
rTTVCzUt/wa9G+GU+RH8Lw2ON19hB+eWn4vOBfhoHrH0NVwhd+o709PV3AX2
3Vlrmvw98RZrKoddVelH78XXUcTMItNHtOHsHYb9LcC6EZwJ4NlALP3xhWnL
HNNM9DqgZxP6UpYwD47Qb01zwBi2nFwFhotwmfMl/LB+jrmS6I2DsxObyTOc
+3Cd6UvWshabXrC+D3x30ZPIma3wRRr9ygDim9YnTxf/9yMbCodnwBENphb+
plJwXxUfvAfnO2RbjMvnoCC6NizEj4xrLDPdol+JXavAcQkd/9J7M7dzIvcM
7nIZO4E/E/t+DDH1oy+D3Gx854j+AD9ia5DJdTx5A78OwrZ69DfAVZDWAD+/
BN8PtGj89BZbixAna7ahdycxjQ9qY/PRDSYX5vdEmn5hPGgN95LWDD/UZi4a
f/rC72MwNQOvAzirMW6Mzd7EqjNxW4nYOEy7RbzFg/kVPB4OhyfOHMB5E4nR
z5PgI4P/17k3v/NepJm+P46ff8a2/cQVcpXXk3M5dzE+cdxFbsWnrnDVgpYE
jrbEnvBNBH0Ma6/At/o/+IT/W4mxxXDvAy+h9PHw0hOuRuArN+KiYYTpT/Zk
4od+4Ou2lNyAP7bh52x074EjQ/Yq/Ncizocg+xi7i7Lux/8CnHsF2+dwPwLJ
wXHk/9rk/CzyrD93pB135j7tw7w7Q76dx51/SR7ayfu5lPzoTX6YSg7pSt5K
5x1KKkuuIHf5kpMe8BYEkNNu8wbsJr/caJT//uxmLYfc25dc6QKuZ5y/Ai4+
Ar8D/tuO3+bjww7kgerYWA4ubmPLAbAOgn834uYRsj7sO0I8hOObdsg5wJUL
d/QaHGRzr6bhz1vE1h186kIu8MDG6dj1gFbTCx3k0Pu8LZN4A7Ly3kewPsS+
szQPbP8Ae93Ie5HMZ2HrZfLf9Ir5c/7Y04C5FW3JW7wnAei5xZ4kdBdGXwbv
T0VyYDlieTPjweSgvmDwoneC583IBtJcOxFHnDODN+EZerPR15P82Y37NQ5/
VwLzZ+Qsf+6h4ft7+PJoXo4jJoOJg2g4uIvdmxiHcFfi2FeSfgmx4wk3PVmf
Am/HidlX8FgT/yfg+yw4fkGunUJMdo3hHc67N9yTIDhfwF53+C0Df47cvTrs
dSGO1nPnyhM7qYw7cG8/IX8MpHdhvh6cv5uXP3eQ8+Lw15yt5EDugmsC8bIP
/OS/y9yFveC4QMvFZ6mc0559LdGzihhvx70rwzvqRT8W7rLhKpf50tzJf4kX
D974YrwzgcRkD+5mK2RrkZNi8fFj7B5DLCwBXyPuUBdi5SFxlYP+EXDxBJmZ
7Nk8kLjKy7XovjI8n+vB6PDh3XYbkz+fjB+iiI9b+LIGsXoKXw7ED2mcnUob
kvfu4a+nvNHx+G48720cb2tY3vebY/633zvuRATvaUvipCtvbSxzLfgu3MV9
CWdvgSrkae6GMe6PzG7e7e7ovUkM9eYejsPWotjtABe9sDOD8RPs9oOHH4mj
VYy3suaDDY5g/J09l4ipe8T2e2yoStytRW45dlXFbk9sDiGXD0FPGvsi4LUc
sXaAb5Nt6J/HOJV4XMf9vIiObOZDwHYDvG/4jtmLrelgTuMbdgd2Xuc7twfj
n7jzw4rzvn2I3c+l8k+la3x/z7lLe8g4R0q5KtXPoEb4Uzr7l3QauVbM13kg
LaSfgdw/j6Q1xllPpKv3pC73pc3o+Yfv+QN/SCdohc5Q8xxljjpg0i5qgUPU
DGnoZj7psuSAfA/OOXRNOv63NIH/S6kPKp/js/is1PEUmKglCp2kRmI9E1yj
wNSZuuEI/53ZN5+557nSSr6BCn9sqvCGM17w+cT/bOb7gmsncleRi78geWRS
l3F2AvNvwDr1tlTzopSdKk2m/4W535A/yDmnwdY8ndqK//vuSNHsWwAfBRl/
zhkXC5GfihL/cOsPtxX51urE/8kFwZLNnkvUhehzgOMseBpPjTMW3lKof4ph
31fY+tsxqTptwc/UfDRfOJq1Q6q0RnpLnbV3C7aHw90G7N5IXRqFzV9T59GW
rqBuW4QN06Re1GfBc6RP6UfOli4sluqGSL9Sr6Wvlzb9gD3HqeMS8CVnJ6dQ
f9I3PS39wVx/arRA1t/Qz4T31cn4CHzu56Xu2LEMWS/2JDLnCcZgZOv8il+Z
L0v/+gT1GxweoxVhT1F49iMu/iJmst8SE9jdhbgpTJwVh7tRxNFT1kvdwjfU
fG+Jx1TaEfhLgkcnYrQN8TDuBvUj/i6MzqXw5o0PvTgvHiyj4esL8DQjvpKp
P1334iN4ctqGvXDluZZYog49CWcz+L+dWnU/4zD6M9hZGjsCiMtx+yVHdKQw
XwrOq8B3NHVvVrAUF8s5YdwFeA5cKKUGUSfDa9tVcLcaOyPZMx2ME5ibhT/h
XQvw11TsxR8TZlJTU8uXoL6uOpwamRrchfGLUfBKvX1jKDHGOJZaPpKafp07
XDJ2pqZ/PUxagvzHyKX049yu0u5u3NHGxIiL9GcxcNaQ7rtiQznpUhmpYVnu
V2H933//A+pa9mk=
"], Body -> True, AspectRatio -> 1/3, 
    Filling -> Axis, Ticks -> None, FrameTicks -> None, 
    MaxPlotPoints -> 1000, PlotStyle -> Hue[0.07, 1, 1]]], UpTo[3]]]
&#10005
ctevollist[{n_, i_} -> len_] := 
 ListStepPlot[
  Length /@ 
   ResourceFunction[
     "CyclicTagSystemEvolveList"][{{0, 1}, {0}, {0, 1, 1}}, 
    IntegerDigits[i, 2, n], Ceiling[(len*1.05)]], Body -> True, 
  AspectRatio -> 1/3, Filling -> Axis, Ticks -> None, 
  FrameTicks -> None, MaxPlotPoints -> 1000, 
  PlotStyle -> Hue[0.07, 1, 1]]

GraphicsGrid[
 Partition[
  Append[
   ctevollist /@ {{1, 1} -> 59, {4, 7} -> 170, {5, 21} -> 
      1259, {7, 126} -> 6470, {10, 687} -> 134318}, 
   ListStepPlot[CompressedData["
1:eJytl4d/z1cXxz9Hqio1G7MiqC32amxBCGLEiC1CYjW1a+8IosjyaFEREVSs
xowQpRr1pA2pIiLakloh9qgRPO+88i88v9frvu793XvuuZ/zOeee+z1VRk7s
M8EkeX0gzSouTXeSmnwqudAqNJK+pflUkLrWYt5TWjFQyuknteks3aG9aC3N
c5dutpdC+kphXpJrgJQwmL3IRg2VvOlH+EvJU6ShgVLpsZL/cOlxf+lRb+ll
Rym8jzRytDTsCymAfv84qRNyGWM4A31/jZdi2HtgkLRqADroi3FeezBM6yCt
ZX96OykRjOGdpF3d6Zsz11Ty44x1HlI8mPrQXLylCHBu8ZXcwRAFtjK92IPe
IHQW8JPOIOdF/xFznTg/aJIUO1Equ1SaMV/qFgrOydLluXDGXFCEVC8au+Kk
RbQKiVLnw9L1rVI1xrnfS5GMK+6T5sZLt49ImfR1DsLlT9KDX6R9/0jbbkrr
r0tHGb96JZ1/JjnRnpY2JdLmlzNlljCN/9R02MWUW9fkXNPUuqLJg7UP6L1q
mZq4mnY7m6wZ4+am19VNs+n9PEw5DU13Wpp82LehgelGbVMke2agy7+y6WgZ
00DOalDJdI75Nex9V8p0qpppRAXTIv4XaWyq39qU9LnpNP9LoNOtpGkxcgEF
TDXAEsN+L+a8WQ9hfSzn/Aqe6Eacg95lyBzDlsrIRX5mugbmiuASOAe7m54g
m1DVNIC93eqYkpl73NHUa4jpYE/Tc2xxb2HKYk9UP2QGmwoNMKWxPqq/6RX9
VOaL9jI5dDHdBW94U1OfJpyJ7mD2eWNTQ2yuxBnZ4AplLcPNFFHe1PkT02U4
vg/uqFZgZT69PfbWAye6hnia/kbHWXRv7It/OO+8j6n8cNOYUcjTNo4EY3c4
6cpZyDmA+xt01aB91w7+O8AFWJLRd6K36b23KQy9ceC/jX2z25hKIpsBJ5mM
p3UzecLDWGRKovMlMv9l/ynwNwRLa8YHapiawe8OWt36ppXYXIj5RPYEsX8g
+GLAWn+MaRDt5AhwDYMfWij4q/uaHrD+HEwRnN0QjM/Yt5PzfeGyJFh6cl5Z
/DqSGNrKeQvxw+/MpTB3DD7ncmYP8DQhTm7CX2M4Gwa/r5FzgMOWtEB8eRRc
bdFflzgajv5zcLydcV32+KO7A/HkWAxO3pOkiKsAYjqYuDnP2I1zLhCz14mb
ZWDoTOz7Mj7E+skipkb4sA06Eomd4/BQEAwxJfL1PULmN7AlYuMd/PK4h6lT
Z+IF/jNoveHKY6hpCi0bP0YTW33hbfQM07bpYJ1MrM8k/meZnGZj8yrThGhT
se2mWVtMV3bgu02mjmGmPUH4NhDfwLUH+9InmXaxtzT71pJ9g2jr5pvuTTPF
Ml8CmctTwTaWOB8NR/hiFmc362M6A/8B8HYXzM7EVgzYctnz8QpTUzBMDeYe
rTTVCzUt/wa9G+GU+RH8Lw2ON19hB+eWn4vOBfhoHrH0NVwhd+o709PV3AX2
3Vlrmvw98RZrKoddVelH78XXUcTMItNHtOHsHYb9LcC6EZwJ4NlALP3xhWnL
HNNM9DqgZxP6UpYwD47Qb01zwBi2nFwFhotwmfMl/LB+jrmS6I2DsxObyTOc
+3Cd6UvWshabXrC+D3x30ZPIma3wRRr9ygDim9YnTxf/9yMbCodnwBENphb+
plJwXxUfvAfnO2RbjMvnoCC6NizEj4xrLDPdol+JXavAcQkd/9J7M7dzIvcM
7nIZO4E/E/t+DDH1oy+D3Gx854j+AD9ia5DJdTx5A78OwrZ69DfAVZDWAD+/
BN8PtGj89BZbixAna7ahdycxjQ9qY/PRDSYX5vdEmn5hPGgN95LWDD/UZi4a
f/rC72MwNQOvAzirMW6Mzd7EqjNxW4nYOEy7RbzFg/kVPB4OhyfOHMB5E4nR
z5PgI4P/17k3v/NepJm+P46ff8a2/cQVcpXXk3M5dzE+cdxFbsWnrnDVgpYE
jrbEnvBNBH0Ma6/At/o/+IT/W4mxxXDvAy+h9PHw0hOuRuArN+KiYYTpT/Zk
4od+4Ou2lNyAP7bh52x074EjQ/Yq/Ncizocg+xi7i7Lux/8CnHsF2+dwPwLJ
wXHk/9rk/CzyrD93pB135j7tw7w7Q76dx51/SR7ayfu5lPzoTX6YSg7pSt5K
5x1KKkuuIHf5kpMe8BYEkNNu8wbsJr/caJT//uxmLYfc25dc6QKuZ5y/Ai4+
Ar8D/tuO3+bjww7kgerYWA4ubmPLAbAOgn834uYRsj7sO0I8hOObdsg5wJUL
d/QaHGRzr6bhz1vE1h186kIu8MDG6dj1gFbTCx3k0Pu8LZN4A7Ly3kewPsS+
szQPbP8Ae93Ie5HMZ2HrZfLf9Ir5c/7Y04C5FW3JW7wnAei5xZ4kdBdGXwbv
T0VyYDlieTPjweSgvmDwoneC583IBtJcOxFHnDODN+EZerPR15P82Y37NQ5/
VwLzZ+Qsf+6h4ft7+PJoXo4jJoOJg2g4uIvdmxiHcFfi2FeSfgmx4wk3PVmf
Am/HidlX8FgT/yfg+yw4fkGunUJMdo3hHc67N9yTIDhfwF53+C0Df47cvTrs
dSGO1nPnyhM7qYw7cG8/IX8MpHdhvh6cv5uXP3eQ8+Lw15yt5EDugmsC8bIP
/OS/y9yFveC4QMvFZ6mc0559LdGzihhvx70rwzvqRT8W7rLhKpf50tzJf4kX
D974YrwzgcRkD+5mK2RrkZNi8fFj7B5DLCwBXyPuUBdi5SFxlYP+EXDxBJmZ
7Nk8kLjKy7XovjI8n+vB6PDh3XYbkz+fjB+iiI9b+LIGsXoKXw7ED2mcnUob
kvfu4a+nvNHx+G48720cb2tY3vebY/633zvuRATvaUvipCtvbSxzLfgu3MV9
CWdvgSrkae6GMe6PzG7e7e7ovUkM9eYejsPWotjtABe9sDOD8RPs9oOHH4mj
VYy3suaDDY5g/J09l4ipe8T2e2yoStytRW45dlXFbk9sDiGXD0FPGvsi4LUc
sXaAb5Nt6J/HOJV4XMf9vIiObOZDwHYDvG/4jtmLrelgTuMbdgd2Xuc7twfj
n7jzw4rzvn2I3c+l8k+la3x/z7lLe8g4R0q5KtXPoEb4Uzr7l3QauVbM13kg
LaSfgdw/j6Q1xllPpKv3pC73pc3o+Yfv+QN/SCdohc5Q8xxljjpg0i5qgUPU
DGnoZj7psuSAfA/OOXRNOv63NIH/S6kPKp/js/is1PEUmKglCp2kRmI9E1yj
wNSZuuEI/53ZN5+557nSSr6BCn9sqvCGM17w+cT/bOb7gmsncleRi78geWRS
l3F2AvNvwDr1tlTzopSdKk2m/4W535A/yDmnwdY8ndqK//vuSNHsWwAfBRl/
zhkXC5GfihL/cOsPtxX51urE/8kFwZLNnkvUhehzgOMseBpPjTMW3lKof4ph
31fY+tsxqTptwc/UfDRfOJq1Q6q0RnpLnbV3C7aHw90G7N5IXRqFzV9T59GW
rqBuW4QN06Re1GfBc6RP6UfOli4sluqGSL9Sr6Wvlzb9gD3HqeMS8CVnJ6dQ
f9I3PS39wVx/arRA1t/Qz4T31cn4CHzu56Xu2LEMWS/2JDLnCcZgZOv8il+Z
L0v/+gT1GxweoxVhT1F49iMu/iJmst8SE9jdhbgpTJwVh7tRxNFT1kvdwjfU
fG+Jx1TaEfhLgkcnYrQN8TDuBvUj/i6MzqXw5o0PvTgvHiyj4esL8DQjvpKp
P1334iN4ctqGvXDluZZYog49CWcz+L+dWnU/4zD6M9hZGjsCiMtx+yVHdKQw
XwrOq8B3NHVvVrAUF8s5YdwFeA5cKKUGUSfDa9tVcLcaOyPZMx2ME5ibhT/h
XQvw11TsxR8TZlJTU8uXoL6uOpwamRrchfGLUfBKvX1jKDHGOJZaPpKafp07
XDJ2pqZ/PUxagvzHyKX049yu0u5u3NHGxIiL9GcxcNaQ7rtiQznpUhmpYVnu
V2H933//A+pa9mk=
"], Body -> True, AspectRatio -> 1/3, 
    Filling -> Axis, Ticks -> None, FrameTicks -> None, 
    MaxPlotPoints -> 1000, PlotStyle -> Hue[0.07, 1, 1]]], UpTo[3]]]

What Can It Compute?

When Put up initially invented tag methods in 1920 he meant them as a string-based idealization of the operations in mathematical proofs. However a decade and a half later, as soon as Turing machines have been identified, it began to be clear that tag methods have been higher framed as being computational methods. And by the Nineteen Forties it was identified that at the least in precept string-rewriting methods of the sort Put up used have been able to doing precisely the identical varieties of computations as Turing machines—or, as we’d say now, that they have been computation universal.

At first what was proved was {that a} pretty basic string-rewriting system was computation common. However by the early Sixties it was identified {that a} tag system that looks only at its first element is also universal. And actually it’s not too tough to write a “compiler” that takes any Turing machine rule and converts it to a tag system rule—and page 670 of A New Form of Science is dedicated to displaying a pictorial instance of how this works:

Emulating a Turing machine with a tag system

For instance we are able to take the simplest universal Turing machine (which has 2 states and three colours) and compile it right into a 2-element-deletion tag system with 32 attainable components (those above 9 represented by letters) and guidelines:

alt

However what a couple of tag system like Put up’s 00, 1101 one—with a lot less complicated guidelines? Might it even be common?

Our sensible expertise with computer systems may make us suppose that to get universality we’d essentially need to have a system with sophisticated guidelines. However the shocking conclusion advised by the Principle of Computational Equivalence is that this isn’t appropriate—and that as a substitute primarily any system whose habits is just not clearly easy will truly be able to common computation.

For any specific system it’s often extraordinarily tough to show this. However we now have a number of examples that appear to validate the Precept of Computational Equivalence—specifically the rule 110 cellular automaton and the 2,3 Turing machine. And this leads us to the conjecture that even tag methods with quite simple guidelines (at the least ones whose total habits is just not clearly easy) also needs to be computation common.

How can we get proof for this? We’d think about that we may see a specific tag system “scanning over” a variety of computations as we alter its preliminary circumstances. After all, computation universality simply says that it have to be attainable to assemble an preliminary situation that performs any given computation. And it could possibly be that to carry out any decently subtle computation would require an immensely complicated preliminary situation, that will by no means be “discovered naturally” by scanning over attainable preliminary circumstances.

However the Precept of Computational Equivalence truly goes additional than simply saying that every one types of methods can in precept do subtle computations; it says that such computations must be fairly ubiquitous amongst attainable preliminary circumstances. There could also be some particular preliminary circumstances that result in easy habits. However different preliminary circumstances ought to produce habits that corresponds to a computation that’s in a way as subtle as some other computation.

And a consequence of that is that the habits we see will sometimes be computationally irreducible: that normally there will probably be no option to compute its end result rather more effectively than simply by following every of its steps. Or, in different phrases, once we observe the system, we can have no option to computationally scale back it—and so its habits will appear to us complicated.

So once we discover habits in tag methods that appears to us complicated—and that we don’t seem in a position to analyze or predict—the expectation is that it should correspond to a classy computation, and be an indication that the tag system follows the Precept of Computational Equivalence and is computation common.

However what precise computations do specific tag methods do? Clearly they do the computations which are outlined by their guidelines. However the query is whether or not we are able to by some means additionally interpret the general computations they do when it comes to acquainted ideas, say in arithmetic or pc science.

Take into account for instance the 2-element-deletion tag system with guidelines 1111. Beginning it off with 11 we get

alt
&#10005
Column[Row /@ 
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 1, 1, 1}}, {1, 1}, 5]]

and we are able to see that the tag in impact simply “counts up in unary”. (The 1-element-deletion rule 111 does the identical factor.)

Now think about the tag system with guidelines:

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2, 2}, 2 -> {1, 1, 1, 1}}

Beginning it with 11 we get

Column
&#10005
Column[Row /@ 
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 2}, {2, _, 
      s___} :> {s, 1, 1, 1, 1}}, {1, 1}, 8]]

or extra pictorially (pink is 1, blue is 2):

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 2}, {2, _, 
      s___} :> {s, 1, 1, 1, 1}}, {1, 1}, 34], Automated], 
 Mesh -> True, MeshStyle -> GrayLevel[.75, .75], 
 ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}]

However now take a look at steps the place strings of solely 1s seem. The variety of 1s in these strings varieties the sequence

Total /@ Cases
&#10005
Complete /@ 
 Circumstances[ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 2}, {2, _, 
      s___} :> {s, 1, 1, 1, 1}}, {1, 1}, 1000], {1 ...}]

of successive powers of two. (The 1-element-deletion rule 12, 211 offers the identical sequence.)

The rule

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2, 2}, 2 -> {1, 1, 1}}

ranging from 11 yields as a substitute

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 2}, {2, _, 
      s___} :> {s, 1, 1, 1}}, {1, 1}, 80], Automated], 
 MeshStyle -> GrayLevel[.75, .75], Body -> False, 
 ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}]

and now the lengths of the sequences of 1s type the sequence:

Total /@ Cases
&#10005
Complete /@ 
 Circumstances[ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 2}, {2, _, 
      s___} :> {s, 1, 1, 1}}, {1, 1}, 10000], {1 ...}]

This sequence is just not as acquainted as powers of two, nevertheless it nonetheless has a reasonably conventional “mathematical interpretation”: it’s the results of iterating

n |-> Ceiling
&#10005
n |-> Ceiling[(3 n)/2]

or

n |-> If
&#10005
n |-> If[EvenQ[n], (3 n)/2, (3 n + 1)/2 ]

(and this similar iteration applies for any preliminary string of 1s of any size).

However think about now the rule:

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {1, 2}, 2 -> {1, 1, 1}}

Here’s what it does beginning with sequences of 1s of various lengths:

Row
&#10005
Row[Table[
  ArrayPlot[
   PadRight[
    ResourceFunction[
      "TagSystemEvolveList"][{{1, _, s___} :> {s, 1, 2}, {2, _, 
        s___} :> {s, 1, 1, 1}}, Table[1, k], 100]], 
   ImageSize -> , 
   ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
     2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}], ok, 2, 20], 
 Spacer[2]]

In impact it’s taking the preliminary variety of 1s n and computing the operate:

ListStepPlot
&#10005
ListStepPlot[
 ParallelTable[
  Last[Total /@ 
    Cases[
     ResourceFunction[
       "TagSystemEvolveList"][{{1, _, s___} :> {s, 1, 2}, {2, _, 
         s___} :> {s, 1, 1, 1}}, Table[1, k], 100000], {1 ...}]], ], Heart, Filling -> Axis, Body -> True, PlotRange -> All,
  AspectRatio -> 1/3, PlotStyle -> Hue[0.07, 1, 1]]

However what “is” this operate? In impact it will depend on the binary digits of n, and seems to be given (for n > 1) by:

With
&#10005
With[{e = IntegerExponent[n + 1, 2]}, (3^e (n + 1))/2^e - 1]

What different “identifiable features” can easy tag methods produce? Take into account the foundations:

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2, 3}, 2 -> {1}, 3 -> {1, 1, 1}}

Beginning with a string of 5 1s this provides (3 is white)

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 3}, {2, _, 
      s___} :> {s, 1}, {3, _, s___} :> {s, 1, 1, 1}}, Table[1, 5], 
   100], {22, 10}], Mesh -> True, 
 ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}, 
 MeshStyle -> GrayLevel[0.85, 0.75]]

in impact working for 21 steps after which terminating. If one appears to be like on the string of 1s produced right here, their sequence of lengths is 5, 8, 4, 2, 1, and normally the sequence is set by the iteration

n |-> If
&#10005
n |-> If[EvenQ[n], n/2, 3 n + 1 ]

besides that if n reaches 1 the tag system terminates, whereas the iteration retains going.

So if we ask what this tag system is “doing”, we are able to say it’s computing 3n + 1 downside iterations, and we are able to explicitly “see it doing the computation”. Right here it’s beginning with n = 7

ArrayPlot
&#10005
ArrayPlot[
 PadRight[
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 3}, {2, _, 
      s___} :> {s, 1}, {3, _, s___} :> {s, 1, 1, 1}}, Table[1, 7], 
   200]], Body -> False, 
 ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
   2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}]

and right here it’s beginning with successive values of n:

Row
&#10005
Row[Table[
  ArrayPlot[
   PadRight[
    ResourceFunction[
      "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 3}, {2, _, 
        s___} :> {s, 1}, {3, _, s___} :> {s, 1, 1, 1}}, Table[1, k], 
     150], ], ImageSize -> Automated, 160, 
   Body -> False, 
   ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
     2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}], ], 
 Spacer[2]]

Does the tag system at all times finally halt? That is precisely the 3n + 1 problem—which has been unsolved for the higher a part of a century.

It might sound exceptional that even such a easy tag system rule can in impact give us such a tough mathematical downside. However the Precept of Computational Equivalence makes this appear a lot much less shocking—and actually it tells us that we must always count on tag methods to rapidly “ascend out of” the vary of computations to which we are able to readily assign conventional mathematical interpretations.

Altering the rule to

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2, 3}, 2 -> {1, 1, 1}, 3 -> {1}}

yields as a substitute the iteration

Row
&#10005
Row[Table[
  ArrayPlot[
   PadRight[
    ResourceFunction[
      "TagSystemEvolveList"][{{1, _, s___} :> {s, 2, 3}, {2, _, 
        s___} :> {s, 1, 1, 1}, {3, _, s___} :> {s, 1}}, Table[1, k], 
     150], ], ImageSize -> Automated, 160, 
   Body -> False, 
   ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
     2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}], ], 
 Spacer[2]]

which once more is “interpretable” as equivalent to the iteration:

n |-> If
&#10005
n |-> If[EvenQ[n], 3 n/2, (n - 1)/2]

However what if we think about all attainable guidelines, say with the quite simple type 1__, 2___? Here’s what every of the 32 of those does ranging from 1111:

alt
&#10005
Column[{Row[Take[#, 20], Spacer[1]], 
    Row[Take[#, {21, 26}], Spacer[1]], 
    Row[Take[#, -6], Spacer[1]]}] &[
 ArrayPlot[
    PadRight[
     ResourceFunction[
       "TagSystemEvolveList"][{{1, _, s___} :> {s, 
         Splice[#[[1]]]}, {2, _, s___} :> {s, Splice[#[[2]]]}}, {1, 
       1, 1, 1}, 40]], ImageSize -> , Body -> False, 
    ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
      2 -> Hue[.7, .8, .5], 
      0 -> GrayLevel[.85]}] & /@ (TakeList[#, {2, 3}] & /@ 
    Tuples[{1, 2}, 5])]

For a few of these we’ve been in a position to establish “conventional mathematical interpretations”, however for a lot of we have now not. And if we go even additional and take a look at the very easiest nontrivial guidelines—of the shape 1_, 2___—here’s what occurs ranging from a string of 10 1s:

Row
&#10005
Row[ArrayPlot[
    PadRight[
     ResourceFunction[
       "TagSystemEvolveList"][{{1, _, s___} :> {s, 
         Splice[#[[1]]]}, {2, _, s___} :> {s, Splice[#[[2]]]}}, 
      Desk[1, 10], 40], ], 
    ImageSize -> , Body -> False, 
    ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
      2 -> Hue[.7, .8, .5], 
      0 -> GrayLevel[.85]}] & /@ (TakeList[#, {1, 3}] & /@ 
    Tuples[{1, 2}, 4]), Spacer[1]]

One in every of these guidelines we already mentioned above

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2}, 2 -> {2, 2, 1}}

and we discovered that it appears to result in infinite irregular progress (right here proven “detrended” by ):

ListStepPlot
&#10005
ListStepPlot[
 MapIndexed[# - (Sqrt[2] - 1) First[#2] &, 
  ResourceFunction[
    "TagSystemEvolveList"][{{1, _, s___} :> {s, 2}, {2, _, 
      s___} :> {s, 2, 2, 1}}, Table[1, 10], 10000, 1, 
   "Lengths"]], Heart, AspectRatio -> 1/4, Filling -> Axis, 
 Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

However even within the case of

First
&#10005
First[#] -> Row[Last[#]] & /@ {1 -> {2}, 2 -> {1, 1, 1}}

which seems at all times to halt

Row
&#10005
Row[Table[
  ArrayPlot[
   PadRight[
    ResourceFunction[
      "TagSystemEvolveList"][{{1, _, s___} :> {s, 2}, {2, _, 
        s___} :> {s, 1, 1, 1}}, Table[1, k], 40], ], 
   ImageSize -> , Body -> False, 
   ColorRules -> {3 -> White, 1 -> Hue[.03, .9, 1], 
     2 -> Hue[.7, .8, .5], 0 -> GrayLevel[.85]}], ], Spacer[1]]

the variations between halting instances with successive sizes of preliminary strings type a surprisingly complicated sequence

ListStepPlot
&#10005
ListStepPlot[
 Differences[
  First /@ 
   Table[
    Length /@ 
     FindTransientRepeat[
      ResourceFunction[
        "TagSystemEvolveList"][{{1, _, s___} :> {s, 2}, {2, _, 
          s___} :> {s, 1, 1, 1}}, Table[1, k], 600], 3], ok, 
     150]], Heart, PlotRange -> {0, 21}, AspectRatio -> 1/5, 
 Filling -> Axis, Body -> True, PlotStyle -> Hue[0.07, 1, 1]]

that doesn’t appear to have any easy conventional mathematical interpretation. (By the way in which, in a case like this it’s completely attainable that there will probably be some sort of “mathematical interpretation”—although it may be just like the page of weird definitions that I found for halting times of Turing machine 600720 in A New Form of Science.)

So Does It At all times Halt?

When Emil Put up was learning his tag system again in 1921, considered one of his large questions was: “Does it at all times halt?” Frustratingly sufficient, I need to report that even a century later I nonetheless haven’t been in a position to reply this query.

Operating Put up’s tag system on my pc I’m in a position to work out what it does billions of instances quicker than Put up may. And I’ve been in a position to take a look at billions of attainable preliminary strings. And I’ve discovered that it may well take a really very long time—like half a trillion steps—for the system to halt:

Show
&#10005
Present[ListStepPlot[
  Transpose[{Range[Length[#]] 100000000/1000000, #} &[
    ResourceFunction["TagSystemEvolveList"][
     "Post", {2, IntegerDigits[264107671, 2, 28]}, 643158954877, 
     100000000, "Lengths", Methodology -> "BitwiseOptimized"]]], 
  Body -> True, AspectRatio -> 1/3, Filling -> Axis, 
  PlotStyle -> Hue[0.07, 1, 1]], 
 FrameTicks -> {Automated, 
    None, {Thread[{Range[0, 643000][[1 ;; -1 ;; 100000]], 
      Append[Range[0, 500][[1 ;; -1 ;; 100]], "600 billion"]}], 
    None}}]

However to this point—even with all of the computation I’ve accomplished—I haven’t discovered a single instance the place it doesn’t finally halt.

If we have been doing strange pure science, billions of examples that every one in the end work the identical would usually be excess of sufficient to persuade us of one thing. However from learning the computational universe we all know that this type of “scientific inference” received’t at all times be appropriate. Gödel’s theorem from 1931 launched the thought of undecidability (and it was sharpened by Turing machines, and so on.). And that’s what can chew us within the computational universe.

As a result of one of many penalties of undecidability as we now understand it is that there may be questions the place there could also be no certain on how a lot computation will probably be wanted to reply them. So which means even when we have now did not see one thing in billions of examples that does not imply it’s unattainable; it might simply be that we haven’t accomplished sufficient computation to see it.

In follow it’s tended to be assumed, although, that undecidability is one thing uncommon and unique, that one will solely run into if one asks some sort of awkward—or “meta”—query. However my explorations within the computational universe—and specifically my Principle of Computational Equivalence—suggest that this isn’t appropriate, and that as a substitute undecidability is quite ubiquitous, and happens primarily each time a system can behave in methods that aren’t clearly easy.

And which means—regardless of the simplicity of its development—it’s truly to be anticipated that one thing just like the 00, 1101 tag system may present undecidability, and in order that questions on it may require arbitrary quantities of computational effort to reply. However there’s one thing of a catch. As a result of the way in which one usually proves the presence of undecidability is by proving computation universality. However at the least within the typical mind-set about computation universality, a common system can’t at all times halt—since in any other case it wouldn’t be capable of emulate methods that themselves don’t halt.

So with this connection between halting and computation universality, we have now the conclusion that if the 00, 1101 tag system at all times halts it can’t be computation common. So from our failure to discover a non-halting instance the obvious conclusion may be that our tag system does in truth at all times halt, and isn’t common.

And this might then be taken as proof in opposition to the Precept of Computational Equivalence, or at the least its utility to this case. However I imagine strongly sufficient within the Precept of Computational Equivalence that I might have a tendency to attract the alternative conclusion: that really the 00, 1101 tag system is common, and received’t at all times halt, and it’s simply that we haven’t gone far sufficient in investigating it to see a non-halting instance but.

However how far ought to we have now to go? Undecidability says we are able to’t make certain. However we are able to nonetheless probably use experience from studying other systems to get some sense. And this in truth tends to counsel that we’d need to go a protracted option to get our first non-halting instance.

We noticed above an example of cellular automata during which unbounded progress (a tough analog of non-halting) does happen, however we have now to look by means of nearly 100,000 initial conditions earlier than we discover it. A New Form of Science incorporates many different examples. And in quantity concept, it’s fairly routine to have Diophantine equations where the smallest solutions are very large.

How ought to we take into consideration these sorts of issues? In essence, we’re taking computation common methods and attempting to “program them” (by establishing acceptable preliminary circumstances) to have a specific type of habits, say non-halting. However there’s nothing to say these applications need to be quick. Sure, non-halting might sound to us like a easy goal. And, sure, the common system ought to in the long run be capable of obtain it. However given the actual elements of the common system, it might be sophisticated to get.

Let me provide two analogies. The primary has to do with mathematical proofs. Having discovered the very simplest possible axiom system for Boolean algebra ((p · q) · r) · (p · ((p · r) · p)) = = r, we all know that in precept we are able to show any theorem in Boolean algebra. However even one thing like p · q = q · pwhich may appear easy to us—can take a whole lot of elaborate steps to show given our specific axiom system.

As a extra whimsical instance, think about the method of self-reproduction. It appears easy sufficient to explain this goal, but to attain it, say with the elements of molecular biology, could also be complicated. And perhaps on the early Earth it was solely as a result of there have been so many molecules, and a lot time, that self-reproduction may ever be “found”.

One may suppose that, sure, it could possibly be tough to seek out one thing (like a non-halting preliminary situation, or a configuration with specific habits in a mobile automaton) by pure search, however that it could nonetheless be attainable to systematically “engineer” one. And certainly there could also be methods to “engineer” preliminary circumstances for the 00, 1101 tag system. However normally it’s one other consequence of the Precept of Computational Equivalence (and computational irreducibility) that there isn’t any assure that there will probably be any “easy engineering path” to achieve any specific functionality.

By the way in which, one impression from tag methods and plenty of other forms of methods is that as one will increase the sizes of preliminary circumstances, one crosses a sequence of thresholds for various behaviors. Solely at measurement 14, for instance, may some lengthy “freeway” in our tag system’s state transition graph seem. After which nothing longer may seem till measurement 17. Or some specific interval of ultimate cycle may solely seem at size-15 preliminary circumstances. It’s as if there’s a “minimal program size” wanted to attain a specific goal, in a specific system. And maybe equally there’s a minimal preliminary string size vital to attain non-halting in our tag system—that we simply don’t occur to have reached but. (I’ve accomplished random searches in longer preliminary circumstances, although, so we at the least comprehend it’s not frequent there.)

OK, however let’s strive a special tack. Let’s ask what can be concerned in proving that the tag system doesn’t at all times halt. We’re attempting to show primarily the next assertion: “There exists an preliminary situation i such that for all steps t the tag system has not halted”. Within the language of mathematical logic this can be a ∃∀ assertion, that’s on the degree within the arithmetic hierarchy.

One option to show it’s simply explicitly to discover a string whose evolution doesn’t halt. However how would one present that the evolution doesn’t halt? It may be apparent: there may for instance simply be one thing like a hard and fast block that’s getting added in a easy cycle of some type, as in:

ListStepPlot
&#10005
ListStepPlot[
   ResourceFunction[
     "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
       s___} :> {s, 0, 1}, {2, _, s___} :> {s, 2, 2, 1}}, {2, 0, 2}, 
    100, 1, "Lengths"], Heart, PlotRange -> {{0, 100}, Automated}, 
   AspectRatio -> 1/3, Filling -> Axis, Body -> True, 
   FrameTicks -> False, PlotStyle -> Hue[0.07, 1, 1]] &[52 -> {3, 20}]

Nevertheless it additionally may not be apparent. It could possibly be like a few of our examples above the place there appears to be systematic progress, however the place there are small fluctuations:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 1}, {1, _, 
     s___} :> {s, 1, 1, 0}}, {1, 0}, 200, 1, "Lengths"], Heart, 
 AspectRatio -> 1/3, Filling -> Axis, Body -> True, 
 FrameTicks -> False, PlotStyle -> Hue[0.07, 1, 1]]

Will these fluctuations suddenly become big and lead the system to halt? Or will they at all times keep by some means sufficiently small that that can’t occur? There are many questions like this that come up in quantity concept. And typically (as, for instance, with the Skewes number associated with the distribution of primes) there may be surprises, with very long-term developments getting reversed solely in exceptionally massive circumstances.

By the way in which, even figuring out “halting” may be tough, particularly if (as we do for our tag system) we outline “halting” to incorporate going right into a cycle. For instance, we noticed above a tag system that does cycle, however takes greater than 18,000 steps to take action:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction[
   "TagSystemEvolveList"][{{0, _, s___} :> {s, 0}, {1, _, 
     s___} :> {s, 0, 2}, {2, _, s___} :> {s, 1, 1, 2}}, 
  IntegerDigits[6, 3, 2], 40000, 1, "Lengths"], Heart, 
 AspectRatio -> 1/5, Filling -> Axis, Body -> True, 
 FrameTicks -> False, PlotStyle -> Hue[0.07, 1, 1]]

Conversely, simply because one thing takes a very long time to halt doesn’t imply that it is going to be tough to point out this. For instance, it’s fairly frequent to see Turing machines that take an enormous variety of steps to halt, however behave in mainly systematic and predictable methods (this one takes 47,176,870 steps):

alt

However to “clarify why one thing halts” we’d need to have one thing like a mathematical proof: a sequence of steps per a sure set of axioms that derives the truth that the system halts. In impact the proof is a higher-level (“symbolic”) means of representing elements of what the system is doing. As a substitute of all the person values at every step within the evolution of the system we’re simply calling issues x and y (or no matter) and deriving relationships between them at some sort of symbolic degree.

And given a specific axiom system it might or is probably not attainable to assemble this type of symbolic proof of any given reality. It could possibly be that the axiom system simply doesn’t have the “derivational energy” to characterize faithfully sufficient what the system we’re learning is doing.

So what does this imply for tag methods? It means, for instance, that it may completely effectively be {that a} given tag system evolution doesn’t halt—however that we couldn’t show that utilizing, say, the axiom system of Peano Arithmetic.

And actually as quickly as we have now a system that’s computation common it seems that any finite axiom system should finally fail to have the ability to give a finite proof of some reality in regards to the system. We will consider the axioms as defining sure relations in regards to the system. However computational irreducibility implies that finally the system will be capable of do issues which can’t be “decreased” by any finite set of relations.

Peano Arithmetic incorporates as an axiom the assertion that mathematical induction works, within the sense that if a press release s[0] is true, and s[n] implies s[n + 1], then any assertion s[n] have to be true. Nevertheless it’s attainable to come up with statements that entail for instance nested collections of recursions that successfully develop too rapidly for this axiom alone to have the ability to describe symbolically “in a single go” what they’ll do.

If one makes use of a stronger axiom system, nonetheless, then one will be capable of do that. And, for instance, Zermelo–Fraenkel set theory—which permits not solely strange induction but additionally transfinite induction—could reach with the ability to give a proof even when Peano Arithmetic fails.

However in the long run any finitely specified axiom system will fail to have the ability to show every part a couple of computationally irreducible system. Intuitively it’s because making proofs is a type of computational discount, and it’s inevitable that this may solely go to this point. However more formally, one can think about utilizing a computational system to encode the attainable steps that may be made with a given axiom system. Then one would assemble a program within the computational system that will systematically enumerate all theorems within the axiom system. (It could be simpler to consider first making a multiway system during which every attainable utility of the axiom guidelines is made, after which “unrolling” the multiway system to be “run sequentially”.)

And for instance we may set issues up in order that the computational system halts if it ever finds an inconsistency within the theorems derived from the axiom system. However then we all know that we received’t be capable of show that the computational system doesn’t halt from inside the axiom system as a result of (by Gödel’s second incompleteness theorem) no nontrivial axiom system can show its personal consistency.

So if we selected to work, say, purely inside Peano Arithmetic, then it may be that Put up’s authentic query is just unanswerable. We’d haven’t any option to show or disprove that his tag system at all times halts. To know which may require a finer degree of study—or, in impact, the next diploma of discount—than Peano Arithmetic can present. (Choosing a particular model of Peano Arithmetic would resolve the question, however to residence in on a specific mannequin can in impact require infinite computational effort.)

If we have now a tag system that we all know is common then it’s inevitable that sure issues about it is not going to be provable inside Peano Arithmetic, or some other finitely specified axiom system. However for any given property of the system it might be very tough to find out whether or not that property is provable inside Peano Arithmetic.

The issue is just like proving computation universality: in impact one has to see methods to encode some specified construction inside a specific formal system—and that may be arbitrarily tough to do. So simply as it might be very exhausting to show that the 00, 1101 tag system is computation common, it might even be very tough to show that some specific property of it’s not “accessible” by means of Peano Arithmetic.

Might or not it’s undecidable whether or not the 00, 1101 tag system at all times halts? And if we may show this, would this even have proved that it in truth doesn’t halt? Recall that above we talked about that at the least the plain assertion of the issue is on the degree within the arithmetic hierarchy. And it seems that statements at this degree don’t have “default truth values”, so proving undecidability wouldn’t instantly give us a conclusion. However there’s nothing to say that some intelligent reformulation may not scale back the issue to or , at which level proving undecidability would lead to a definite conclusion.

(One thing like this in truth occurred with the Riemann Speculation. At first this appeared like a assertion, nevertheless it was reformulated as a statement—and finally decreased to the particular assertion a number of sections above {that a} specific computation shouldn’t terminate. However now if the termination of that is proved undecidable, it should in truth not terminate, and the Riemann Speculation have to be true.)

Can one show undecidability with out proving computation universality? There are in precept methods that present “intermediate degrees”: they exhibit undecidability however can’t straight be used to do common computation (and Put up was in truth the one who advised that this may be attainable). However precise examples of methods with intermediate diploma nonetheless appear to contain having computation universality “inside”, however then limiting the input-output capabilities to forestall the universality from being accessed, past making sure properties undecidable.

Essentially the most satisfying (and in the end passable) option to show universality for the 00, 1101 tag system would merely be to assemble a compiler that takes a specification of another system that’s identified to help universality (say a specific known-to-be-universal tag system, or the set of all attainable tag methods) after which turns this into an preliminary string for the 00, 1101 tag system. The tag system would then “run” the string, and generate one thing that might readily be “decoded” as the results of the unique computation.

However there are methods one may think establishing what quantities to universality, that could possibly be sufficient to show halting properties, despite the fact that they may not be as “sensible” as precise methods to do computations. (Sure, one may conceivably think about a molecular-scale pc that works similar to a tag system.)

Within the present proofs of universality for the simplest cellular automata and Turing machines, for instance, one assumes that their preliminary configurations comprise “background” periodic patterns, with the particular enter for a specific computation being a finite-size perturbation to this background. For a mobile automaton or Turing machine it appears pretty unremarkable to think about such a background: despite the fact that it extends infinitely throughout the cells of the system it by some means doesn’t appear to be including greater than a small quantity of “new data” to the system.

However for a tag system it’s extra sophisticated to think about an infinite periodic “background”, as a result of at each step the string the system is coping with is finite. One may think about modifying the foundations of the tag system in order that, for instance, there’s some fastened background that acts as a “masks” each time the block of components is added on the finish of the string. (For instance, the masks may flip the worth of each ingredient, relative to a hard and fast “coordinate system”.)

However with the unique tag system guidelines the one option to have an infinite background appears to be to have an infinite string. However how may this work? The foundations of the tag system add components on the finish of the string, and if the string is infinitely lengthy, it’s going to take an infinite variety of steps earlier than the values of those components ever matter to the precise habits of the system.

There’s one barely unique chance, nonetheless, which is to consider transfinite variations of the tag system. Think about that the string within the tag system has a size given by a transfinite number, say the ordinal ω. Then it’s completely significant within the context of transfinite arithmetic to think about further components being added at positions ω + 1 and so on. And if the tag system then runs for ω steps, its habits can begin to rely upon these added components.

And despite the fact that the strings themselves can be infinite, there can nonetheless be a finite (“symbolic”) option to describe the system. For instance, there could possibly be a operate f[i] which defines the worth of the ingredient. Then we are able to formally write down the foundations for the tag system when it comes to this operate. And despite the fact that it could take an infinite time to explicitly generate the strings which are specified, it may well nonetheless be attainable to “purpose” about what occurs, simply by doing symbolic operations on the operate f.

For sure, the assorted points I’ve mentioned above about provability specifically axiom methods could come into play. However there should still be circumstances the place particular outcomes about computation universality could possibly be established “symbolically” about transfinite tag methods. And conceivably such outcomes may then be “projected down” to suggest undecidability or different outcomes about tag methods with finite preliminary strings.

Clearly the query of proving (or disproving) halting for the 00, 1101 tag system is a sophisticated one. We may be fortunate, and be capable of discover with our computer systems (or conceivably engineer) an preliminary string that we are able to see doesn’t halt. Or we’d be capable of assemble a symbolic illustration during which we are able to perform a proof.

However in the end we’re in a way on the mercy of the Precept of Computational Equivalence. There’s presumably computational irreducibility within the 00, 1101 tag system that we are able to’t systematically outrun.

Sure, the hint of the tag system appears to be a great approximation to a random stroll. And, sure, as a random stroll it’s going to halt with likelihood 1. However in actuality it’s not a “really random” random stroll; it’s a stroll decided by a particular computational course of. We will flip our questions on halting to questions in regards to the randomness of the stroll (and to take action could present attention-grabbing connections with the foundations of likelihood concept). However in the long run we’re again to the identical points, and we’re nonetheless confronted by computational irreducibility.

Extra in regards to the Historical past

Emil Post

Tag methods are easy sufficient that it’s conceivable they might have arisen in something like games even millennia in the past. However for us tag methods—and notably the particular 00, 1101 tag system we’ve largely been learning—have been the invention of Emil Put up, in 1921.

Emil Put up lived most of his life in New York Metropolis, although he was born (right into a Jewish household) in 1897 in Augustow, Poland (then a part of the Russian Empire). (And, sure, it’s really exceptional how most of the notable contributors to mathematical logic within the early a part of the twentieth century have been born to Jewish households in a reasonably small area of what’s now japanese Poland and western Ukraine.)

As a toddler, Put up appears to have at first needed to be an astronomer, however having misplaced his left arm in a freak car-related road accident at age 12 he was informed this was impractical—and turned as a substitute to arithmetic. Put up went to a public highschool for presented college students after which attended Metropolis Faculty of New York, graduating with a bachelor’s diploma in math in 1917. Maybe presaging a lifelong curiosity in generalization, he wrote his first paper while in college (although it wasn’t revealed till 15+ years later), with reference to fractional differentiation.

He enrolled within the math PhD program at Columbia, the place he bought concerned in a seminar learning Whitehead and Russell’s just lately revealed Principia Mathematica, run by Cassius Keyser, who was one of many early American mathematicians within the foundations of math (and who wrote many books on historical past and philosophy round arithmetic; a typical instance being his 1922 Mathematical Philosophy, a Study of Fate and Freedom). Early in graduate faculty, Put up wrote a paper about functional equations for the gamma function (associated to fractional differentiation), however quickly he turned to logic, and his thesis—written in 1920—included early variations of what grew to become his signature concepts.

Put up’s primary goal in his thesis was to simplify, streamline and additional formalize Principia Mathematica. He began by propositional calculus, and tried to “drill down” to seek out out extra of what logic was actually about. He invented truth tables (as several other people also independently did) and used them to show completeness and consistency outcomes. He investigated how completely different logic features could possibly be built up from one another by means of composition, classifying completely different components of what’s now referred to as the Post lattice. (He commented on Nand and an early easy axiom system for it—and may effectively have gone additional with it if he’d identified the minimal axiom system for Nand that I finally discovered in 2000. In one other small-intellectual-world story, I understand now his lattice can be just like my “cellular automaton emulation network”.) Going within the path of “what’s logic actually about” Put up additionally thought-about multivalued logic, and algebraic buildings round it.

Put up revealed the core of his thesis in 1921 as “Introduction to a General Theory of Elementary Propositions”, however—in an unlucky and recurring theme—didn’t publish the whole thing for an additional 20 years. However even in 1920 Put up had what he referred to as “generalization by postulation” and this rapidly became the concept all operations in Principia Mathematica (or arithmetic normally) may in the end be represented as transformations (“manufacturing guidelines”) on strings of characters.

When he lastly ended up publishing this in 1943 he referred to as the ensuing formal buildings “canonical methods”. And already by 1920 he’d found that not all attainable manufacturing guidelines have been wanted; it was ample to have solely ones in “regular type” g$$h, the place $ is a “sample variable”. (The thought of $ representing a sample grew to become frequent in early pc string-manipulation methods, and actually I used it for expression patterns in my SMP system in 1979—most likely with out on the time understanding it got here from Put up.)

Put up was near the idea of common computation, and the notion that something (in his case, any string transformation) could possibly be constructed up from a hard and fast set of primitives. And in 1920 —within the effort to “scale back his primitives” he got here up with tag methods. On the time—11 years earlier than Gödel’s theorem—Put up and others nonetheless thought that it’d by some means be attainable to “remedy arithmetic” in some finite means. Put up felt he had good proof that Principia Mathematica could possibly be decreased to string rewriting, so now he simply needed to remedy that.

One fundamental query was methods to inform when two strings must be thought-about equal underneath the string rewriting guidelines. And in formulating a easy case of this Put up got here up with tag methods. Specifically, he needed to find out whether or not the “iterative course of [of tag] was terminating, periodic, or divergent”. And Put up made “the issue of ‘tag’… the key undertaking of [his] tenure of a Procter fellowship in arithmetic at Princeton throughout the tutorial 12 months 1920–21.”

Put up later reported {that a} “main success of the undertaking was the whole resolution of the issue for all bases during which μ and ν have been each 2”, although said that “even this particular case… concerned appreciable labor”. However then, as he later wrote, “whereas appreciable effort was expanded [sic] on the case μ = 2, ν > 2… little progress resulted… [with] such a easy foundation as 000, 11101, ν = 3, proving intractable”. Put up makes a footnote “Quite a few preliminary sequences… tried [always] led… to termination or periodicity, often the latter.” Then he added, reflecting our random stroll observations, “It may be famous that an simply derived likelihood ‘prognostication’ advised… that periodicity was to be anticipated.” (I’m curious how he may inform it must be periodicity fairly than termination.)

However by the top of the summer time of 1921, Put up had concluded that “the answer of the final downside of ‘tag’ appeared hopeless, and with it [his] complete program of the answer of finiteness issues”. In different phrases, the seemingly easy downside of tag had derailed Put up’s complete program of “fixing arithmetic”.

In 1920 Princeton had a prime American arithmetic division, and Put up went there on a prestigious fellowship (just lately endowed by the Procter of Procter & Gamble). However—like the issue of tag—issues didn’t work out so effectively there for Put up, and in 1921 he had the primary of what would develop into a sequence of “runaway thoughts” manic episodes, in what seems to have been a cycle of what was then referred to as manic melancholy.

It is unusual to suppose that the issue of tag might need “pushed Put up loopy”, and possibly the timing of the onset of manic melancholy had extra to do along with his age—although Put up later appears to have believed that the thrill of analysis may set off manic episodes (which regularly concerned talking intensely about streams of poorly connected ideas, just like the “psychic ether” from which new concepts come, discovering a brand new star named “Put up”, and so on.) However in any case, in late 1921 Put up—who had by then returned to Columbia—was institutionalized.

By 1924 he had recovered sufficient to take up an instructorship at Cornell, however then relapsed. Through the years that adopted he supported himself by educating highschool in New York, however continued to have psychological well being points. He married in 1929, had a daughter in 1932, and in 1935 lastly grew to become a professor at Metropolis Faculty, the place he remained for the remainder of his life.

Put up revealed nothing from the early Nineteen Twenties till 1936. However in 1936—with Gödel’s theorem identified, and Alonzo Church’s “An Unsolvable Problem of Elementary Number Theory” just lately revealed—Put up revealed a 3-page paper entitled “Finite Combinatory Processes—Formulation 1”. Put up comes extremely near defining Turing machines (he talks about “employees” interacting with a probably infinite sequence of “marked” and “unmarked packing containers”). And he says that he “expects [his] formulation to be logically equal to recursiveness within the sense of the Gödel–Church growth”, including “Its function, nonetheless, is just not solely to current a system of a sure logical efficiency but additionally, in its restricted area, of psychological constancy”. Put up doesn’t get too particular, however he does make the remark (fairly resonating with my own work, and notably our Physics Venture) that the speculation of world success of those formalisms can be “not a lot… a definition or an axiom however… a pure legislation”.

In 1936 Put up additionally revealed his longest-ever paper: 142 pages on what he referred to as “polyadic teams”. It’s mainly about summary algebra, however in typical Put up model, it’s a generalization, involving trying not at binary “multiplication” operations however for instance ternary ones. It’s not been a preferred matter, although, curiously, I additionally independently got interested in it in the 1990s, finally discovering Put up’s work on it.

By 1941 Put up was publishing extra, together with a number of now-classic papers in mathematical logic, protecting issues like levels of unsolvability, the unsolvability of the phrase downside for semigroups, and what’s now referred to as the Post Correspondence Problem. He managed his time in a really exact means, following a grueling educating schedule (with intense and exact lectures deliberate to the minute) and—apparently to keep up his psychological wellbeing—restricting his analysis actions to 3 particular hours every day (interspersed with walks). However by then he was a revered professor, and logic had develop into a extra common area, giving him extra of an viewers.

In 1943, largely summarizing his earlier work, Put up revealed “Formal Reductions of the General Combinatorial Decision Problem”, and in it, the “downside of tag” makes its first revealed look:

Post’s problem of tag

Put up notes that “the little progress made in [its] resolution” makes it a “candidate for unsolvability”. (Discover the correction in Put up’s handwriting “intensely” “intensively” within the copy of his paper reproduced in his collected works.)

By means of all this, nonetheless, Put up continued to wrestle with psychological sickness. However by the point he reached the age of fifty in 1947 he started to enhance, and even loosened up on his inflexible schedule. However in 1954 melancholy was again, and after receiving electroshock remedy (which he thought had helped him prior to now), he died of a coronary heart assault on the age of 57.

His former undergraduate pupil, Martin Davis, finally published Post’s “Absolutely Undecidable Problems”, subtitled “Account of an Anticipation”, which describes the arc of Put up’s work—together with extra element on the story of tag methods. And in hindsight we are able to see how shut Put up got here to discovering Gödel’s theorem and inventing the thought of common computation. If as a substitute of turning away from the complexity he present in tag methods he had embraced and explored it, I believe he would have discovered not solely foundational concepts of the Nineteen Thirties, but additionally a few of what I discovered half a century later in my by-then-computer-assisted explorations of the computational universe.

When Put up died, he left many unpublished notes. A substantial quantity of them concern a serious undertaking he launched in 1938 that he deliberate to name “Artistic Logic”. He appeared to really feel that “excessive abstraction” as a means of exploring arithmetic would give option to one thing during which it’s acknowledged that “processes of deduction are themselves primarily bodily and therefore topic to formulations in a bodily science”. And, sure, there’s an odd resonance right here with my very own present efforts—knowledgeable by our Physics Venture—to “physicalize” metamathematics. And maybe I’ll uncover that right here too Put up anticipated what was to come back.

So what occurred to tag methods? By the mid-Nineteen Fifties Put up’s concept of string rewriting (“manufacturing methods”) was making its means into many issues, notably each the event of generative grammars in linguistics, and formal specifications of early computer languages. However tag methods—which Put up had talked about solely as soon as in his revealed works, after which as a sort of apart—have been nonetheless mainly unknown.

Put up had come to his string rewriting methods—a lot as Turing had come to his Turing machines—as a option to idealize the processes of arithmetic. However by the Nineteen Fifties there was growing curiosity in utilizing such summary methods as a option to characterize “basic computations”, in addition to brains. And one individual drawn on this path was Marvin Minsky. After a math PhD in 1954 at Princeton on what amounted to analog synthetic neural networks, he began exploring extra discrete methods, initially finite automata, primarily trying to find the only components that will help common computation (and, he hoped, thinking-like habits).

Close to the top of the Nineteen Fifties he checked out Turing machines—and in looking for the only type of them that will be common began their correspondence with Put up’s string rewriting methods. Marvin Minsky knew Martin Davis from their time collectively on the Bronx Excessive College of Science in New York, and by 1958 Davis was totally launched in mathematical logic, with a just lately revealed e book entitled Computability and Unsolvability.

As Davis tells it now, Minsky phoned him about some unsolvability outcomes he had about Put up’s methods, asking in the event that they have been of curiosity. Davis informed him about tag methods, and that Put up had thought they may be common. Minsky discovered that indeed they were, publishing the lead to 1960 in “Recursive Unsolvability of Post’s Problem of ‘Tag’ and Other Topics in Theory of Turing Machines”.

Minsky had just lately joined the school at MIT, but additionally had a place at MIT’s Lincoln Laboratory, the place in engaged on computing for the Air Power there was a collaboration with IBM. And it was most likely by means of this that Minsky met John Cocke, a lifelong pc designer (and basic inventor) at IBM (who in later years was instrumental within the growth of RISC architecture). The consequence was that in 1963 Minsky and Cocke revealed a paper entitled “Universality of Tag Systems with P=2” that dramatically simplified Minsky’s development and confirmed (primarily by compiling to a Turing machine) that universality could be achieved with tag methods that delete solely 2 components at every step. (One may consider it as an final RISC structure.)

For a number of years, Minsky had been looking for out what the only common Turing machine may be, and in 1962 he used the outcomes Cocke and he had about tag methods to assemble a 7-state, 4-color universal machine. That machine remained the report holder for the only identified common Turing machine for greater than 40 years, although lastly now we all know the very easiest attainable common machine: a 2,3 machine that I discovered and conjectured can be common—and that was proved so by Alex Smith in 2007 (thereby profitable a prize I offered).

However again in 1967, the visibility of tag methods bought an enormous enhance. Minsky wrote an influential e book entitled Computation: Finite and Infinite Machinesand the final a part of the e book was dedicated to “Image-Manipulation Methods and Computability”, with Put up’s string rewriting methods a centerpiece.

However my favourite a part of Minsky’s e book was at all times the final chapter: “Very Easy Bases for Computability”. And there on web page 267 is Put up’s tag system:

From Marvin Minsky’s “Very Simple Bases for Computability”

Minsky experiences that “Put up discovered this (00, 1101) downside ‘intractable’, and so did I, even with the assistance of a pc”. However then he provides, in a mode very attribute of the Marvin Minsky I knew for practically 40 years: “After all, until one has a concept, one can’t count on a lot assist from a pc (until it has a concept)…” He goes on to say that “if the reader tries to check the habits of 100100100100100100 with out [the aid of a computer] he will probably be sorry”.

Effectively, I assume computer systems have gotten so much quicker because the early Sixties; for me now it’s trivial to find out that this case evolves to a 10-cycle after 47 steps:

ListStepPlot
&#10005
ListStepPlot[
 ResourceFunction["TagSystemEvolveList"]["Post", 
  Flatten[Table[{1, 0, 0}, 6]], 90, 1, "Lengths"], Filling -> Axis, 
 Body -> True, AspectRatio -> 1/3, PlotStyle -> Hue[0.07, 1, 1]]

(By the way in which, I just lately requested Martin Davis if Put up had ever run a tag system on a pc. He responded: “Goodness! When Put up died von Neumann nonetheless thought {that a} dozen computer systems ought to suffice for America’s wants.  I assume I may have programmed [the tag system] for the [Institute for Advanced Study] pc, nevertheless it by no means occurred to me to take action.” Notably, in 1954 Davis did begin programming logic theorem-proving algorithms on that pc.)

After their look in Minsky’s e book, tag methods grew to become “identified”, however they hardly grew to become well-known, and solely a only a few papers appeared about them. In 1972, at the least their title bought some visibility, when Alan Cobham, a longtime IBMer then engaged on coding concept, revealed a paper entitled “Uniform Tag Sequences”. Sure, this was about tag methods, however now with only one ingredient being deleted at every step, which meant there couldn’t actually be any interplay between components. The arithmetic was rather more tractable (this was considered one of a number of innovations of neighbor-independent substitution systems producing purely nested habits), nevertheless it didn’t actually say something about Put up’s “downside of tag”.

Truly, I’ve Been Right here Earlier than…

Once I began engaged on A New Kind of Science in 1991 I needed to discover the computational universe of easy applications as extensively as I may—to seek out out simply how basic (or not) the shocking phenomena I’d seen in mobile automata within the Eighties truly have been. And virtually from the start within the desk of contents for my chapter on “The World of Simple Programs”, nestled between substitution methods and register machines, have been tag methods (I had truly first talked about tag methods in a paper in 1985):

“The World of Simple Programs”

In the principle textual content, I solely spent two pages on them:

Tag systems in A New Kind of Science

And I did what I’ve accomplished so many times for so many kinds of systems: I searched and located remarkably easy guidelines that generate complicated habits. After which on these pages I confirmed my favourite examples. (I generalized Put up’s particular tag methods by permitting dependence on extra than simply the primary ingredient.)

Did I take a look at Put up’s particular 00, 1101 system? A New Form of Science consists of the note:

Notes on tag systems

And, sure, it mentions Put up’s 00, 1101 tag system, then feedback that “at the least for all of the preliminary circumstances as much as size 28, the rule finally simply results in habits that repeats”. An innocuous-looking assertion, in very small print, tucked behind my very large e book. However like so many such statements within the e book, there was quite a bit behind it. (By the way in which, “size 28” then is what I might think about [compressed] size 9 now.)

A fast search of my filesystem rapidly reveals (.ma is an earlier format for notebooks that, sure, we are able to nonetheless learn over a 3rd of a century later):

A quick search of my filesystem

I open one of many pocket book recordsdata (and, sure, home windows—and screens—have been tiny in these days):

TagSystems2.nb

And there it’s! Put up’s 00, 1101 tag system, together with many others I used to be learning. And it appears I couldn’t let go of this; in 1994 I used to be working a standalone program to attempt to discover infinitely rising circumstances. Right here’s the output:

Output

In order that’s the place I bought my assertion about “as much as measurement 28” (now measurement 9) from. I don’t know the way lengthy this took to run; “pyrethrum” was on the time the quickest pc at our company—with a newfangled 64-bit CPU (a DEC Alpha) working on the now-snail-sounding clock velocity of 150 MHz.

My archives from the early Nineties report a good quantity of further “visitors” about tag methods. Interactions with Marvin Minsky. Interactions with my then-research-assistant about what I ended up calling “cyclic tag systems” (I initially referred to as them “cyclic substitution methods”).

For practically 15 years there’s not a lot. That’s, till June 25, 2007. It’s been my custom since we began our Wolfram Summer School again in 2003 that on the primary day I do a “dwell experiment”, and attempt to uncover one thing. Effectively, that day I made a decision to take a look at tag methods. Right here’s how I started:

LiveExperiment1-01.nb

Proper there, it’s Put up’s 00, 1101 system. And I believe I took it additional than I’d ever accomplished earlier than. Fairly quickly I used to be discovering “lengthy survivors” (I even bought one which lasted greater than 200,000 steps):

LiveExperiment1-03.nb

I used to be drawing state transition graphs:

LiveExperiment1-02.nb

However I clearly determined that I couldn’t get additional with the 00, 1101 system that day. So I turned to “variants” and rapidly discovered the 2-element-deletion 1, 110 rule that I’ve described above.

I occurred to put in writing a piece about this particular live experiment (“Science: Live and in Public”), and proper then I made a psychological word: let me take a look at Put up’s tag system once more earlier than its centenary, in 2021. So right here we’re….

The Path Ahead

Emil Put up didn’t handle to crack his 00, 1101 tag system again in 1921 with hand calculations. However we’d think about {that a} century later—with the equal of tens of billions instances extra computational energy we’d be capable of do. However to this point I haven’t managed it.

For Put up, the failure to crack his system derailed his complete mental worldview. For me now, the failure to crack Put up’s system in a way simply bolsters my worldview—offering but extra indication of the power and ubiquity of computational irreducibility and the Precept of Computational Equivalence.

After spending a number of weeks throwing a whole lot of recent computer systems and all types of computational strategies at Put up’s 00, 1101 tag system, what do we all know? Right here’s a abstract:

  •   All preliminary strings as much as (uncompressed) size 84 lead both to cycles or termination
  •   The time to termination or biking may be so long as 643 billion steps
  •   The sequence of lengths of strings generated appears to at all times behave very like a random stroll
  •   The sequences of 0s and 1s generated appear successfully random, aside from about 31% statistical redundancy
  •   Most cycles are in particular households, however there are additionally some sporadic ones

What’s lacking right here? Put up needed to know whether or not the system would halt, and so will we. However now the Principle of Computational Equivalence makes a particular prediction. It predicts that the system must be able to common computation. And this mainly has the implication that the system can’t at all times halt: there needs to be some preliminary string that may make it develop endlessly.

In pure science it’s customary for theories to make predictions that may be investigated by doing experiments within the bodily world. However the sort of predictions that the Precept of Computational Equivalence makes are extra basic; they’re not nearly specific methods within the pure world, however about all attainable summary methods, and in a way all conceivable universes. Nevertheless it’s nonetheless attainable to do experiments about them, although the experiments at the moment are not bodily ones, however summary ones, carried out within the computational universe of attainable applications.

And with Put up’s tag system we have now an instance of 1 specific such experiment: can we discover non-halting habits that may validate the prediction that the system can help common computation? To take action can be one other piece of proof for the breadth of applicability of the Precept of Computational Equivalence.

However what’s going to be concerned in doing it? Computational irreducibility tells us that we are able to’t know.

Conventional mathematical science has tended to make the belief that when you already know an summary concept for one thing, then you possibly can work out something you need about it. However computational irreducibility exhibits that isn’t true. And actually it exhibits how there are basic limitations to science that intrinsically come up from inside science itself. And our problem in analyzing Put up’s tag system is in a way simply an “in your face” instance of how robust these limitations may be.

However the Precept of Computational Equivalence says that someplace we’ll see non-halting habits. It doesn’t inform us precisely what that habits will probably be like, or how tough it’ll be for us to interpret what we see. Nevertheless it says that the “easy conclusion” of “at all times halting” shouldn’t proceed endlessly.

I’ve to this point accomplished practically a quintillion iterations of Put up’s tag system in all. However that hasn’t been sufficient. I’ve been in a position to optimize the computations a bit. However essentially I’ve been left with what appears to be uncooked computational irreducibility. And to make progress I appear to wish extra time and extra computer systems.

Will 1,000,000 of as we speak’s computer systems be sufficient? Will it take a billion? I don’t know. Possibly it requires a brand new degree of computational velocity. Possibly to resolve the query requires extra steps of computation than the bodily universe has ever accomplished. I don’t know for positive. However I’m optimistic that it’s inside the present computational capabilities of the world to seek out that little string of bits for the tag system that may enable us to see extra in regards to the basic Precept of Computational Equivalence and what it predicts.

Sooner or later there will probably be ever extra that we are going to need and have to discover within the computational universe. And in a way the issue of tag is a dry run for the sorts of issues that we are going to see increasingly usually. However with the excellence of a century of historical past it’s a great place to rally our efforts and be taught extra about what’s concerned.

To date it’s solely been my computer systems which have been engaged on this. However we’ll be setting issues up in order that anybody can be part of the undertaking. I don’t know if it’ll get solved in a month, a 12 months or a century. However with the Precept of Computational Equivalence as my information I’m assured there’s one thing attention-grabbing to find. And a century after Emil Put up outlined the issue I, for one, need to see it resolved.

Notes

The primary tag-system-related features used are within the Wolfram Function Repository, as TagSystemEvolve, TagSystemEvolveList, TagSystemConvert, CyclicTagSystemEvolveList.

A listing of t steps within the evolution of the tag system from an (uncompressed) preliminary checklist init may be achieved with

TagSystemEvolveList
&#10005
TagSystemEvolveList[init_List, t_Integer] := 
 With[{ru = 
    Dispatch[{{0, _, _, s___} -> {s, 0, 0}, {1, _, _, s___} -> {s, 1, 
        1, 0, 1}}]}, NestList[Replace[ru], init, t]]

or

TagSystemEvolveList
&#10005
TagSystemEvolveList[init_List, t_Integer] := 
 NestWhileList[
  Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[1 + First[#]]]] &, init, 
  Size[#] >= 3 &, 1, t]

giving for instance:

TagSystemEvolveList
&#10005
TagSystemEvolveList[{1, 0, 0, 1, 0}, 4]

The checklist of lengths may be obtained from

TagSystemLengthList
&#10005
TagSystemLengthList[init_List, t_Integer] := 
 Reap[NestWhile[(Sow[Length[#]]; #) &[
      Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[1 + First[#]]]]] &, 
    init, Size[#] >= 3 &, 1, t]][[2, 1]]

giving for instance:

TagSystemLengthList
&#10005
TagSystemLengthList[{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0}, 25]

The output from t steps of evolution may be obtained from:

TagSystemEvolve
&#10005
TagSystemEvolve[init_List, t_Integer] := 
 NestWhile[Join[Drop[#, 3], {{0, 0}, {1, 1, 0, 1}}[[1 + First[#]]]] &,
   init, Size[#] >= 3 &, 1, t]

A model of this utilizing a low-level queue data structure is:

TagSystemEvolve
&#10005
TagSystemEvolve[init_List, t_Integer] := 
 Module[{q = CreateDataStructure["Queue"]}, Scan[q["Push", #] &, init];
  Do[If[q["Length"] >= 3, 
    Scan[q["Push", #] &, If[q["Pop"] == 0, {0, 0}, {1, 1, 0, 1}]]; 
    Do[q["Pop"], 2]], t]; Regular[q]]

The compressed {p, values} type of a tag system state may be obtained with

TagSystemCompress
&#10005
TagSystemCompress[list_] := {Mod[Length[list], 3], 
  Take[list, 1 ;; -1 ;; 3]}

whereas an uncompressed type may be recovered with:

TagSystemUncompress
&#10005
TagSystemUncompress[{p_, list_}, pad_ : 0] := 
 Be a part of[Riffle[list, Splice[{pad, pad}]], 
  Desk[pad, <|0 -> 2, 1 -> 0, 2 -> 1|>[p]]]

Every step in evolution in compressed type is obtained from

TagSystemCompressedStep
&#10005
TagSystemCompressedStep[{p_, {s_, r___}}] := 
 Apply[{#1, Join[{r}, #2]} &,
  <|{0, 0} -> {2, {0}}, {1, 0} -> {0, {}}, {2, 0} -> {1, {0}}, {0, 
      1} -> {1, {1, 1}}, {1, 1} -> {2, {0}}, {2, 1} -> {0, {1}}|>[{p, 
    s}]]

or:

TagSystemCompressedStep
&#10005
TagSystemCompressedStep[list : {_Integer, _List}] := 
 Substitute[list, {{0, {0, s___}} -> {2, {s, 0}}, {1, {0, 
      s___}} -> {0, {s}}, {2, {0, s___}} -> {1, {s, 0}}, {0, {1, 
      s___}} -> {1, {s, 1, 1}}, {1, {1, s___}} -> {2, {s, 0}}, {2, {1,
       s___}} -> {0, {s, 1}}}]

The biggest-scale computations accomplished right here made use of further-optimized code (out there within the Wolfram Operate Repository), during which the state of the tag system is saved in a bit-packed array, with 8 updates being accomplished at a time by having a desk of outcomes for all 256 circumstances and utilizing the primary byte of the bit-packed array to index into this. This strategy routinely achieves 1 / 4 billion updates per second on present {hardware}. (Bigger replace tables not slot in L1 cache and so sometimes don’t assist.)

As I’ve talked about, there isn’t a very massive literature on the particular habits of tag methods. In 1963 Shigeru Watanabe described the basic families of cycles for Put up’s 00, 1101 tag system (although didn’t uncover the “sporadic circumstances”). After A New Kind of Science in 2002, I’m conscious of 1 intensive sequence of papers (partly utilizing computer experiment methods) written by Liesbeth De Mol following her 2007 PhD thesis. Carlos Martin (a student at the Wolfram Summer School) additionally wrote about probabilistic methods for predicting tag system evolution.

Leave a Reply

Your email address will not be published.