Message Boards

GROUPS:

Staff Picks Wolfram Science Computer Science Graphics and Visualization Graphs and Networks Wolfram Language Wolfram High School Summer Camp

Gooha Park

[WSC21] Turing machines with longer head-jumps and complexity

Gooha Park

Posted 3 months ago

699 Views

3 Replies

8 Total Likes

Follow this post

Causal Graphs For Turing Machines with Greater Head-Jumps

Turing machines with longer head-jumps and complexity
by Gooha Park

Introduction

Turing Machine is a rudimentary computational device developed by Alan Turing in 1936.

This computational essay will investigate Turing Machines with longer head-jumps and their relation to complexity. Various qualities and aspects of Turing Machines with Longer head jumps will be represented through extensive visualizations. Ultimately, the essay will attempt to argue that Turing Machines with longer head-jumps are capable of displaying complex behavior.

Introduction to Turing Machines

The Turing machine consists of an apparatus called a “Head” which is capable of reading and writing characters. Prior to functioning, a systematic rule is encoded inside the Turing machine and the machine is placed on a linear tape. When the machine is placed on the tape, the "Head" starts moving on a linear tape and fills the tape with characters

Show the Rules For a Given Turing Machine:

In[]:=

RulePlot[TuringMachine[2506]]

Out[]=

Looking above, one will be able to see the rules that define a Turing Machine. In the wolfram language, 4 elements consist to define a distinct rule for a Turing Machine: colors, state, displacement, and the rule number. The first element is its possible head-states. The head-state is described by the direction of the black pointer. Looking at the diagram, clearly there are only two head states: up and down. The second element is the total number of color. In the Wolfram Language, instead of inputting characters on a linear tape, colors are encoded on the tape. In the example, there are two colors: white and orange. The third element is the displacement, a terminology denoting the head movement of the machine. In the RulePlot above, as the Turing Machine moves to its next stage, the head either moves one to the left or right: thus the displacement of this particular Turing Machine is one. If all three elements are specified, a total of (2*state*color*displacement)^(state*color) distinct rules can be made. Each rule gives a different combination of colors, states and displacement.

Diagram for a Turing Machine after 60 evolutions:

In[]:=

RulePlot[TuringMachine[2506],{1,{{},0}},60]

Out[]=

The explanation above might be daunting if one has never seen the operation of a Turing Machine. Looking above, one will see a Turing Machine that has filled out an empty tape after 60 evolutions. As the Turing Machine experiences an increase in its evolution, the white cells are filled. The increase in evolution is represented by the vertical expansion of the diagram. Thus, if one wanted to know what the linear tape looked like after time A, one would have to vertically move down A steps. After locating A steps down, the entire horizontal row would correspond to the state of the tape.

What is Complexity and why is it relevant to Turing Machines?

Complexity commonly refers to a system manifesting intricate, complicated, and perhaps irregular behavior. With this basic definition, Stephen Wolfram has conducted studies on complex behavior. In these studies, he has argued against the common intuition that the creation of complex behavior require complex instructions and processes. Instead, he argues that complex behavior can be created through iterating simple rules.

Show the Rules for CellularAutomaton Rule 30

In[]:=

RulePlot[CellularAutomaton[30]]

Out[]=

Show the result of running this rule for 200 Iterations

In[]:=

ArrayPlot[CellularAutomaton[30,{{1},0},200],ImageSize750]

Out[]=

The image above shows the result of repeating cellular automaton 30 for 600 iterations. I hope we can all agree that the pattern displayed above is profoundly complex. Interestingly, the rules that constitute this pattern is quite simple. In that light, I hope we can see the connection between Turing Machines and complex behavior. Like cellular automaton, Turing machines operate on very basic rules that manipulate its movement. The greater significance is that when we observe the pattern plotted by Turing machines over long periods of time, Truing Machines are also capable of demonstrating complex behavior.

Rules for a Turing Machine with a Rule Number of 596 440, 2 States, 3 Colors and a displacement of 1 and its final results

In[]:=

RulePlot[TuringMachine[{596440,2,3}],ImageSize450]RulePlot[TuringMachine[{596440,2,3}],{1,{{},0}},700,ImageSize100]

Out[]=

The image above shows a 2 state, 3 color Turing machine with a displacement of 1 and a rule number of 596,440. The core constituents of this Turing Machine are 6 simple rules. Yet, from these simple patterns, we can create complex and interesting patterns.

Turing Machines with Greater Head Jumps

When we look at existing studies on the behavior of Turing Machines - at least those concerning the notion of complexity - there has been scarce effort to analyze machines with displacements larger than one. To visualize the behavioral pattern of Turing machines with greater head-jumps, let us look at a rule for a Turing machine with displacement of 1.

RulePlot for a standard Turing Machine with a Rule number of 2506, 2 colors, 2 states, and a displacement of 1

In[]:=

RulePlot[TuringMachine[2506]]

Out[]=

In this example, the Turing machine clearly has a displacement of 1. For this rule to qualify as a Turing machine with greater head-jumps, the displacement of the Turing machines would have to have absolute values greater than one.

Custom Modeling Turing Machines with Greater Head-Jumps

As I was analyzing Turing Machines with greater head-jumps, I encountered a major issue: the function RulePlot did not return a visualization of the rules. I deemed this problematic because it seemed queer to start analyzing Turing Machines without knowing their fundamental rules. Thus, I decided to create a custom visualization which would follow a similar format to the Rule-Plot function.

Generate a list that encodes the vital information of a Turing Machine

ORGlistTuring[tnum_Integer,st_Integer,CI_Integer,Dx_Integer,Rp_Integer]:=Flatten[TuringMachine[{tnum,st,CI,Dx},{1,{{},0}},Rp*3],1]

The first step of the process was creating a function that produced the most standard information of a Turing Machine: its current state, position of the head, and the values that are encoded on the linear tape.

In[]:=

ORGlistTuring[2506,2,2,1,5]//Short

Out[]//Short=

{{1,4,0},{0,0,0,0,0,0,0},{2,5,1},{0,0,0,1,0,0,0},24,{1,2,-2},{0,1,1,0,1,0,1},{2,1,-3},{0,0,1,0,1,0,1}}

To illustrate its role, I ran the function to see what a Turing Machine with 2 colors , 2 states , displacement of 1, and a rule number of 2506 would produce for 5 evolutions. Although this information wasn't exactly what I needed to visualize the rules of the Turing machine, it provided a good source material to produce what I needed. After obtaining the “raw data” of the Turing machine, I used the “ORGRulePlot” function to extract the data I needed.

Extract Key information from the list above: head state, displacement, color

ORGRulePlot[ind_Integer,lst_List]:=DeleteDuplicates[Table[If[j==1,lst[[2*i-1,1]],If[j==2,lst[[2*i+1,1]],If[j==3,lst[[2*i+1,3]]-lst[[2*i-1,3]],If[j==4,If[i==1,0,lst[[2*i,lst[[2*i-1,2]]]]],If[j==5,lst[[2*i+2,lst[[2*i-1,2]]]],0]]]]],{i,ind},{j,5}]]

The "ORGRulePlot " function first receives the basic data generated from the ORGlistTuring function. Then, the function creates a sublist with 5 elements for every evolution the Turing Machine goes through. The five elements of the ORGRulePlot function follows the order of (original head state, next head state, displacement, original value on the tape, and the second value encoded on the tape). Depending on what the user specifies for the ind variable of the function, the function finds the rule for ind evolutions. Since the rules of Turing Machines are in a closure, - the Turing Machine can not exceed a certain set of rules - if the function is computed for a sufficient evolution, the "DeleteDuplicate" function is able to find all the distinct rules.

Use the extracted data to create a custom RulePlot

plotTM[reflist_List]:=Table[{Grid[Table[If[i==1,Item[reflist[[k,1]],BackgroundIf[reflist[[k,4]]==0,White,If[reflist[[k,4]]==1,Orange,If[reflist[[k,4]]==2,Green],If[reflist[[k,4]]==3,Blue]]]],If[i==2,Item[reflist[[k,2]],BackgroundIf[reflist[[k,5]]==0,White,If[reflist[[k,5]]==1,Orange,If[reflist[[k,5]]==2,Green],If[reflist[[k,5]]==3,Blue]]]],0]],{i,2},{j,1}],Frame->All],NumberLinePlot[Interval[{0,reflist[[k,3]]}]]},{k,1,Length[reflist]}];

With the information provided by the "ORGRulePlot" function, the "plotTM " function returns a custom visualization. Since the ORGRulePlot function returns the 2 head states, 2 values on the linear tape, and the displacement, the remaining job was to sensibly visualize the data. In the custom visualization, there are two cells vertically stacked and each cell contained a number and a color. The number represented the head state and while the color represented the data encoded on the linear tape. Next to the two cells was a number line which provided the displacement of the head.

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[2506,2,2,1,900]]]

Out[]=

The example above provides a Rule-Plot for a Turing machine with a rule number of 2506, 2 states, 2 colors, and a displacement of 1. If one compares this to the standard Rule-Plot for the same Turing Machine, one will see that both results are identical.

Modeling the Rules of All the Turing Machines given Above

2 State, 2 Color, Displacement range of -2 to 2

In[]:=

ArrayPlot[Last/@TuringMachine[{2981,2,2,2},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[2981,2,2,2,900]]]

Out[]=

2 State, 2 Color, Displacement ranging from -3 to 3

In[]:=

ArrayPlot[Last/@TuringMachine[{13080,2,2,3},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[13080,2,2,3,900]]]

Out[]=

In[]:=

ArrayPlot[Last/@TuringMachine[{12798,2,2,3},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[12798,2,2,3,900]]]

Out[]=

2 State, 2 Color, Displacement ranging from -4 to 4

In[]:=

ArrayPlot[Last/@TuringMachine[{23498,2,2,4},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[23498,2,2,4,900]]]

Out[]=

2 State, 3 Color, Displacement ranging from - 2 to 2

In[]:=

ArrayPlot[Last/@TuringMachine[{207892,2,3,2},{1,{{},0}},3000],ImageSize150]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[900,ORGlistTuring[207892,2,3,2,900]]]

Out[]=

2 State, 4 color,Displacement ranging from -3 to 3

In[]:=

ArrayPlot[Last/@TuringMachine[{500010902,2,4,3},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[2000,ORGlistTuring[500010902,2,4,3,2000]]]

Out[]=

In[]:=

ArrayPlot[Last/@TuringMachine[{500010908,2,4,3},{1,{{},0}},400]]

Out[]=

In[]:=

Grid@plotTM[ORGRulePlot[2500,ORGlistTuring[500010908,2,4,3,2500]]]

Out[]=

Modeling Turing Machines with Greater Head-Jumps

After understanding the basic qualities of Turing Machines and the notion of complexity, my first step in the project consisted of finding interesting Turing machines that displayed complex behavior. To do this, I designed a function that produced the possible Turing Machines for the corresponding total number of colors, states, and displacement.

Generate an array of Turing Machines that matches the user-specified information:

In[]:=

ArrayTm[s_Integer,c_Integer,dx_Integer,evo_Integer,n1_Integer,n2_Integer]:=Table[ArrayPlot[Last/@TuringMachine[{x,s,c,dx},{1,{{},0}},evo]],{x,n1,n2}]

To use the function, the user first defines the total number of states, color, and the maximum possible displacement. After defining these key elements the user defines the range of rules. What this means is that if I input 2,2,3 - for the variable "color, state and dx" - the function will produce a Turing machine with 2 states, 2 colors and a displacement ranging from -3 to 3. If I write 20,000 and 20,100 for n1 and n2, the function will provide the all the corresponding models in the range.

In[]:=

ArrayTm[2,2,3,70,10183,10200]

Out[]=





Looking above, we can see how the function can be used to see the various Turing Machine models. This was the most repetitive and time-consuming part of the project because the total possible number of Turing Machine rises at an exponential rate when I increased either the color, state or displacement. Furthermore, within the few thousand to few million possible variations, only few of the models exhibited complex and interesting behavior. Many of the rules did not produce any behavior or was a repetition of previous models.

Graph Relation Between Different Turing Machines States

Modeling the Relationship between different Rules Via Graphs

After modeling the rule for respective Turing Machines, the first step of my analysis started with observing the relationship among the different sub-rules of the Turing Machine. To be more specific, I wanted to see how the Turing Machine changed its rule-state as it went through an increase in its evolution. To model this, I brought back two functions I used in the previous section:"ORGlistTuring" and "ORGRulePlot".

ORGlistTuring[tnum_Integer,st_Integer,CI_Integer,Dx_Integer,Rp_Integer]:=Flatten[TuringMachine[{tnum,st,CI,Dx},{1,{{},0}},Rp*3],1]

The two func