Traditional Turing machines generally operate on a standard 1-dimensional, bidirectional tape with predictable constraints. In this project, I aim to extend the definition of the Turing machine tape beyond these constraint to abstract graphs, ultimately generalizing the machine’s architecture to be completely independent of its underlying tape structure. My primary objective in this project is to create algorithms which fully traverse and visualize the traversal of each of these abstract graphs.
To study the traversal of graphs using Turing machines, I investigate five distinct graph topologies: 1-dimensional unidirectional tapes, 1-dimensional bidirectional tapes, 2-dimensional grid graphs, cyclic graphs, and binary trees. Furthermore, the project explores the patterns surrounding the specific Turing machine configurations necessary to successfully execute these traversals.
Based on these observed patterns, I establish a theorem regarding the maximum upper-bound of colors required for a 2-state Turing machine to traverse any N-ary tree graph tape.
To study the traversal of graphs using Turing machines, I investigate five distinct graph topologies: 1-dimensional unidirectional tapes, 1-dimensional bidirectional tapes, 2-dimensional grid graphs, cyclic graphs, and binary trees. Furthermore, the project explores the patterns surrounding the specific Turing machine configurations necessary to successfully execute these traversals.
Based on these observed patterns, I establish a theorem regarding the maximum upper-bound of colors required for a 2-state Turing machine to traverse any N-ary tree graph tape.
Introduction
Introduction
A Turing machine is a simplistic mathematical model of a computer invented by Alan Turing in 1936 as an abstract concept to describe computation. Turing described this machine to consist of a “tape” represented as an infinite strip of cells containing symbols from some fixed alphabet, A, and a machine “head” capable of being in a finite number of states, Q. The alphabet is considered to contain a designated blank symbol, which is spread across all but finitely many cells at the outset.
A illustration of a Turing machine using a bidirectional tape containing the symbols 1 and 0 (Stern, 2000)
The tape used by a typical Turing machine is visualized as 1-Dimensional and infinite. Thus, a traditional 1-Dimensional bidirectional-tape Turing machine may be defined as a 3-tuple consisting of the number of states (which must be finite), number of symbols (which must be finite), the number of directions available for the head on the tape, and a transition function mapping the current state and the current symbol to a new state, a new symbol, and a direction to move towards.
For example, a traditional Turing machine, which always has two directions, with 4 states and 2 colors may be written as (4,2)-TM.
For example, a traditional Turing machine, which always has two directions, with 4 states and 2 colors may be written as (4,2)-TM.
This project generalizes the concept of a Turing machine’s tape such that the head is free to move on a more general graph-tape in some fixed number of directions which may exceed the tradition limit of 2. An example would be a 2-Dimensional grid-graph tape, in which there are 4 possible directions (Up, Down, Left, and Right) at any given point on the tape as compared to the 2 possible directions on the traditional bidirectional tape.
The Turing machine also contains a Transition function which is responsible for transforming the symbol α currently read by the head and the head state q into: the next symbol α’ to be written at the current tape position, the next head state q’, and the direction to be taken by the head to reach the next position on the tape.
The Transition Function works by using a ruleset, which is the set of actions needed to be taken by the Turing machine given any state and symbol. In this essay, I will be dealing strictly with deterministic Turing machines. A deterministic Turing machine ensures that all 2-tuples of (CurrentState, CurrentSymbol) have one unique action associated with them, while a non-deterministic Turing machine gives a set of possible actions. This ruleset allows us to directly encode algorithms into the Turing Machine through the creation of custom transition functions. It should be noted that the transition function does not have any global knowledge of the underlying tape beyond the number of legal directions to be taken from any position, which is assumed to be a constant value throughout the tape. This separates the transition function from the geometry of the tape. The machine chooses a direction, while the graph determines what that direction means.
In this essay, I generalize the definition of Turing machines by allowing the head to move along an arbitrary graph instead of a simple, linear tape.
In order to make the transition function applicable to these abstract graphs, I restrict my study to graphs which every vertex has the same out degree, even if this means there exist edges that point to the vertex itself (eg. the leftmost cell in a unidirectional tape or the top node of a binary tree). I also consider cases in which the graph is finite. However, this reduces the capabilities of a general Turing Machine to a finite state machine.
A typical problem in Graph simulations is the traversal of all nodes on a graph. Therefore, one question that arises from the use of abstract graphs on Turing machines is how can one write a program which can cover all nodes/cells on the tape. In this project, a “fully traversed” tape is defined to be one which is initially empty and where all nodes/cells have been assigned a non-zero symbol once the Turing machine has halted. In the special case of infinite graphs, it is required that every node be visited in some finite time, even though the machine will never halt.
Therefore, a graph-tape abstraction may allow us to explore interesting properties of these graphs, as we are attempting to perform actions like traversal with the extremely limited information typical of a Turing machine.
To generalize Turing machines on graphs, I abstract the essential properties of the underlying tape by replacing the 1-dimensional tape with a more general graph. I consider this new graph to have the property that all nodes have the same number of directions. I will refer to such an object as a “Turing graph” which consists of a starting state, a number of valid directions, and a function that takes a position and a direction and returns the location in that direction.
To begin, I examine this problem statement for several specified graphs and geometries, and then address the generalization of the Turing machine and the transition function to be independent of the graph-tape assuming a still constant number of legal directions at any point on the tape.
The Turing machine also contains a Transition function which is responsible for transforming the symbol α currently read by the head and the head state q into: the next symbol α’ to be written at the current tape position, the next head state q’, and the direction to be taken by the head to reach the next position on the tape.
The Transition Function works by using a ruleset, which is the set of actions needed to be taken by the Turing machine given any state and symbol. In this essay, I will be dealing strictly with deterministic Turing machines. A deterministic Turing machine ensures that all 2-tuples of (CurrentState, CurrentSymbol) have one unique action associated with them, while a non-deterministic Turing machine gives a set of possible actions. This ruleset allows us to directly encode algorithms into the Turing Machine through the creation of custom transition functions. It should be noted that the transition function does not have any global knowledge of the underlying tape beyond the number of legal directions to be taken from any position, which is assumed to be a constant value throughout the tape. This separates the transition function from the geometry of the tape. The machine chooses a direction, while the graph determines what that direction means.
In this essay, I generalize the definition of Turing machines by allowing the head to move along an arbitrary graph instead of a simple, linear tape.
In order to make the transition function applicable to these abstract graphs, I restrict my study to graphs which every vertex has the same out degree, even if this means there exist edges that point to the vertex itself (eg. the leftmost cell in a unidirectional tape or the top node of a binary tree). I also consider cases in which the graph is finite. However, this reduces the capabilities of a general Turing Machine to a finite state machine.
A typical problem in Graph simulations is the traversal of all nodes on a graph. Therefore, one question that arises from the use of abstract graphs on Turing machines is how can one write a program which can cover all nodes/cells on the tape. In this project, a “fully traversed” tape is defined to be one which is initially empty and where all nodes/cells have been assigned a non-zero symbol once the Turing machine has halted. In the special case of infinite graphs, it is required that every node be visited in some finite time, even though the machine will never halt.
Therefore, a graph-tape abstraction may allow us to explore interesting properties of these graphs, as we are attempting to perform actions like traversal with the extremely limited information typical of a Turing machine.
To generalize Turing machines on graphs, I abstract the essential properties of the underlying tape by replacing the 1-dimensional tape with a more general graph. I consider this new graph to have the property that all nodes have the same number of directions. I will refer to such an object as a “Turing graph” which consists of a starting state, a number of valid directions, and a function that takes a position and a direction and returns the location in that direction.
To begin, I examine this problem statement for several specified graphs and geometries, and then address the generalization of the Turing machine and the transition function to be independent of the graph-tape assuming a still constant number of legal directions at any point on the tape.
1-Dimensional Graph Tapes
1-Dimensional Graph Tapes
1-Dimensional Unidirectional Graph Tapes
1-Dimensional Unidirectional Graph Tapes
I begin by focusing on a simpler example: the 1-Dimensional unidirectional graph tape. In this context, the tape is assumed to extend infinitely in one direction, which I have chosen to be the rightwards. Since I assume that every position in the tape has the same valid number of directions, I make a convention for a 1-sided unidirectional tape that the leftmost cell reaches itself when one attempts to move further left. The algorithm used to traverse this tape is trivial, since the head can simply always move rightwards and “fully traverse” the graph.
This section of the essay also establishes several functions that will be used throughout this project. To begin, a constructor function is established in order to generalize the definition of Turing graphs for all the examples. Next, I define the Turing machine function, which provides the core framework for the Turing machine to use a given transition function in order to transform a given state and symbol into a new state, new symbol, and direction to be moved to. Finally, I define a Turing machine evolution function, which allows for the Turing machine function to be iterated repeatedly in order to traverse the entire graph.
This section of the essay also establishes several functions that will be used throughout this project. To begin, a constructor function is established in order to generalize the definition of Turing graphs for all the examples. Next, I define the Turing machine function, which provides the core framework for the Turing machine to use a given transition function in order to transform a given state and symbol into a new state, new symbol, and direction to be moved to. Finally, I define a Turing machine evolution function, which allows for the Turing machine function to be iterated repeatedly in order to traverse the entire graph.
rules1DU encodes the algorithm that traverses an empty, 1 -Dimensional unidirectional graph using a (2,2)-TM.
In[]:=
rules1DU=<|{1,1}->{1,1,1},{1,0}->{1,1,1},{2,1}->{1,1,1},{2,0}->{1,1,1}|>;
I create a constructor function to generalize the Turing graphs. This function takes mandatory input parameters of the machine’s starting position, number of available directions, a neighborhood function calculating the next position, and the machine tape. There is an additional optional parameter which takes the graph function of a tape (to be used in later sections upon the introduction of abstract graph tapes)
turingGraphBuilder is the Turing graph constructor function
In[]:=
turingGraphBuilder[start_,directions_,nbrFn_,labels_,graph_:None]:=<|"start"->start,"directions"->directions,"nbrFn"->nbrFn,"labels"->labels,"graph"->graph|>;
turingGraph1DU creates a 1-Dimensional unidirectional Turing graph which extends infinitely in the the rightwards direction, is initially blank, and has initial position 0 and initial state 2.
In[]:=
Clear[turingGraph1DU];turingGraph1DU=turingGraphBuilder[0,2,(#1+#2)&,<||>];
tmStep generalized for any given Turing graph, position, state, and set of rules. This function does not iterate, only running once and giving the new state of the machine head, symbol to be written at the current position, and direction to be taken by the machine.
In[]:=
tmStep[{turingGraph_,pos_,state_},rules_]:=Module[{check,newDirection,newSymbol,newState,updatedGraph,newPos},check=Lookup[turingGraph["labels"],Key[pos],0];If[!KeyExistsQ[rules,{state,check}],Return[{turingGraph,pos,state}]];newDirection=rules[{state,check}][[3]];newSymbol=rules[{state,check}][[2]];newState=rules[{state,check}][[1]];updatedGraph=ReplacePart[turingGraph,"labels"->Append[turingGraph["labels"],pos->newSymbol]];newPos=updatedGraph["nbrFn"][pos,newDirection];{updatedGraph,newPos,newState}]
evolveTM processes the Turing machine over a specified number of iterations/steps and operates on any given Turing graph, set of transition rules, initial head position, initial state.
In[]:=
evolveTM[turingGraph_,rules_,startPos_,startState_,maxSteps_:10]:=NestList[tmStep[#,rules]&,{turingGraph,startPos,startState},maxSteps]
history1DU stores history for 100 steps of the Turing machine on a 1 - Dimensional bidirectional graph tape
In[]:=
Clear[history1DU];history1DU=CloudGet[CloudObject[
https://www.wolframcloud.com/obj/54737f61-fcc7-4c13-81f8-cbfb8d2baeb7
]];To minimize computation time within this essay, I computed the history1DU function in the cloud, assigned the output to a cloud object, and referenced this cloud object in this essay.
The original expression was: history1DU=evolveTM[turingGraph1DU, rules1DU, 0, 1, 10];
visualizeTM1D displays the traversal of the Turing machine head specifically for the case of a 1D tape
visualizeTM1D[history_List]:=ListAnimateTableModule{currentGraph,currentPos,machinePath},currentGraph=history[[i,1]];currentPos=history[[i,2]];machinePath=history[[1;;i,2]];Graphics{Thick,Gray,Line[({#1,0}&)/@machinePath],Blue,PointSize[Large],Point[({#1,0}&)/@Keys[currentGraph["labels"]]],Red,PointSize[Large],Point[{currentPos,0}]},,{i,1,Length[history]},
Call the visualizeTM1D to display the Turing machine head (in red) traversing a 1-Dimensional unidirectional graph tape over 15 steps.
In[]:=
visualizeTM1D[history1DU]
Out[]=
1-Dimensional bidirectional Graph Tapes
1-Dimensional bidirectional Graph Tapes
This section of the essay focuses on 1-Dimensional bidirectional Turing graphs. In this context, the tape is said to extend infinitely in both directions (visually “leftwards” and “rightwards”). Unlike the previous example in which the machine head only moves in one direction, the machine head must now move both leftwards and rightwards. To do this, the machine head must continuously change directions. This is done by forcing the machine head to turn in the opposite direction once a node which a blank symbol is read.
The step-by-step operation of the algorithm that traverses an empty, 1-Dimensional bidirectional graph using a (2, 2)-TM can be outlined in pseudocode below:
1
. Move leftwards until a node with the blank symbol 0 is read
2
. Write 1 at this position and start moving rightwards.
3
.Move rightwards until a node with the blank symbol 0 is read
4
.Write 1 at this position and start moving leftwards
5
.Return to Step 1
rules1DB encodes the algorithm that traverses an empty, 1-Dimensional bidirectional graph using a (2,2)-TM.
In[]:=
rules1DB=<|{1,1}->{1,1,-1},{2,1}->{2,1,1},{1,0}->{2,1,1},{2,0}->{1,1,-1}|>;
turingGraph1DB creates a 1-Dimensional bidirectional Turing graph which extends infinitely in both the leftwards and rightwards direction, is initially blank, and has initial position 0 and initial state 2.
In[]:=
Clear[turingGraph1DB];turingGraph1DB=turingGraphBuilder[0,2,(#1+#2&),<||>];
history1DB stores history for 100 steps of the Turing machine on a 1-Dimensional bidirectional graph tape
In[]:=
Clear[history1DB];history1DB=CloudGet[CloudObject[
https://www.wolframcloud.com/obj/05cf1050-39bf-4b7c-b88d-fe992832ddaa
]];To minimize computation time within this essay, I computed the history1DB function in the cloud, assigned the output to a cloud object, and referenced this cloud object in this essay.
The original expression was: history1DB=evolveTM[turingGraph1DB, rules1DB, 0, 1, 10];
Call visualizeTM1D to display the Turing machine head (in red) traversing a 1-Dimensional bidirectional graph tape over 100 steps.
2-Dimensional Grid-Graph tapes
2-Dimensional Grid-Graph tapes
I will now focus on traversing a 2-Dimensional Grid-Graph Tape. In this context, the tape is assumed to extend infinitely in all 4 directions: upwards, downwards, leftwards, and rightwards. Since I must traverse the entire graph systematically, it is necessary to build an algorithm which covers all directions. I aim to do this through the use of a spiral extending infinitely outwards from the starting position.
Typically Turning Machines are described by the number of states and number of symbols. However, as an addition due to the establishment of new directions beyond a typical Turing machine tape, this essay will use a different convention for the notation of Turing machines, such that a Turing with Q states, N symbols, and F directions is written as (Q, N, F)-TM.
A significant challenge in creating the spiral using a naive (4,2,4)-TM is the lack of internal memory in the Turing machine. As a result, the machine head cannot determine exactly when to turn a corner on the spiral path without additional information. Consequently, the machine cannot rely solely on four states representing the four directions of movement.
This limitation is addressed by introducing four additional intermediate states, allowing the Turing machine to retain information about its previous move. Specifically, these states record whether the machine head’s last turn was successful, meaning it continued along the intended spiral path, or unsuccessful, meaning it followed a cyclic path instead of the outward-extending spiral. Therefore, the machine uses 8 states which are partitioned such that each of the four possible directions is associated with two states: a pure state, in which the machine is given no information beyond the direction in which it has just moved, and an impure state, in which the machine is given information about its previous move and the direction in which it must move next.
Typically Turning Machines are described by the number of states and number of symbols. However, as an addition due to the establishment of new directions beyond a typical Turing machine tape, this essay will use a different convention for the notation of Turing machines, such that a Turing with Q states, N symbols, and F directions is written as (Q, N, F)-TM.
A significant challenge in creating the spiral using a naive (4,2,4)-TM is the lack of internal memory in the Turing machine. As a result, the machine head cannot determine exactly when to turn a corner on the spiral path without additional information. Consequently, the machine cannot rely solely on four states representing the four directions of movement.
This limitation is addressed by introducing four additional intermediate states, allowing the Turing machine to retain information about its previous move. Specifically, these states record whether the machine head’s last turn was successful, meaning it continued along the intended spiral path, or unsuccessful, meaning it followed a cyclic path instead of the outward-extending spiral. Therefore, the machine uses 8 states which are partitioned such that each of the four possible directions is associated with two states: a pure state, in which the machine is given no information beyond the direction in which it has just moved, and an impure state, in which the machine is given information about its previous move and the direction in which it must move next.
The step-by-step operation of the algorithm that traverses an initially empty, 2-Dimensional grid graph tape using a (8, 2,4)-TM can be outlined in pseudocode below:
1
.Write 1 to the starting cell. Move rightwards and write 1 to the empty cell. Similarly, every time there is a rightwards movement, write 1 to the node at the new position and move downwards immediately afterwards.
2
.If the downwards node is already filled, change the internal state to right leaning and move back upwards. This means the head will now have the information that it must move rightwards after moving upwards. Continue Step 1 until a blank downwards cell is seen.
3
.If the downwards node is not filled, write 1 and move leftwards. Similarly, every time there is a downwards movement, write 1 to the node at the new position and move leftwards immediately afterwards
4
.If the leftwards node is already filled, change the internal state to downwards leaning and move back rightwards. This means the head will now have the information that it must move downwards after moving rightwards. Continue Step 3 until a blank leftwards cell is seen
5
.If the leftwards node is not filled, write 1 and move upwards. Similarly, every time there is a leftwards movement, write 1 to the node at the new position and move upwards immediately afterwards.
6
.If the upwards node is already filled, change the internal state to leftwards leaning and move back downwards. This means the head will now have the information that it must move leftwards after moving downwards. Continue Step 5 until a blank upwards cell is seen.
7
.If the upwards node is not filled, write 1 and move rightwards. Similarly, every time there is an upwards movement, write 1 to the node at the new position and move rightwards immediately afterwards.
8
.If the rightwards node is already filled, change the internal state to upwards leaning and move back leftwards. This means the head will now have information that it must move upwards after moving leftwards. Continue Step 8 until a blank rightwards cell is seen.
9
.Return to Step 1
rules2D encodes an algorithm that traverses an empty two-dimensional grid graph using an (8,2,4)-TM.
turingGraph2D creates a two-dimensional grid Turing graph that extends infinitely in all four cardinal directions, is initially blank, and has an initial head position of {0,0} and an initial state of 4. The neighborhood function uses arithmetic operations on coordinate lists to translate the machine head by one unit in any of the four defined directions.
history2D stores history for 100 steps of the Turing machine on a 1-Dimensional bidirectional graph tape
To minimize computation time within this essay, I computed the history2D function in the cloud, assigned the output to a cloud object, and referenced this cloud object in this essay.
The original expression was: history2D = evolveTM[turingGraph2D, rules2D, {0,0}, 1, 100];
visualizeTM2D displays the traversal of the Turing machine head specifically for the case of a 2D grid-graph tape
Call visualizeTM2D to display the Turing machine head (in red) traversing a 2-Dimensional grid-graph tape over 100 steps.
Cyclic/2-regular Graph Tapes
Cyclic/2-regular Graph Tapes
I will now focus on traversing a 2-regular graph, also known as a cyclic graph, where each node has an out-degree of exactly 2. In this context, the tape is assumed to be a finite, cyclic structure.
The primary challenge in dealing with 2-regular graphs and all subsequent graph forms discussed in this essay is their deviation from a standard shape that can be easily represented on a Cartesian plane. Unlike the 1D and 2D examples, I cannot use standard line plots to represent the abstraction of the machine tape. Therefore, I now aim to describe graph objects explicitly rather than relying on graph embeddings/emulations on the Cartesian plane.
Moreover, the concepts of direction and position become significantly more abstract. To overcome this problem in the context of Cyclic graphs, I employ a method involving the vertices of the abstract graph. I assume that all vertices are labeled using integers; in particular, cyclic graphs are labeled using consecutive, increasing integers in a clockwise direction. Therefore, movement around the graph can be represented simply as addition to (for clockwise movement) or subtraction from (for anticlockwise movement) the vertex label. I can further simplify the algorithm by reusing logic from the previous 1-Dimensional unidirectional tape example. This may be done because a cyclic graph, when “cut” and opened, becomes a finite 1-Dimensional tape that can be treated similarly to the previous 1D unidirectional Turing model.
Since I have already established the algorithm for this structure, I can adapt it for the cyclic graph. The only necessary modification is the handling of the “wrap-around” condition, which is the situation where the machine reaches the end of the graph. One might assume that, because the graph is cyclic, the head would simply continue circling; however, the logic relies on vertex labels. Therefore, in a N-node cyclic graph when moving from the final node N back to the first node 1, a simple increment would lead the machine to attempt to write to a non-existent vertex label beyond N. To solve this, I use modular arithmetic in the transition function: all movement operations are performed modulo N. Thus, the transition function adds 1 to the vertex label modulo N to move to the next position. Additionally, since these graphs contain exactly one cycle, clockwise (head state 1) and counterclockwise (head state 2) traversals follow each other’s reverse paths, allowing us to use the same algorithm and simply change the initial state to traverse the graph in both directions.
The primary challenge in dealing with 2-regular graphs and all subsequent graph forms discussed in this essay is their deviation from a standard shape that can be easily represented on a Cartesian plane. Unlike the 1D and 2D examples, I cannot use standard line plots to represent the abstraction of the machine tape. Therefore, I now aim to describe graph objects explicitly rather than relying on graph embeddings/emulations on the Cartesian plane.
Moreover, the concepts of direction and position become significantly more abstract. To overcome this problem in the context of Cyclic graphs, I employ a method involving the vertices of the abstract graph. I assume that all vertices are labeled using integers; in particular, cyclic graphs are labeled using consecutive, increasing integers in a clockwise direction. Therefore, movement around the graph can be represented simply as addition to (for clockwise movement) or subtraction from (for anticlockwise movement) the vertex label. I can further simplify the algorithm by reusing logic from the previous 1-Dimensional unidirectional tape example. This may be done because a cyclic graph, when “cut” and opened, becomes a finite 1-Dimensional tape that can be treated similarly to the previous 1D unidirectional Turing model.
Since I have already established the algorithm for this structure, I can adapt it for the cyclic graph. The only necessary modification is the handling of the “wrap-around” condition, which is the situation where the machine reaches the end of the graph. One might assume that, because the graph is cyclic, the head would simply continue circling; however, the logic relies on vertex labels. Therefore, in a N-node cyclic graph when moving from the final node N back to the first node 1, a simple increment would lead the machine to attempt to write to a non-existent vertex label beyond N. To solve this, I use modular arithmetic in the transition function: all movement operations are performed modulo N. Thus, the transition function adds 1 to the vertex label modulo N to move to the next position. Additionally, since these graphs contain exactly one cycle, clockwise (head state 1) and counterclockwise (head state 2) traversals follow each other’s reverse paths, allowing us to use the same algorithm and simply change the initial state to traverse the graph in both directions.
rulesC encodes the algorithm that traverses an empty, cyclic graph-tape using a (2,2,2)-TM.
turingGraphC is a finite, cyclic Turing graph with 12 vertices and initially empty nodes.
historyC stores history for 100 steps of the Turing machine on a cyclic graph tape
To minimize computation time within this essay, I computed the historyC function in the cloud, assigned the output to a cloud object, and referenced this cloud object in this essay.
The original expression was: historyC = evolveTM[turingGraphC, rulesC, 1, 1, 13];
visualizeTMC displays the traversal of the Turing machine head specifically for the case of a cyclic graph tape
Call visualizeTMC to display the Turing machine head (in red) traversing a cyclic graph tape over 100 steps.
Binary Tree Graph Tapes
Binary Tree Graph Tapes
I will now focus on traversing a binary tree graph tape, also known as a 2-ary graph . In this context, the tape is assumed to be a finite, hierarchical structure.
A significant challenge in navigating binary trees, similar to the experience with cyclic graphs, is their deviation from structures easily represented on a Cartesian plane. I overcome this by utilizing built-in N-ary tree visualization tools via graph objects rather than relying on fixed Cartesian coordinates. Furthermore, I address the lack of an inherent “clockwise” or “anticlockwise” movement, which necessitates a new labeling convention. Instead of spatial direction, I define the convention based on the tree’s inherent layer structure. Specifically, I define the root node as a 1-tuple and every subsequent node or layer via the appendage of tuples of increasing size to the root tuple.
The primary obstacle, however, is embedding a finite algorithm into the transition function of the Turing machine. I resolve this by implementing a (2, 4, 3)-TM with a “backtracking” strategy, in which the machine head continuously leaves “breadcrumb” symbols on the graph.
This allows the machine head to retain memory of its traversal history without violating the restrictions of a generalized Turing machine. In this algorithm, I adopt a left-handed traversal convention, meaning that a parent node’s left child is always visited before its right child.
This allows the machine head to retain memory of its traversal history without violating the restrictions of a generalized Turing machine. In this algorithm, I adopt a left-handed traversal convention, meaning that a parent node’s left child is always visited before its right child.
The step-by-step operation of the algorithm that traverses the first few layers of an initially empty, binary tree graph tape using a (2, 4, 3)-TM can be outlined in pseudocode below:
1
.Begin at the root node. Write 3 to this node.
2
.Move to the left child and write one to the empty node.
3
.Move to the parent and write 0.
4
.Move to the right child and write one to the empty node.
5
.Move to the parent and write 3.
6
.Move to the left child. Since the node contains a one, it can be deduced that the machine has already traversed this node once. Continue to the left child.
7
.Write one to the empty node, and move to the parent.
8
.If the parent contains a 1, it can be deduced that the machine has traversed this node twice: once on the way down from the parent to the left child, and now once on the way up from the left child to the parent.
9
.Write a 2 to this parent, and move to the right child
10
.Write one to the empty node, and move to the parent.
11
.If the parent contains a 2, it can be deduced that the machine has traversed this node three times: once on the way down from the parent to the left child, once on the way up from the left child to the parent, and once on the way up from the right child to the parent. Write 1 to the parent, and move to its parent.
12
.If a parent contains a 3, it can be deduced that the machine has reached the root node, since there is no other situation in which a machine head would move up and see a 3. Moreover, a 3 implies that the root can only been traversed once in this cycle of the algorithm. Write 0 to this parent to signify that the left subtree of the graph has been fully traversed in the scope of this algorithm cycle, and move to the right child.
13
.Move to the left child. Since the node contains a one, it can be deduced that the machine has already traversed this node once. Continue to the left child.
14
.Write one to the empty node, and move to the parent.
15
.If the parent contains a 1, it can be deduced that the machine has traversed this node twice: once on the way down from the parent to the left child, and now once on the way up from the left child to the parent.
16
.Write a 2 to this parent, and move to the right child
17
.Write one to the empty node, and move to the parent.
18
.If the parent contains a 2, it can be deduced that the machine has traversed this node three times: once on the way down from the parent to the left child, once on the way up from the left child to the parent, and once on the way up from the right child to the parent. Write 1 to the parent, and move to its parent.
19
.If a parent contains a 0, it can be deduced that the machine has reached the root node and that the left subtree of this graph has been traversed in the scope of this algorithmic cycle, since there is no other situation in which a machine head would move up and see 0. Write 3 to this parent to signify that the right subtree of the graph has been fully traversed in the scope of this algorithm cycle as well.
20
.Repeat Steps 2-17 until the given maximum number of steps have been computed
rulesBinary encodes the algorithm that traverses an empty, binary tree tape using a (2,3,3)-TM. Head State 1 and 2 represent an ascending or descending move during the past move of the machine head.
nbrFnBinary is the neighborhood function of the (2,3,3)-TM with input parameters of machine head position and the next direction to be moved to
turingGraphBinary creates a finite, cyclic Turing graph with an initially empty graph
historyBinary stores history for 230 steps of the Turing machine on a binary tree graph tape
To minimize computation time within this essay, I computed the historyBinary function in the cloud, assigned the output to a cloud object, and referenced this cloud object in this essay.
The original expression was: historyBinary = evolveTM[turingGraphBinary, rulesBinary, {}, 1, 230];
visualizeTMBinary displays the traversal of the Turing machine head specifically for the case of a binary graph tape
Call visualizeTMBinary to display the Turing machine head (node circled in red) traversing a cyclic graph tape over 230 steps.
Generalizing the upper bounds of N-ary tree traversal
Generalizing the upper bounds of N-ary tree traversal
After the construction of a traversal algorithm for binary graphs, a natural next step would be to find traversal algorithms for N-ary trees. Therefore, upon extensions to the existing algorithm and the configuration of the corresponding Turing Machine, I will now provide and prove a proposed upper-bound for the configuration of a 2-state Turing machine such that it may traverse any initially empty N-ary tree.
I build the logical proof through analysis of the binary graph traversal function.
Step 1 : Analysis of extracted generalized logic from the binary graph
Step 1 : Analysis of extracted generalized logic from the binary graph
Three primary requirements for a traversal algorithm can be deduced through the algorithm for the binary graph traversal. Firstly, it is necessary to distinguish between the left and right subtrees of the root node in the graph. Secondly, it is necessary to distinguish between the left and right subtrees of all other, non-root nodes in the graph. Thirdly, it is necessary to distinguish between the root node and all other nodes.
The current algorithm tracks traversal by distinguishing the symbols available. In the binary base case provided, the Turing Machine utilizes exactly 4 symbols to successfully navigate the graph without losing its position. Two symbols, specifically 0 and 3, are strictly reserved for the root node to indicate whether the left or right subtree is currently being processed. The remaining two symbols, 1 and 2, are utilized by all non-root nodes to track whether the machine is descending, returning from a left child, or returning from a right child. Fundamentally, the machine operates on 2 states: one state dictating downward movement to search for empty nodes, and one state dictating upward movement to backtrack through parents.
The current algorithm tracks traversal by distinguishing the symbols available. In the binary base case provided, the Turing Machine utilizes exactly 4 symbols to successfully navigate the graph without losing its position. Two symbols, specifically 0 and 3, are strictly reserved for the root node to indicate whether the left or right subtree is currently being processed. The remaining two symbols, 1 and 2, are utilized by all non-root nodes to track whether the machine is descending, returning from a left child, or returning from a right child. Fundamentally, the machine operates on 2 states: one state dictating downward movement to search for empty nodes, and one state dictating upward movement to backtrack through parents.
Step 2: Generalizing Symbol Requirements for N-ary Trees
Step 2: Generalizing Symbol Requirements for N-ary Trees
To extend this traversal logic to an N-ary tree, the machine must maintain the ability to strictly differentiate the root from non-root nodes, while dynamically tracking exactly which of the N subtrees is currently being traversed at any given node.The root node acts as the ultimate anchor for the algorithm’s cycle. To ensure the machine knows when to terminate or move to the next primary branch, the root must track which of its N distinct sub-branches it is currently processing. Consequently, it requires at least N unique symbols.
Similarly, every non-root node must act as a localized anchor for its own subtrees. To prevent infinite loops during backtracking, non-root nodes must track which of their N branches the machine head is returning from. This dictates that all non-root nodes combined require a distinct, separate set of N unique symbols. However, it is unnecessary to define a separate set of symbols for each of non-root nodes, as they all utilize the same traversal logic. Therefore, summing the root and non-root requirements yields a total alphabet size of 2N symbols.
Similarly, every non-root node must act as a localized anchor for its own subtrees. To prevent infinite loops during backtracking, non-root nodes must track which of their N branches the machine head is returning from. This dictates that all non-root nodes combined require a distinct, separate set of N unique symbols. However, it is unnecessary to define a separate set of symbols for each of non-root nodes, as they all utilize the same traversal logic. Therefore, summing the root and non-root requirements yields a total alphabet size of 2N symbols.
Step 3: Proof of Generalization via Induction
Step 3: Proof of Generalization via Induction
This generalization may be proven using induction based on the axiom that each additional branch added to the N-ary tree requires specific symbol additions.
Base Case (N = 2)
Base Case (N = 2)
As demonstrated in the previously described algorithm for binary tree traversal, 2 unique symbols are required for the root and 2 symbols for the non-root nodes, yielding a total of 4 symbols. The head contains 2 states representing the ascending and descending movement of the head. This satisfies the (2, 2N)-TM configuration for N=2, proving the base case.
Inductive Step
Inductive Step
Let N = k. Assume a k-ary tree can be completely traversed using a Turing Machine with 2 states and 2k symbols. I must evaluate the configuration when the graph is extended to a (k+1)-ary tree, meaning every node in the graph gains exactly one additional branch. To account for this new branch, the root node requires exactly one more symbol to signify when the machine is traversing its new (k+1)-th subtree. Likewise, all non-root nodes collectively require exactly one more symbol to track the upward backtracking from their respective (k+1)-th subtrees. Therefore, extending the graph by a single branch per node requires exactly 2 additional symbols added to the machine’s overall tape alphabet.
The new total symbol requirement for a (k+1)-ary tree is formulated as 2k plus the 1 root addition and 1 non-root addition. This expression, 2k + 2, factors into 2(k+1), which satisfies the form of the proposition. It should be noted that the number of machine head states may remain the same (ascending and descending). This is because the head state, in this context, represents 1-dimensional directional data indicating the direction of the machine head’s previous move. Since the only information needed by the machine head regarding its past direction is whether it was moving upward toward a parent or downward toward one of the child subtrees due to the logic in the algorithm, I only require two states regardless of how large k gets for an k-ary tree.
Conclusion
Conclusion
Conclusion
Conclusion
This project successfully generalized Turing machines by making it independent of the tape itself, demonstrating that the machine can be defined separately from the tape and does not need to be modified when the tape structure changes. Furthermore, I abstracted the notion of a tape through the definition of Turing graphs, allowing a wide variety of abstract graph structures to be represented as tapes using a single, unified Turing graph constructor.
Building upon these generalizations, this project built specialized traversal algorithms encoded as transition rulesets, which allow the Turing machine to traverse each of the five graph types explored: one-dimensional unidirectional graphs, one-dimensional bidirectional graphs, two-dimensional grid graphs, cyclic graphs, and binary trees. I also designed specialized visualization functions for each graph type, enabling users to observe the movement of the machine head throughout its traversal of the graph.
In addition to constructing traversal algorithms, this project developed efficient Turing machine configurations capable of implementing these traversals. Notably, the project proposed a conjecture on the upper bound for the number of colors required by a 2-state Turing machine traversing an N-ary graph tape. This conjecture was shown to have an upper bound of 2N colors, leading to the conclusion that a (2, 2N)-Turing machine provides an upper bound on the simplest Turing machine capable of traversing an N-ary tree graph tape.
Building upon these generalizations, this project built specialized traversal algorithms encoded as transition rulesets, which allow the Turing machine to traverse each of the five graph types explored: one-dimensional unidirectional graphs, one-dimensional bidirectional graphs, two-dimensional grid graphs, cyclic graphs, and binary trees. I also designed specialized visualization functions for each graph type, enabling users to observe the movement of the machine head throughout its traversal of the graph.
In addition to constructing traversal algorithms, this project developed efficient Turing machine configurations capable of implementing these traversals. Notably, the project proposed a conjecture on the upper bound for the number of colors required by a 2-state Turing machine traversing an N-ary graph tape. This conjecture was shown to have an upper bound of 2N colors, leading to the conclusion that a (2, 2N)-Turing machine provides an upper bound on the simplest Turing machine capable of traversing an N-ary tree graph tape.
Future Directions
Future Directions
Further graph topologies
Further graph topologies
This project has yet to cover more complex graph topologies, such as higher N-regular and connected graphs. Therefore, although I have not created the visualization function yet, I will discuss my work with 3-regular graphs, specifically focusing on the dodecahedral graph.
I will now explain a potential algorithm for traversing a dodecahedral graph using the concept of layered cycles, meaning the graph can be expressed as a series of interconnected cyclic graphs.
1
.Begin at the initial node. Write 2 to this node to mark the starting point of the current boundary cycle.
2
.Move along the clockwise-oriented edge to the neighboring node.
3
.If the node contains a 0, write 1 to this empty node to signify it has been traversed in the current cycle.
4
.Continue moving along the next clockwise-oriented edge.
5
.If the node contains a 0, write 1 to the empty node. Repeat this clockwise traversal and writing process.
6
.If the node contains a 2, it can be deduced that the machine has completed a full closed loop and has returned to the start of the current cycle.
7
.Upon reading the 2, move along the closest edge leading further “inwards” into the graph.
8
.Repeat Steps 2-7 until there exist no further, untraversed, inwards branches in the graph. It can then be deduced that there are no further unvisited layers to traverse inward, as the core/center of the graph has been reached.
9
.Halt the execution of the state machine, or repeat the traversal logic until a given maximum number of steps have been computed.
This algorithm contains several flaws. It should be noted that the notion of clockwise orientation is quite difficult to define for abstract graphs. This issue was encountered in cyclic graphs earlier in this essay as well; however, it was circumvented because our cyclic graph had a trivial labeling system in which we could simply view it as similar to a 1-dimensional line, which can be easily traversed by choosing one direction to move in and waiting until the machine head wraps back to its original position. In this context, however, determining which directional choice maps to which physical edge is quite difficult, as vertex labels are not trivially placed (e.g., +1 does not strictly mean clockwise, and -1 does not mean counterclockwise).
There is also the issue of moving across layers. Although there are nodes that connect the outward layer to the inward layers, not every node on a given layer can be used to enter the next layer. This means that, at some point in our algorithm, we must provide the machine with the information that it has both completed a cycle on its current layer and is positioned at a node connected to the next layer.
If we do not do this, the machine head may get stuck in an infinite loop, constantly moving back and forth between two layers. This happens because nodes that do not connect to further inward layers instead connect back to outward layers. However, the nodes in all layer (in circular order) alternate between having inward and outward layer connections. Therefore, if we have completed a cycle and find ourselves on a node without an inward connection, we must instruct the Turing machine to move one unit left or right to reach a valid inward-connecting node.
A complete, formalized algorithm would resolve these topological issues purely through the explicit use of internal states and symbols written to the tape (or nodes), rather than relying on the “oracles” or external structural knowledge implicitly assumed in the proposed algorithm.
Other further directions
Other further directions
Since this project has already generalized several components of the Turing machine, a natural next step is to generalize the algorithm used to traverse Turing graphs. Ideally, this traversal function could navigate any input graph without requiring modifications for different structures. This concept can be extended even further by exploring graphs that lack a constant out-degree. Instead of a uniform structure, the algorithm would only be provided the maximum out-degree present across all nodes in the graph. To handle this, the existing algorithms could be adapted: if each direction is associated with an integer symbol, attempting to choose a non-existent direction (e.g., the machine expects the maximum degree N, but the current node only has out-degree N-4) would trigger a specific convention. By mapping these non-existent edges back to the node itself, creating a self-loop, the machine can seamlessly process vertices with lower out-degrees using only its internal state and the available directions.
Next, this essay explores more practical applications of these algorithms. One approach is to analyze the time complexity and traversal speed of a single algorithm across multiple types of graphs, while keeping the embedded information constant. This comparative analysis could reveal distinct patterns and highlight special cases where certain graph topologies inherently outperform others.
Finally, the project’s scope regarding graph-tapes can be expanded to include N-regular graphs, complete graphs, and polyhedral graphs (e.g., dodecahedra). As with the previous conjecture and proof for N-ary graphs, it is highly likely that similar patterns govern the Turing machine configurations required for these more complex traversals.
Next, this essay explores more practical applications of these algorithms. One approach is to analyze the time complexity and traversal speed of a single algorithm across multiple types of graphs, while keeping the embedded information constant. This comparative analysis could reveal distinct patterns and highlight special cases where certain graph topologies inherently outperform others.
Finally, the project’s scope regarding graph-tapes can be expanded to include N-regular graphs, complete graphs, and polyhedral graphs (e.g., dodecahedra). As with the previous conjecture and proof for N-ary graphs, it is highly likely that similar patterns govern the Turing machine configurations required for these more complex traversals.
Acknowledgements
Acknowledgements
I would like to express my deepest gratitude to my mentor, Lyman Hurd, for his invaluable guidance throughout this project. His constant feedback, help in understanding new concepts, and suggestions for extensions (such as binary trees) were instrumental in shaping the direction and rigor of my project.
I am also extremely thankful to Stephen Wolfram for helping me formulate my initial ideas and introducing me to the fascinating field of Turing machines on graphs.
I would also like to extend a special thanks to Dugan Hammock for his insightful advice on extending my project and helping me further analyze my Turing machine traversal algorithms.
Moreover, I owe a great deal of thanks to the teaching assistants Max Wang, Daniel Xu, Eric Archerman, Amrita Kumar, and Arnay Garhyan, who patiently guided me through countless brainstorming and debugging sessions.
On a personal note, I am incredibly grateful to my dorm-mates, especially Jiaxuan Chen, and my parents for supporting me and helping me deal with and push through issues in my project.
Finally, I would like to thank the program directors, Rory Foulger, Eryn Gillam, Megan Davis, and Cyrus Taylor for making my participation in the 2026 Wolfram Summer Research Program (WSRP) possible and creating such a remarkable research opportunity.
I am also extremely thankful to Stephen Wolfram for helping me formulate my initial ideas and introducing me to the fascinating field of Turing machines on graphs.
I would also like to extend a special thanks to Dugan Hammock for his insightful advice on extending my project and helping me further analyze my Turing machine traversal algorithms.
Moreover, I owe a great deal of thanks to the teaching assistants Max Wang, Daniel Xu, Eric Archerman, Amrita Kumar, and Arnay Garhyan, who patiently guided me through countless brainstorming and debugging sessions.
On a personal note, I am incredibly grateful to my dorm-mates, especially Jiaxuan Chen, and my parents for supporting me and helping me deal with and push through issues in my project.
Finally, I would like to thank the program directors, Rory Foulger, Eryn Gillam, Megan Davis, and Cyrus Taylor for making my participation in the 2026 Wolfram Summer Research Program (WSRP) possible and creating such a remarkable research opportunity.
References
References
◼
Ackerman, N., & Freer, C. (2017). On the computability of graph Turing machines. arXiv:1703.09406
◼
Bartha, M. (2010). Turing automata and graph machines. arXiv preprint arXiv:1006.1428.
◼
Kunc M, Okhotin A. (2020). Reversibility of Computations in Graph-Walking Automata. In: Lecture Notes in Computer Science. ; 2013:595-606. doi:10.1007/978-3-642-40313-2_53
◼
Turing machines on graphs by Stefan Graham, Wolfram Community, STAFF PICKS, 2023, https : // community.wolfram.com/groups/-/m/t/2959123
◼
Stern, A. (2000). Quantum Theoretic Machines; What is Thought from the Point of View of Physics. Elsevier. https://doi.org/10.1016/B978-0-444-82618-3.X5047-5
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Generalization of Turing machine to abstract graphs
by Aadi Chakraborty
Wolfram Community, STAFF PICKS, July 9, 2026
https://community.wolfram.com/groups/-/m/t/3750050
by Aadi Chakraborty
Wolfram Community, STAFF PICKS, July 9, 2026
https://community.wolfram.com/groups/-/m/t/3750050