Programming Turing Machines: Introduction
Back again with another theory-heavy topic! The project I’ve been working on is quite extensive so it will be split into three parts:
As these topics are created, they will be linked together for easy navigation, but let’s go ahead and get started.
Informal definition
A Turing machine is a relatively simple model for computation, consisting of only three parts: a tape, a head, and a state machine. For those unfamiliar with finite automata, brush up on DFAs and how they work, as that will help tremendously for understanding the mechanics at play (try this).
Think of the tape as an infinite roll of film. Each cell, however, contains at most 1 symbol or can be blank. Let’s say for instance our tape looks like this:
|>|a|a|b|_|_|...
For this textual representation, cells are denoted by ‘|’ characters and blank cells are represented by ‘_’ characters. The reason for this will show up later on, but we will see it is easier to reason about '_'s being blanks, rather than spaces.
Another notation you will see me use frequently is using the ‘>’ character as a marker for the beginning of the tape. The symbols you use on the tape have nothing to do with the Turing machine concept; simply find or make a convention and stick with it (if you want to use Emojis, Turing won’t stop you [probably]). How the symbols you use on your tape are used with the Turing machine will be discussed in the formal definition.
The next component of the machine is the head. It has four operations it can perform: move left, move right, read, and write. Any time the machine executes an instruction, it will read, write, and move, in that order. Denoting the position of the head on the tape can be done many different ways, but I found using a ‘^’ character is easiest:
|>|a|a|b|_|_|...
^
The last piece of the puzzle is the underlying state machine. This is what tells the Turing machine what to read and write, as well as which direction to move. We can represent the different functions of a particular Turing machine configuration by using different states for a particular purpose. Similar to the head, there are many ways the current state can be represented textually, but I prefer to append it to the end of the tape:
>aab s1
^
The trailing ‘_’ characters will be ignored unless they are necessary for a particular function; ‘_’ characters within the middle of the tape will not be ignored, and will still represent blank cells.
Formal definition
The following definition is an excerpt from the fantastic book Introduction to the Theory of Computation by Michael Sipser:
A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qA, qR), where Q, Σ, Γ are all finite sets and:
- Q is the set of states,
- Σ is the input alphabet, where ‘_’ ∉ Σ,
- Γ is the tape alphabet, where ‘_’ ∈ Γ and Σ ⊆ Γ,
- δ: Q x Γ → Q x Γ x {L,R} is the transition function,
- q0 ∈ Q is the start state,
- qA ∈ Q is the accept state, and
- qR ∈ Q is the reject state, where qR ≠ qA.
A Turing machine M = (Q, Σ, Γ, δ, q0, qA, qR) computes as follows. Initially, M receives its input w = w1w2…wn ∈ Σ* on the leftmost n squares of the tape, and the rest is blank (i.e., filled with blank symbols). The head starts at the leftmost square of the tape. Note that Σ does not contain the blank symbol, so the first blank appearing on the tape marks the end of the input. Once M has started, the computation proceeds according to the rules described by the transition function. If M ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L. The computation continues until it enters either the accept or reject states, at which point it halts. If neither occurs, M goes on forever.
Note: There are other definitions of a Turing machine, including a variant of the 7-tuple construction and a “simpler” 6-tuple construction. Use the definition you understand most, as that will be the most beneficial to you.
So with the above definition in mind, the “meat” of a Turing machine lies within its transition function. We can rewrite it in a way that is more intuitive to us from an implementation perspective:
δ(q, a) = (q’, b, d), where:
- q, q’ ∈ Q,
- a, b ∈ Σ, and
- d ∈ {L,R}.
Example
Let’s start with a machine based on our earlier configuration:
>aab s1
^
We can use the above to fill out the construction of a Turing machine that will do nothing (for the time being):
- Q = { s1 },
- Σ = { a, b }
- Γ = { a, b, >, _ }
Since we currently only have one state, s1 is our q0, while the other q’s are undefined. We can represent our transition function with a state diagram, but we could also use a list of tuples. Currently, our machine has no defined behavior; let’s add some stuff to make a machine that accepts only the word “aabb”. We need to go ahead and add two additional states to our machine so we have a place to go to accept and reject (I use H for “halt”):
- Q = { s1, s2, H },
- Σ = { a, b }, and
- Γ = { a, b, >, _ }.
Let’s go ahead and start writing transition tuples. The order of the tuples in the list have no meaning, however the elements within each tuple will adhere to the following order:
(q, a, b, d, q’), where q, q’, a, b, d maintain the same definitions from above.
We can start by creating a transition to check that our input begins with a ‘>’:
(s1, >, >, R, s2)
This transition states that when in s1, the machine will read a ‘>’ from the tape, write a ‘>’ on the tape, move one cell to the right, then transition to s2.
With the initial ‘>’ character taken care of, we can check the next cell for an ‘a’:
(s1, >, >, R, s2),
(s2, a, a, R, s3)
This performs a similar operation as before, though this time on a different symbol. We have a problem though: s3 is not a valid state in Q. Let’s rewrite the definition of our Turing machine with additional states that are needed:
- Q = { s1, s2, s3, s4, s5, s6, H },
- Σ = { a, b },
- Γ = { a, b, >, _ },
- q0 = s1,
- qA = s6, and
- qR = H.
And the necessary transitions:
(s1, >, >, R, s2),
(s2, a, a, R, s3),
(s3, a, a, R, s4),
(s4, b, b, R, s5), and
(s5, b, b, R, s6).
The halting transition is as follows, and is performed when no valid transition can be found:
(q, a, a, R, H) where q is the current state and a is a symbol in Σ that has no transition for q.
When we “run” the Turing machine, we can see what it does by writing the configuration for every instruction. As stated, we start with our head at the start of the tape, and or machine in our q0 of s1:
>aab s1
^
We look in our transitions and find the path (s1, >, >, R, s2). The next configuration is written immediately under the previous one:
>aab s1
^
>aab s2
^
To continue, we again look in our transitions and find (s2, a, a, R, s3):
>aab s1
^
>aab s2
^
>aab s3
^
Let’s continue this until our Turing machine halts, then examine what happened:
>aab s1
^
>aab s2
^
>aab s3
^
>aab s4
^
>aab_ s5
^
>aab__ H
^
As you can see, our machine carried on just fine until it ran out of letters. Since our transition function was defined to recognize “aabb”, it had nowhere to go when it got to the first ‘_’ at the end of our word, “aab”. Therefore, “aab” was not accepted by the Turing machine. Let’s run this again, this time using the accepting word “aabb”:
>aabb s1
^
>aabb s2
^
>aabb s3
^
>aabb s4
^
>aabb s5
^
>aabb_ s6
^
Since s6 was our qA, the Turing machine halted in a valid state, and “aabb” was accepted.
Parting words
Using the Turing machine model to solve a particular problem can be extremely useful. Our example was simple for demonstration purposes, but these models can be used for much more advanced problems. If at any point the construction and mechanics of a Turing machine was confusing (or incorrect) please let me know so I can clear it up. Having a solid understanding of these will help tremendously as I describe my implementation of a Turing machine for advanced problem solving.
For the purposes of demonstration, familiarize yourself with my representation of the transition function as a list of tuples; this will reappear in the implementation later on.
Part II is out!