The Turing Machine

logo

Virtual Assistant, Web Design and bookkeeping services

The Turing Machine is a model of computation which is reflected in every sort of computer we use today: the computer in my iPhone, the computers in a large scientific establishment, the computers that are attached to the hull of a ship which measure temperature for climate researchers.

Alan Turing, father of Computer Science, renowned code breaker, mathematician and Artificial Intelligence pioneer, developed a model of computation which lasts to this very day and works for tiny computers up to super computers. He came up with a convincing mathematical definition of the notion of an algorithm, now know as the Turing Machine. It is based on a tape machine where the computation is carried out by tape moving under a head. The tape is neatly divided into squares. Each square can contain exactly one symbol from a finite set of symbols. Given a computer (a person in Turing’s time) and the tape, we can specify precisely what it means for this computer to follow an algorithm.

We assume that for any algorithm, one of the states and one of the squares on the tape are designated as the starting state and the starting square. Given such a starting state and square, an algorithm consists of instructions of the following shape that the computer should follow: IF you are in a certain state of mind and observe in the current square a certain symbol (or that it is empty), THEN perform the following actions (always doing the writing first):

  • Write s / blank
  • Next state q
  • Move left / right / stay

There is at most one instruction for each combination of a state of mind and a current square. In other words, the computer is given no choice: either there are no actions for the current square and state, or a specific course of action is prescribed by the (single) instruction for that combination. For this reason, the Turing Machines described here are sometimes also referred to as deterministic Turing Machines.

Turing machines allow us to simplify the description of algorithms. The following is the example of a Turing Machine for adding two sequences of ◼. Informally, in English an algorithm for carrying out such additions, assuming that the square with the leftmost ◼ is the starting square:

Move to the right, until you encounter an empty square. Then write a into the empty square and resume moving to the right. When you hit on another empty square, move back one step. Then erase the ◼.

This algorithm can be stated with mathematical precision as a Turing Machine. To specify this Turing Machine, we first specify the set of its states Q and the set of symbols S it can use:

Q = {LookingForEndFirstNumber, LookingForEndSecondNumber, CompleteCalculation}
S = {◼}

To make the table more precise, we use numbers to refer to the three states: 0 for LookingForEndFirstNumber, 1 for LookingForEndSecondNumber and 2 for CompleteCalculation.

The Turing Machine for addition can be captured by a table. Each cell in the table contains the actions that are to be carried out for a given combination of state and current square. In other words, each cell in the table represents an instruction. That is, except for the cell at the bottom right of the table. That cell contains no actions: if we end up in that cell, the computation halts.

Each Turing Machine can be viewed as a mathematically precise version of an algorithm. The tape (including information on which of the squares is the current square) and the current mental state of the computer are not part of the Turing Machine. However, the tape plays a special role in that it contains the input when the algorithm is started and records intermediate results (similar to the notepad of a human computer).

A Turing Machine only describes the algorithms. To execute the algorithm, one also needs the initial state, an infinite tape (possibly with some symbols on it already), and the initial position of the tape head.

Turing Machines play a pivotal role in Turing’s proof that there are computational problems that are not computable. A problem is computable if there is an algorithm that solves every instance of the problem in a finite number of steps. This means that for each input the algorithm should return , after a finite amount of time, the output given by the mathematical function that corresponds to the computational problem. The other key ingredient of Turing’s proof is a mathematically precise definition of the concept of a computational problem.

The abstract definition of a Turing Machine using set notation:

A Turing Machine M is a triple, (Q, S, I), consisting of:
1. a finite set of k states Q = {q1, …, qk}
2. a finite set of n symbols S = {s1, …, sn}
3. a finite set of instructions I. Each instruction i ∈ I is a tuple (c, A) consisting of:
– a condition c ∈ Q x (S U {blank})
– a triple of actions A = (a1, a2, a3) such that A ∈ {Write x : x ∈ (S U {blank})} x {NextState q : q ∈ Q} x {MoveLeft, MoveRight, MoveStay}.
Furthermore, we have that if (c, A) ∈ I and (c, A‘) ∈ I then A = A‘.
In words, for each condition, there is at most one instruction.

The claim that Turing Machines capture the intuitive idea of an algorithm is known as the Church-Turing test.

It might be baffling that such a simple definition of algorithm can capture all that programs on modern computers can do. Unlike Python, and other languages, Turing Machines don’t have variables, assignments, additions, if-, while-, and for-instructions, etc., so how can they compute the same as programs?

If you imagine a computer that has no RAM, jus a hard disk as memory, then the effect of executing a program is, in the end, just reading and writing 0s and 1s from an to various positions on the disk. Some of the bits on the disk could represent the pixels on the screen, other bits may be played via a loudspeaker as sound, other bits are the result of typing characters on a keyboard, but that’s all related to how I/O devices generate and interpret sequences of bits. The essence of computation, at its most basic level, is to change those sequences of bits in memory, and that’s what a Turing Machine is able to capture in the simplest possible way.

Today, we call the deterministic Turing Machine (DTM) the classical model of computing. The DTM is an influential abstraction which provides an intuitive, rigorous and realistic mathematical model of algorithms. The physical realisation of the Universal Turing Machine is our modern electronic computer today.

Firstly, the DTM model seems to capture the intuitive notion of a computation. This was made plausible when Turing showed in his 1936 paper how any computation carried out by a human computer could be modelled with a Turing Machine. More specifically, the Turing Machine modelled an algorithm that prescribed what the human computer was expected to do at each stage of a computation. The force of Turing’s argument can be appreciated best by keeping in mind that at the time, in 1936, a substantial number of people were employed as ‘computers’, with the use of this term in English dating back as far as the seventeenth century. Turing’s idea became known as the Church–Turing thesis that sets out that every function that would naturally be regarded as computable can be computed by a deterministic Turing Machine.

The mathematical rigour with which the Turing Machine model is defined enabled Turing to prove certain things about it. Most spectacularly, as we’ve seen, he proved that not all possible functions can be computed by a DTM. This means that if the Church–Turing thesis is correct, the set of functions ‘that would naturally be regarded as computable’ is definitely a proper subset of the set of all possible functions.

When people started building programmable electronic computers, from the middle of the last century onwards, these machines were all running algorithms that corresponded to DTMs. In fact, all these machines were essentially physical realisations of the Universal Turing Machine.

Turing Machines, including the Universal Turing Machine, are abstractions. Running a Turing Machine on a given input means carrying out a sequence of instructions, until no further instructions apply. Each instruction is carried out based on the content of the current square and current state and may result in an update of these. The Universal Turing Machine has an additional property.
A Universal Turing Machine is a Turing Machine U which can take the description of any other Turing Machine m as input together with any input x for that machine, and compute the output that m computes given input x.
Physical devices are realisations of a Universal Turing Machine.


You May Also Like…

The origins of Java

The origins of Java

In 1990, Patrick Naughton, a disgruntled software engineer working for Sun Microsystems (the company was acquired and...

What is procedural programming?

What is procedural programming?

Before object-orientation the predominant method for structuring programs was procedural programming. Procedural...

0 Comments

Submit a Comment

Your email address will not be published.