Since the number of possible rules for a simple 2-D Turing machine, even one with only 2 states and 3 colors, exceeds 10 billion, it is impossible to traverse all the results of the Turing machines implementing all the rules. Therefore, I found it necessary to develop a system that could classify the results of the Turing machines and then use machine learning to find the relationship between the rules and this classification of the Turing machines. Using this system, the result of the Turing machine can be predicted without actually running it. In the following section, a classification function was constructed based on the density of “black cells”, as well as some other patterns, in the result of the Turing machine. Then, a predicting function is constructed that learns the relationship between rules and the classification result of the Turing machines. Also, an interesting phenomenon was found: as the number of states of the Turing machine increase, the possibility of having more complex, chaotic result increase.
Introduction
Introduction
A Turing machine is an abstract machine that can do calculations following certain rules. It has four parts. First, an infinite matrix (representing the “data”) Second, a head. The head can move around the matrix, changing the value stored in the matrix. Third, a state register. The state register can record the current state of the Turing machine. Last, there is a set of rules. Rules are instructions of how the Turing machine changes its state and values stored in the matrix. Here is the code to run and show an example of a Turing machine:
In[]:=
ic={1,{{{}},0}};steps=300;rule={{1,0}{2,1,{0,1}},{1,1}{2,0,{0,-1}},{2,0}{4,1,{0,-1}},{2,1}{3,0,{0,1}},{3,0}{1,1,{-1,0}},{3,1}{2,1,{0,1}},{4,0}{3,1,{0,-1}},{4,1}{2,0,{1,0}}};ArrayPlot@TuringMachine[rule,ic,steps][[-1,-1]]
Out[]=
The line “TuringMachine[rule,ic,steps]” returns a list of matrices that record the result of the Turing machine from step 1 to step 300. (Step refers to how many times of rules have been implemented.) And “TuringMachine[rule,ic,steps][[-1,-1]]” would output the last matrix of the list representing the latest matrix, which we call the “result” of the Turing machine after implementing the same sets of rules for 300 times. “ic” is the initial condition of the Turing machine. It contains two pieces of information. One, the “1” inside “ic” represents the initial condition of the state. Two, “{{{}},0}” represents the initial condition for the matrix. The rule of the Turing machine is a list of sub-rules. Take one of the sub-rule above as example, “{1,0}->{2,1,{0,1}}”. “{1,0}” on the left means the current state and value of the Turing machine and “2,1” means the state and value of the matrix that the head are pointing after implementing the rule. “{0,1}” means after implementing such a rule, the movement of the head.
Turing machine rules generator
Turing machine rules generator
In the documentation of the Turing machine, each of the rules are assigned with a number so that it can be called without an explicit format. However, when it comes to classifying the Turing machine, it is meaningless if the input is just a number. For example, if rule 5 and rule 7 were classified into one group according to the similarity of those two result of Turing machine. However, we can gain no understanding about how rules might affect the result to Turing machine because "rule 5" and "rule 7" are just two different strings. Therefore, it is necessary to have a function that could output the all combination of rules of Turing machine given the value of states number and colors number. There is a built-in function called "ComputationalSystemRules" which can returns an explicit set of rules for the computational system such as Turing machine. However, ComputationalSystemRules does not parse system specifications beyond those acceptable to RulePlot. Since Turing machine with multiple colors and number of states are not acceptable to RulePlot, there does not have any built-in function that can return the explicit rules for Turing machine with multiple colors and number of states, so I have to develop a function that do so.
In[]:=
rules[s_,k_]:=Module[{a,w,move,original,final}, a=Flatten[Table[Table[{i,j},{i,s}],{j,0,k-1}],1];(*generating all possible sub-rules given the number of states and colors*) w=s*k; move={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};(* all the possible movement of the head*) original=Flatten[Table[{i,j},{i,s},{j,0,k-1}],1]; a=Flatten[Table[Append[a[[i]],move[[j]]],{i,w},{j,8}],1];(*creating the right part of the rules*) final=Flatten[ToExpression[StringJoin[Table["Table[",{w}]]<> "{"<>StringDrop[StringJoin@Table["original[["<>ToString[i]<> "]]->"<>"a"<>"[["<>"k"<>ToString[i]<>"]],",{i,w}],-1]<> "}"<>StringJoin[Table[",{k"<>ToString[i]<>","<>ToString[8*w]<>"}]",{i,w}]]],w-1]](*permutating all the possible sets of rules*)
Basically, the code above is doing permutation and combination such that all possible rules can be returned. However, when I tried to run "rules[3,2]", I realized that it would return a list whose length is more than ten billion because in , the number of rules can be calculated using: . Therefore, this function is not that useful in my case for the poor performance of my computers.
2D -state, -color machines
s
k
(8sk)^(sk)
Random rule generator
Random rule generator
Adding some modification on the Turing machine rules generator, the random rule generator would generate random rule of Turing machine given the number of states and colors. This function is very useful in the classification of the Turing machine because I could make Monte Carlo simulation of the Turing machine system.
In[]:=
randomRule[s_,k_]:=Module[{a,w,move,original},a=Flatten[Table[Table[{i,j},{i,s}],{j,0,k-1}],1]; w=s*k; move={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}}; original=Flatten[Table[{i,j},{i,s},{j,0,k-1}],1]; a=Flatten[Table[Append[a[[i]],move[[j]]],{i,w},{j,8}],1]; Sequence@@@Table[{i,j}a[[RandomInteger[{1,Length[a]}]]],{i,s},{j,0,k-1}]]
In[]:=
randomRule[4,2]
Out[]=
{{1,0}{3,1,{1,0}},{1,1}{2,1,{0,1}},{2,0}{2,1,{1,0}},{2,1}{3,0,{1,-1}},{3,0}{2,1,{-1,0}},{3,1}{2,1,{0,1}},{4,0}{1,1,{0,-1}},{4,1}{3,1,{1,1}}}
Classification of Turing machine
Classification of Turing machine
Criteria
Criteria
In[]:=
FeatureSpacePlot[Table[ArrayPlot@TuringMachine[randomRule[4,2],{1,{{{}},0}},50][[-1,-1]],{4000}]]
Out[]=
By generating four thousand Turing machines with different rules implemented, I found that generally there are four classes of results.
"Line",
"Most cell are blank",
"repetitive graph",
"chaotic"
Summarizing the four classes of results of Turing machines, three main criteria could categorize them:
1. density of the black cell
2. if the pattern of the matrix is a line
3. repetitive of the pattern
1. density of the black cell
2. if the pattern of the matrix is a line
3. repetitive of the pattern
Criteria 1: density of the black cell
Criteria 1: density of the black cell
The reason why criteria 1 changed from “ the sum of all the element over the dimension of the matrix” to the density of the black cell is that only two colors would be considered in my project in order to reduce the dimension that the classification system should consider. By adding up all the elements in a matrix and divided by the product of dimension of the matrix, the density of the black cell can be attained because the element of the matrix would only be 1 or 0.
In[]:=
findDensity1[num_]:=Module[{densitys,rulelist,arrays}, rulelist=ParallelTable[randomRule[100,2],{num}];(*generating the a list of rules *) arrays=Table[TuringMachine[rulelist[[i]],{3,{{{1,0,1,1},{0,1,0,1}},0}},200][[-1,-1]],{i,Length[rulelist]}];(*generating a list of result of Turing machines implementing rulelist above*) densitys=(( Total[Total[#]]/Times@@Dimensions[#])&)/@arrays(*calculating the black cell density of the array above*)]
Criteria 2: if the patterns of the matrix is a line
Criteria 2: if the patterns of the matrix is a line
After generating 4000 random Turing machine, I found that 88% of those results are in shape of line. Therefore, instead of developing a function that could detect the shape of the graph, I should define an index that could differentiate different result of Turing machine whose shape is a line.
In[]:=
findLineWidth[m_List]:=Module[{w,widths,rows,r,test1,test2}, w=If[Length[m]<10,"not",Take[m,{Floor[Length[m]/2]-3,Floor[Length[m]/2]+3}]];(*take the middle six row of matrix*) r=If[Length[Transpose@m]<10,"not",Take[Transpose@m,Floor[Length[Transpose@m]/2]-3, Floor[Length[Transpose@m]/2]+3]];(*take the middle six column of matrix*) widths=If[w==="not","not",Table[Total@w[[i]],{i,Length[w]}]];(*count the element in each row*) rows=If[r==="not","not",Table[Total@r[[i]],{i,Length[r]}]];(*count the element in each column*) test1=If[TrueQ[Length[FindRepeat[widths]]<Length@widths],Mean[widths],0];(*find repetition in "width"*) test2=If[TrueQ[Length[FindRepeat[rows]]<Length@rows],Mean[rows],0];(*find repetition in "rows"*) If[Max[test1,test2]≥ 0.1&&Min[test1,test2]≥ 0.1,Min[test1,test2],If[Max[test1,test2]≥ 0.1 &&Min[test1,test2]< 0.1,Max[test1,test2],"not"]]]
If the graph of the result of the Turing machine is a line, it must have two properties: 1. the line would pass through the middle part of the matrix; 2. in each row or column, the numbers of element "1" should be generally the same. Combining those two properties, the function that judge if the graph of result of Turing machine is a line and returns the "line width" could be attained.
Criteria 3: repetitive of the pattern
Criteria 3: repetitive of the pattern
When function "findLineWidth" determines whether the results of the Turing machine is a line, those results classified as "not" are divided into two groups: "chaotic" and "repetitive".
Combining all the criteria and classify all Turing machine accordingly
Combining all the criteria and classify all Turing machine accordingly
Here is the procedure of classifying the results of Turing machine.
Prediction of classes
Prediction of classes
In predicting the classes of results of Turing machine implementing certain rules, a neuron network should be trained to take rules as input and output the class of the results: "blank", "line", "repetitive", and "chaotic". And there should be a predicted line width in the class “line” as well.
The function below would generate a list of random rules, return a list of results of Turing machine implementing such rules, and then classify those results into the four classes. In this way, connection between rules and classes have been built. Therefore, I could train neuron network using connect between rules and classes to predict the class given certain rules.
Here are four steps to develop prediction function:
Here are four steps to develop prediction function:
1. Generating rules and results of Turing machine
1. Generating rules and results of Turing machine
2.Classify the results of Turing machine into the four classes
2.Classify the results of Turing machine into the four classes
3. Transforming rules into matrix
3. Transforming rules into matrix
4. Constructing dataset and training class predicting function
4. Constructing dataset and training class predicting function
5. Constructing dataset and training line width predicting function
5. Constructing dataset and training line width predicting function
When the result of the Turing machine is a line, the "findLineWidth" function could not only judge if the result is a line but also the calculate the width of the line. Therefore, after class predicting function "pc" predicts certain rules into class "line", a line width predicting function should also predict the line width of the results of Turing machine implementing such rules.
6. Combining all the steps above into one function
6. Combining all the steps above into one function
Interesting finding
Interesting finding
Generating 50000 Turing machines from 2 states to 102 states, the ratio of numbers of complex Turing machines to the states number is close to 20.8291 and the graph between numbers of complex Turing machine and states is a line, which is out of my imagination.
Conclusion
Conclusion
Keywords
Keywords
◼
Turing machine
◼
Machine learning
◼
Monte Carlo simulation