These are lovely systems; suppose we want infinite feedback and at the same time want the graph to continue on generating indefinitely.
Multi-way tag systems in coordinatized rulial space
By Dean Song Gladish
Carleton College
Qooley.com
By Dean Song Gladish
Carleton College
Qooley.com
Abstract.The multi-way tag system, a topic in computational complexity based on Emil Post’s tag system, is that provided the positive integer v and µ symbols taken to be 0, 1, ..., µ-1, the association with each of the µ symbols is a finite sequence as follows. 0 . . . 0 . . . . . . . . . . . . .µ - 1 . . . For such a simple basis as 000, 11101, v=3, it’s an effective procedure for determining of an arbitrary initial My project focuses on the Post decision for a special type of normal system, faithfully per Post’s discovery that his tag operation is applicable in binary space. To advance our understanding of computational irreducibility, my project studies the behavior of tag systems with different rules & initial conditions, evaluated as single-way rules and multi-way tag systems. My project focuses on comparing single-way and multi-way behavior, exploring explosive, degenerate, and cyclic behavior, and visualizing novel instances of the Ruliology. Generating multi-way tag systems, the work provides a new coordinatized method for studying the Ruliad and Rulial space.
a
0,1
a
0,2
a
0,
v
0
a
1,1
a
1,2
a
1,
v
0
a
µ-1
a
µ-1,2
a
µ-1,
v
µ-1
sequence
4
.
The Post Tag System
The Post Tag System
The basis that Post mentions, is the goal of this project that is the tag system can act on different positions in the string such as the simple basis 000, 11101. Furthermore, single-element and two-element spatial tag systems can be generated via the multi-way graph, starting from different initial conditions. The analyzability of this project starts systematically via starting with the single characters 1, and 0. In the end, the symbolic choice of 0 and 1 is arbitrary.
Given all binary numbers 0, 1, 00, 01, 10, 11, 000, 001, etc. remove the first digit for the initial conditions. And for the rules, the same kind of thing so regardless of whether the update is put at the right or left hand side of the string, the multi-way system generated via string-rewriting is called a stag system because it’s about a spatial tag system; a system that can do its update from different positions in the string.
Therefore, visualize a multi-way tag system based on Post’s conjecture, which increments depending on the value of the tag system rules, depending on the dimensionality of the rule cycle sequence which generates paths; when the tag system rules increase dimensionality the string demonstrates explosive behavior, and when the tag system rules reduce the length of the focused string like 000 or 11011, the string degenerates. For dimensionality we create the generational plot, provided that the Post tag system describes extreme, either-or cases for rule length.
Provided that the rules are re-writing strings to greater lengths, most four-rule tag systems appear to be exploding. But first, let us look at the Post tag system with initial condition 101.
Given all binary numbers 0, 1, 00, 01, 10, 11, 000, 001, etc. remove the first digit for the initial conditions. And for the rules, the same kind of thing so regardless of whether the update is put at the right or left hand side of the string, the multi-way system generated via string-rewriting is called a stag system because it’s about a spatial tag system; a system that can do its update from different positions in the string.
Therefore, visualize a multi-way tag system based on Post’s conjecture, which increments depending on the value of the tag system rules, depending on the dimensionality of the rule cycle sequence which generates paths; when the tag system rules increase dimensionality the string demonstrates explosive behavior, and when the tag system rules reduce the length of the focused string like 000 or 11011, the string degenerates. For dimensionality we create the generational plot, provided that the Post tag system describes extreme, either-or cases for rule length.
Provided that the rules are re-writing strings to greater lengths, most four-rule tag systems appear to be exploding. But first, let us look at the Post tag system with initial condition 101.
The Post Tag System, With Initial Condition 1.
The Post Tag System, With Initial Condition 1.
As we know the Post Tag System with initial condition 0 is absolutely trivial. However, initial condition 1 brings about a general exhibition of the Post Tag System.
In[]:=
Dean=Labeled[Graph[ResourceFunction["MultiwaySystem"][{"0"->"00","1"->"1101"},{"1"},3,"StatesGraph",ImageSize->1000,Frame->{{True,False},{True,False}}]],StringTemplate["{0}`a` {1}`b` `e`"][<|"a"->{0,0},"b"->{1,1,0,1},"e":>{1}|>]]
Suppose that Post’s tag system, unless we want the left side of our string to be comprised exclusively of 0s, is mostly accessible via the input size of 1. The first and last 1s are merged because we are mapping rule 1->1101 recursively.
The Post Tag System, With Initial Condition 101.
The Post Tag System, With Initial Condition 101.
In[]:=
Dean=Labeled[Graph[ResourceFunction["MultiwaySystem"][{"0"->"00","1"->"1101"},{"101"},3,"StatesGraph",ImageSize->1000,Frame->{{True,False},{True,False}}]],StringTemplate["{0}`a` {1}`b` `e`"][<|"a"->{0,0},"b"->{1,1,0,1},"e":>{1,0,1}|>]]
The Post tag system is describing string re-writing, and for that there are two rules and three levels in the graph. This tag system is describing the string re-writing. The initial condition of 101 via the MultiwaySystem API determines the direction of time within the graph.
Section 1. Functions & Dependencies.
Section 1. Functions & Dependencies.
Emil Post is really interested in the same three classes of behavior, the iterative process of tag terminating, periodic, and divergent, divergent means length∞ and terminating means the length0 and periodic means we get all these jagged edges like mountains. That is with regard to computational complexity the major project of his tenure of a Procter fellowship in mathematics at Princeton during the academic year
To properly and clearly describe the evolution of the Post Tag System, the Wolfram Language code is presented in a clear narrative format, to explain how Post’s tag system is studied and how the tag system is degenerate, periodic, or exploding. As a result, the sections demarcate each major step function & point of clarification/pivot.
1920-
5
21.
To properly and clearly describe the evolution of the Post Tag System, the Wolfram Language code is presented in a clear narrative format, to explain how Post’s tag system is studied and how the tag system is degenerate, periodic, or exploding. As a result, the sections demarcate each major step function & point of clarification/pivot.
Sub-section 1. Make Shifted Tag System with Four-Set of Rules.
Sub-section 1. Make Shifted Tag System with Four-Set of Rules.
The implementation with NestGraph, that is NestList turned into edges between corresponding elements, and the generation of graphs with layered di-graph embedding, portrays the evolution of new tag systems in the Wolfram Language Code; ResourceFunction[“NestGraphTagged”] serves the function of differently tagging edges corresponding to different
outputs
3
.
The NestGraphTagged function allows us to plot Tag System 2.
In[]:=
Multicolumn[Table[ResourceFunction["NestGraphTagged"][ReplaceList[{{left___,0,0,s___}:>{left,s,1,0,0},{left___,1,0,s___}:>{left,s,1},{left___,0,1,s___}:>{left,s,1,1,0},{left___,1,1,s___}:>{left,s,0,1}}],{{1,1}},i,VertexShapeFunction->_->(Inset[ArrayPlot[{#2},ImageSize->32],#1,#3]&),GraphLayout->"LayeredDigraphEmbedding",PerformanceGoal->"Quality",ImageSize->Automatic],{i,1,8}]]
The graph of the string re-writing, for which Multicolumn allows the Table to be set as a value, denotes the function. Differentiating between branches at each step, we can show functions for Tag System 2 because the cyclic flexibility of the single-element is shown in each row, that is showing the maintenance of, for time steps from previous columns, the three-cycle type steps.
Define MultiwayTagSystem as its own function.
In this format, it’s very beautiful. But what is the point of showing this? To make the multi-way system understandable. The key observation to make about the Post tag system is that the cases of 0s are principally degenerate meaning that they interrupt the game of tag being played by rule 11101.
Tag System 2. Plot the MultiwayTagSystem vertex list against its complement.
ListLinePlot continuity between discrete points on the length of inductively unique vertices.
MultiwayTagSystem function on Tag System 2.
The purpose of Tag System 2 is to first exemplify the histogram & the length of inductively unique vertices.
Visualize Tag System Multi-Way. The RandomMultiwayTagSystem function.
The RandomMultiwayTagSystem function generates all distributed stag systems for Tag System 3.
The purpose of Tag System 3 is to exemplify a special case of degeneracy with rule 1 only. There is oscillatory behavior; generation plots aren’t exclusively explosive.
Suppose we want to vary the fourth rule of Tag System 3.
Aside from varying the initial condition, we can also vary the fourth rule.
Five Time Steps for Tag System 3.
The purpose of Tag System 3 is to exemplify a special case of degeneracy, following rule 001.
ListStepPlots, for Post’s Tag System.
Binary function, finds the binary generations of all generation plots like Tag System 2.
Binary function, finds the binary generations of all generation plots like Tag System 2.
AllGenerationPlots “generational” plots of binary tag systems.
Tag System 4.
Owing to the completely arranged regularity of the rules aside from 00->110, Tag System 4 is designed to essentially represent a single-way graph for which two time steps demonstrate the accumulation of the prerequisites for 00->110.
Tag System 5.
Quite literally, string re-writing. The labels indicate the length 3 of the string, for instance starting with 010 of length 3, then to 101, then 100.
Sub-section GraphDistanceMatrix.
Sub-section GraphDistanceMatrix.
The Temperature Plot of an initial condition for all Tag System 5 Graph Distance Matrices.
String inversion allows the formation of cycles in 3-dimensional space.
Graph Distance Matrix Tag System 4.
Section 2. Descriptions of the Functions.
Section 2. Descriptions of the Functions.
The AllGenerationPlotsBinary function.
The AllGenerationPlots function.
The NestGraphTagged function.
Evaluate one rule, such as Tag System Rule 3, over all initial conditions.
Evaluate one rule, such as Tag System Rule 3, in text.
Evaluate all Temperature Plots for Tag System 3.
Compare behaviors of different paths.
Compare behaviors of different paths.
ListLinePlot of Lengths.
Branchial Graphs.
Branchial graph for the tag system with 4-complete and 5-complete cycles.
...00......000
...10......010
...01......10
...11......111
101
...10......010
...01......10
...11......111
101
Even though we're trying to generate a sequence of 11...1 it seems that the multi-way tag system initial condition value of 101 allows the tag system to, due to the multi-way nature of the plots, alternatively push the existing 1s further up the graph with the application of the 00 rule that is the first rule (once a second 0 is generated by ...10......010 and ...01......10 or combine the two into a staggered 010 or alternatively, 10 plot in which we generate something that looks like a staircase... the multi-way characteristic is coming from the distributed stag system with left___.
Concluding remarks.
Concluding remarks.
Keywords.
Keywords.
◼
Post Tag System
◼
String Rewriting
◼
Multi-Way & One-Way
Acknowledgment.
Acknowledgment.
Props go to James for being such a kind mentor; and Stephen Wolfram defining the direction of this project toward methodically working upward. And to Post for providing the principal tag system.
References.
References.
1
.Mentor James Boyd, for teaching us all about Mathematica and keyboard shortcuts to add real arrows, and functional programming. It is James who has demonstrated the greatest passion for entailment cones, for multi-way computation tag systems, and for having us make team meetings which really kept the project going.
2
.Consultant Nik Murzin, whose generation of TwoWayMultiReplace and the functions needed to complete this project has been nothing less than instrumental because Nik provides the scope and options for our functions, such as TwoWayMultiReplace, Identity, Uniquify, Canonicalize, and KeyMap associations in .m nonetheless. His contributions range from Utilities, TwoWayRule, SubexpressionPositions, String Rewriting with or without documentation, SubexpressionPositions, Quantifiers, MultiReplace, Nik is the one who likes the bi-directional stuff like MultiReplace, MultiCoReplace, MultiBiReplace, and he has been a cornerstone of Metamathematics, Legacy, and Inference. He actually understands how the Mathematica kernel works!
3
.My team Aritra, Lukasz, Utkarsh, James, Nik, Richard, Jonathan, for their contributions to MultiwaySystem, equational logic, axiomatic theory, and equation proofs. When they are not building the kernel, they are building things like Graph, LinkedHypergraph, Multicomputation, MulticomputationLoader, MulticomputationMain, MultiStringReplace, Utilities, and WFR. It’s the notion of Tuples, HoldTuples, MatchSubstitutions, which are so important for focusing on tag systems and allowing the tag system rules to be applied anywhere in the current string. Thank you Utkarsh for explaining how sequentiality works so we didn’t think the past history had bearing on the result of applying the tag system at any given time.
4
.American Journal of Mathematics 1943-04: Vol 65 Iss 2 : Free Download, Borrow, and Streaming : Internet Archive
https://archive.org/details/sim_american-journal-of-mathematics_ 1943-04_ 65_ 2/page/202/mode/2up
https://archive.org/details/sim_american-journal-of-mathematics_ 1943-04_ 65_ 2/page/202/mode/2up
5
.After 100 Years, Can We Finally Crack Post’s Problem of Tag? A Story of Computational Irreducibility, and More—Stephen Wolfram Writings
https://writings.stephenwolfram.com/2021/03/after-100-years-can-we-finally-crack-posts-problem-of-tag-a-story-of-computational-irreducibility-and-more/#connecting-to-number-theory
https://writings.stephenwolfram.com/2021/03/after-100-years-can-we-finally-crack-posts-problem-of-tag-a-story-of-computational-irreducibility-and-more/#connecting-to-number-theory