In this article I will talk about the Turing machine for programmers. A Turing machine is an imaginary computer which is made as simple as possible - it's hard to imagine a simpler computer! A Turing machine doesn’t even know how to do simple arithmetic operations: addition, multiplication, subtraction, and division. To do any of these operations, like adding two numbers, you need to write a program. The simplicity of the Turing Machine makes it convenient to build a mathematical model of it and to use that to analyze algorithms written for it. Although I am interested in the mathematical component, in this article I will focus on programming.

About the Turing machine - why it’s interesting and useful for programmers:

• A Turing machine is one way of representing an algorithm, and because of this it has been used to solve problems in the theory of algorithms.
• A Turing machine has also been used to write some encryption algorithms.
• Using a Turing machine greatly develops algorithmic thinking.
• Programming for a Turing machine is an exciting process, and it differs from ordinary programming significantly since only a meager set of tools and actions are available. However, this sort of “cave programming” can yield some exciting and unexpected solutions.

Required skills:

- Understanding of: conditional statements, loops, the "switch" operator.

Background information:

Before writing a program, we try to think through its algorithm as much as possible. In the strict mathematical world, the term "algorithm" is not formally defined, but there are theories that are used to explain them. Some of these are:

• “Markov’s approach” – theory of “normal algorithms”: algorithm == block diagram
• “Gödel and Church’s approach” - We have a certain set of simple functions (for example: primitive functions), and finite superpositions of these can be constructed. Here, algorithm == recursive function
• Turing’s approach: Algorithm == Turing machine program. For Alan Turing and his followers, a Turing machine program is the algorithm.

It has been proven that if the problem is solvable according to Turing, then it is solvable according to the approaches both of Markov and of Gödel and Church. Vice versa, if the problem is not solvable according to the Turing approach, then it isn’t solvable according to either of the other approaches. That is, Turing solvability = Markov approach solvability = Gödel and Church approach solvability.

Now let's start studying the Turing machine. A Turing machine consists of four parts: an endless tape, a moving read/write head (MRW), the machine program, and a control unit (CU). Let’s go through these one by one.

Endless tape

The endless tape is divided into cells. In the diagram it looks like nothing is written in the cells, but for a Turing machine, each cell must always have a symbol in it. Therefore, it is more correct to think of these blank cells not as being “empty cells”, but instead as cells in which an “empty character” is written. Most often in the literature, the “empty character” is denoted by "∧". Emulators sometimes use " " (space) as an empty character. Notation for an endless tape without drawing the tape itself looks like this: …∧∧∧…, where one character = one cell.

An empty character is always on the tape, but other characters are written to the tape during program execution. The set of characters that can be written to the tape is determined by the programmer, and is called the external alphabet A. For example, say we are going to write a program that will cause the characters «a», «b», «c» to appear on the tape. Then the external alphabet would be A={a,b,c}.

Note 1.

Sometimes emulators impose restrictions on the external alphabet, so you should check the instructions for the specific emulator that you’re using for details.

Note 2.

An empty character does not belong to the external alphabet and is treated separately. The description of the symbols used in the program will contain the notation A∪{∧}. This makes it clear which character plays the role of an empty character.

Note 3.

The external alphabet does not include characters with special functions (which the other characters do not have). For example, one such special character could be a word delimiter character. The programmer can choose any character as the delimiter, such as the character "Y", so that the notation …∧∧turingYmachine∧∧… can be interpreted as having a delimiter between the words turing and machine. However, if “Y” is included in the external alphabet then this string will be interpreted as a single word, instead of two. The "Y" symbol is not just a symbol on the tape but separates turing from machine, so it should not be included in the external alphabet. Why it is not possible to separate these two words (turing and machine) with a space will become clearer later when programming the copy machine. To describe the symbols used in the program, we can use the notation A∪{∧}∪{Y}. In the last point, the concept of a “word” is used several times. A “word” is a sequence of characters where none of them are empty and all of them are part of the external alphabet.

Example 1.

In …∧∧turing∧∧… the word is “turing”.

Example 2.

The entry …∧∧turing∧machine∧∧… has two words (turing and machine).

Example 3.

Once again, let's see with an example why it is so important not to include delimiter characters in the external alphabet. Let the symbols be used for the program:

Then in the notation …∧∧turingYmachine∧∧… there is one word – turingYmachine.

If instead we use a different alphabet is used for the same entry:.

Then in the entry …∧∧turingYmachine∧∧… there will be two words: turing and machine.

A moving read/write head (MRW)

In the image above, the red arrow is the MRW location.
The Turing machine works in steps. At each step the MRW is always located at a specific cell, and performs three actions in each step:

1. Read the character written in the current cell
2. Write a character to the current cell
Note that it always does this. That means that for each step the programmer must specify the character that the machine will write into the current cell. If no change is needed, the programmer simply specifies the same character that is already in the current cell.
3. Perform a shift (moving the MRW)

The MRW can do three types of shifts: 1 cell to the right, 1 cell to the left, or stand still. The set of shifts also has a name - the alphabet of shifts S = {+1, -1, 0}. Another notation for the shift alphabet is S = {R, L, N}.

Note 4.

1) The alphabet of shifts in an emulator may look like this: S = {L, R}. In this case, you will have to add additional states to simulate the "0" shift.
2) We will assume that at the start of execution, the MRW is always located on the leftmost character of the word (however, this is not necessarily always true).

Machine program - We’ll discuss this in detail in a moment.

Control unit (CU)

Controls the operation of the machine with the help of the program. The CU determines what actions need to be done next according to the program, and conveys this information to the MRW.

In Turing machine programming, we do not write commands; instead, we describe states. What actions are taken depend only on the current state and on the inputs to the system. For example, to open a fridge, a Turing machine programmer does not write the command “Open the fridge”, but instead describes a state (which consists of a condition, a command, and the next state): “If you feel hungry: 1) Open the fridge 2) Remember that the fridge is open.” While the program is running, the MRW always has a state. All states that are used in the program are defined in a set called the state alphabet Q={q₀,q₁,… q_n}. It is sometimes called the internal alphabet.

Now, we’ll see how everything works together.
The machine works step by step.
At the first step, the MRW is now in the initial state q₁ and is located at the first character of the word recorded on the tape. The MRW reads the first character of the word, and passes this information to the CU. Using the read character and the current state, the CU decides what the MRW needs to do next, and it sends this information to the MRW. The information on the next action to take that is received by the MRW has three components:

• Symbol - which symbol will be written instead of the current one in the cell on which the MRW is currently located
• Shift - what move the MRW will make after overwriting the current character
• State - what state the MRW will be in in the next step This “triplet” of information is determined by a programmer; this is what Turing machine programming is.

You can think about Turing machine programming as a "switch" statement:

		
			Switch(state)
				Case q₁
					 Switch(symbol)
					Case “a”:
						Print(“c”)
					Moveto(+1)
					q₁
				Case “b”:
					Print(“b”)
					Moveto(+1)
					q₁
				Case “c”:
					Print(“a”)
					Moveto(+1)
					q₁

				Case “ ”:
					Print(“ ”)
					Moveto(-1)
					q₂

			Case q₂:
					Switch(symbol)
				Case “a”:
					Print(“a”)
					Moveto(-1)
						q₂
				Case “b”:
					Print(“b”)
					Moveto(-1)
						q₂
				Case “c”:
					Print(“c”)
					Moveto(-1)
						q₂
				Case “ ”:
					Print(“ ”)
					Moveto(+1)
					q₀
		
	

If a combination of symbol and state that the programmer forgot to account for in the program is encountered, then the program will stop running. The programmer must take into account all possible combinations of input symbol + current state that may occur during the execution of the program, and must prescribe a triplet of character/shift/state for each.

So, after the first step, the MRW will have overwritten the first letter on the tape with a new symbol, then made a shift and moved to a new state (note that each state except the final one can be used more than once). The second step begins: being in some state, the MRW reads the letter, learns the next three actions from the read letter and the current state, etc. One of the properties of the algorithm is finiteness: at some point in time, the program must be completed. q₀ denotes the final state. When the MRW is instructed to transition to the final state, it writes a character to the current cell and makes a shift as usual, but the program execution then stops.

Note 5.
When writing programs, we’re going to assume that after finishing execution, the MRW should stop at the first letter of the result word.

Since a Turing machine program consists of switch statements, it is very convenient to write the algorithm in the form of a table. The general view of the program looks like this:

1≤i≤n
1≤j≤m
s∈{-1,0,1}

In the left column there are the letters of the external alphabet and the empty character that can be read from the tape. If necessary, auxiliary characters with special functions (discussed in Note 3) can be added to the end of the left column.
The table below shows the added delimiter character. A bold line is added to the table (for clarity only) and after this line the additional characters are listed.

The second row of the table contains all the states from the alphabet of states, excluding the final state q_0 (because q_0does not imply any state after itself).
As mentioned earlier, during the execution of the program, various combinations of input symbol + state occur. For each combination of symbol + state encountered, the corresponding table cell is searched. In this cell, the programmer writes a triplet of symbol (to be written in the current cell), shift (of the MRW to a new position on the tape), and state (the next state the MRW will be in). Let’s recall the representation of Turing machine programming as a "switch" statement and note that one cell of the table is a piece of the form:

	
		Switch(state)
			Case q₁:
					Switch(symbol)
				Case “a”:
					Print(“b”)
					Moveto(+1)
						q₂
	

So, writing a Turing machine program is as simple as filling in the cells of the table.
Finally we’re done with the theory. Let's start practicing!

Program examples.

1. Hello world!
Displaying the message "Hello world!" is not the simplest starter program on a Turing machine. It will use an alphabet of 7 letters (which is quite a lot), and there are also a lot of commands, so the program table will be bulky and largely empty. Instead, we’ll write a simpler analogue of the "Hello world!" program for a Turing machine.

Let А={|,x} be an external alphabet. A word is placed on the tape using a certain number of "pipes" (|) from 1 to N. Replace each character of the word with the character "x".

link to the program standard (formal) notation

link to the program more readable notation

Solution:

Explanation: q₁ is a state in which the MRW replaces all pipes with ''x'' (while stepping to the right), but when it encounters an empty character, it assumes that we have reached the end of the word. Therefore, it leaves the empty character unchanged and takes a step to the left, while transitioning to state q₂. In state q₂, the MRW moves back to the beginning of the result word, where it stops.

Visualization on the emulator:

P.S.: if you do not believe that writing the full “Hello world” program is painful and tedious, you can see an implementation of it here.

P. P. S.: By clicking on the links to the emulator, we see the code on the right side of the screen. Note that the syntax will differ from emulator to emulator. In this one, you need to specify the initial state in the start state line: (start state = q₁ ); the final state is written at the end of the entire code as a normal state, but nothing is written after the colon. States are described by several lines, for example:

q₁:
'|' : {write: '|', R: q1} - means if you read “|”, then write “|”, go right, and go to state q1.
'|' : {write: '*', R: q1} - means if you read “|”, then write “*”, go right, and go to state q1.

2. Copy machine

Let А={|} be an external alphabet. A word is placed on the tape with a certain number of "pipes" from 1 to N. Duplicate the word and separate the two words with a delimiter character “Y”.

E. g.: ||| -> |||Y|||

Solution:

Below is the representation of the same program in the emulator:

link to the program

Visualization on the emulator:

Idea:
You need to add an auxiliary character - this will be the delimiter (we use “Y” in this program). The idea is:

1. Replace all the letters of the word with the same number of "a"s (e.g.: ||| -> aaa),
2. Put a fixed delimiter(“Y”) to the right of the word.
3. Seek backwards and replace one “a” character with a pipe “|”, move the MRWbehind the delimiter character, and put another pipe there (aaaY -> aa|Y -> aa|Y| -> …)
4. Seek backwards and replace one “a” character with a pipe “|”, move the MRWbehind the delimiter character, and put another pipe there (aaaY -> aa|Y -> aa|Y| -> …) Repeat step 3 until there are no more “a”s.

Now we can analyze the algorithm in more detail.
We have three states and three main actions.

• q₁ will replace all "pipes" with "a", insert the delimiter "Y", and go to state q₂.
• q₂ is essentially a signal that it's time to put a "pipe" after the last letter of the word. Stepping to the left, it looks for "a", replaces it with "pipe" and goes to state q₃.
• q₃ puts a pipe after the last letter of the word.

It is very convenient to use emulators to test programs. If there is no emulator available, you can check the program yourself by hand. The following pictures are an example of a manual check.

The copy machine is very important, because it is used as a foundation for many other programs.

3. Mirror machine

Let А={x,y} be the external alphabet, and let “Y” be the word delimiter character. A word, made up of an arbitrary number of symbols drawn from A, is placed on the tape. Add a word delimiter character and then the mirrored word.

E.g.: xyxxxy -> xyxxxyYyxxxyx

Solution:
To copy a word that consists only of "pipes", it was necessary to expand the external alphabet - to add one character to act as a placeholder. Everything is the same here, but we now need to add two auxiliary symbols (one for each character in the external alphabet) and one extra state. The extra auxiliary symbols are needed because we need to be able to distinguish between the two symbols on the tape when they will be replaced, and similarly we also need extra states to handle the different behavior when each of the two symbols is to be replaced. Let's say that we have replaced all "x" and "y" with "a" and "b", and we have, for example, "abbaY" on the tape. We now need to write “x” and “y” to the right of the word. This is what the new state is for. "abbxY" -> "abbxYx" -> "abyxYx" -> "abyxYxy" -> ...

Visualization on the emulator:

4. Machine: adding two numbers

A word is printed on the tape, consisting of N "pipes" (“|”), a "+", and M more "pipes". Add the numbers together and change the word on the tape to consist of N+M "pipes".

E.g.: ||+||| -> |||||

Also, if one of the terms is omitted, we will assume that it is equal to zero.
E.g.: +||| -> |||

Solution:

# idea: replace "+" with "pipe"; then remove the last "pipe" at the end of the word.

Visualization:

5. Machine: adding numbers (better)

We can improve the program above. The changes are in displaying the result on the screen.

E.g.: ||+||| -> ||+|||=|||||

Visualization:

link to the program

Here we will use a copy machine from before - the one that allows for a two-character alphabet. Let’s make a copy of the word on the tape, separated by a word delimiter character. This time, we use “=” as the delimiter character: u=u. When we have finished the copy, we can then apply machine 3 (the previous adder program) to the right-hand copy that we just made. This chaining-together of successive machines is referred to as the composition of two Turing machines.
Our new copy machine is basically still just a mirror, but thanks to the commutativity of the addition operation, that’s not a problem.
Note that after the completion of the program, the MRW should have been moved to the beginning of the word, but we’ve omitted this action in our implementation so as not to clutter the program with an additional state.

Composition Implementation

Let T₁, T₂ be Turing machines and u be a word.
The composition (T₂∘T₁)(u) means the following: (T₂∘T₁)(u)= T₂ (T₁ (u))
I.e. T₁ is applied to u first, and then T₂ to the result.

In one of the cells of the table is $q^{\frac{0}{1}}$ - the final state of the machine T₁. Instead, we’ll replace it with $q^{\frac{1}{2}}$ - the initial state of the machine T₂. Thus, the work of the first machine will be performed first, and then the second, giving a composition of the two machines.

An example of machine composition is machine 5: the improved number adder. This is a composition of the mirror machine (machine 3) and the first implementation of the adder machine (machine 4).

Conclusion

Obviously, there is no simpler computer than a Turing machine. However, any mathematical function can be written on a Turing machine, and they can be used to write a program of any complexity. For large or complex programs, you can use composition, as well as the formal implementation of the if-statement and loop operator. In simpler programs, however, this is not required, as it would greatly complicate the program.
From this, we get a remarkable statement: any algorithm can be implemented on a Turing machine. Because of this incredible fact, the Turing machine can be considered the progenitor of modern computers.