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[]=

Turing Machines with Greater Head Jumps

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

Custom Modeling Turing Machines with Greater Head-Jumps

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

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

Use the extracted data to create a custom RulePlot

Modeling the Rules of All the Turing Machines given Above

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

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

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

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

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

Modeling Turing Machines with Greater Head-Jumps

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

Graph Relation Between Different Turing Machines States

Modeling the Relationship between different Rules Via Graphs

Create a list containing the consecutive rules for a given Turing Machine:

Graph the subsequent relationship in a graph:

Graphing the Relationship of the Rules for the Turing Machines Given above

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

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

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

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

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

Significance of the Graph Analysis

Following the Head Movement of the Turing Machine

Only highlight the locations in the array-plot where the head has passed:

Modeling the Head-Movement of all the Turing Machines

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

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

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

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

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

Significance of following the Head-Movement

Graphing the net Displacement throughout Time

ListLinePlot the net displacement of the Head-Movement:

Modeling the Head Movement of the Turing Machines

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

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

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

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

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

Significance

Causal Graph and 3D Causal graphs

Create a Causal graph for Turing Machine:

Create a 3D Causal Graph of the Turing Machine:

Modeling 3d and 2d Causal Graphs of Turing Machines Mentioned Above

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

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

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

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

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

Significance of the Causal Analysis

Conclusion and Extension

Work Cited

nesoacademy, nesoacademy. “Turing Machine - Introduction (Part 1).” YouTube, YouTube, 3 Sept. 2017, www.youtube.com/watch?v=PvLaPKPzq2I.

Wolfram, Wolfram. “TuringMachineCausalGraph: Wolfram Function Repository.” TuringMachineCausalGraph | Wolfram Function Repository, Wolfram, 2021, resources.wolframcloud.com/FunctionRepository/resources/TuringMachineCausalGraph/?i=TuringMachineCausalGraph&searchapi=https%3A%2F%2Fresources.wolframcloud.com%2FFunctionRepository%2Fsearch.

Wolfram, Wolfram. Wolfram 2,3 Turing Machine Research Prize: Technical Details, Wolfram, 2007, www.wolframscience.com/prizes/tm23/technicaldetails.html.

Wolfram, Stephen. A New Kind of Science. Wolfram Media, 2019.