Turing Machine

Algorithms; computer science

A Turing machine is a mathematical tool that is the equivalent of a digital computer. It is the most widely used model of computation in computability and complexity theory in the computer world today. In its simplest form, it consists of an input/output relationship that the machine computes—the input is in binary format on a tape that the machine uses to compute the function, and the output is the contents of the tape when the machine stops. Studying this machine led to the study of classes of language and ultimately led to the development of computer programming languages.

In the 1930s, before digital computers were even thought of, several mathematicians began to think about what it means to compute a function. Alan Turing was one of these mathematicians, and his Turing machine became part of the definition of a computable function: “A function is computable if it can be computed by a Turing machine.” He is called the father of modern computing because the Turing machine is the precursor to all modern computers.

He developed these ideas at King's College, Cambridge, between the years 1932 to 1935, when many free-thinking mathematicians congregated there. His mentors include Christopher Morcom, Philip Hall, M.H.A. Newman, and Bertrand Russell. In 1936-37, he published a groundbreaking paper, On computable numbers, with an application to the Entscheidungsproblem, describing the theory of Turing machines and defining computability. One sentence reads “It is possible to invent a single machine which can be used to compute any computable sequence.” He called this machine a “universal computing machine,” and defined it as a Turing machine that could read the description of any other Turing machine and to carry out what that Turing machine would have done. One might think that complex tasks need complex machines, but that is not true; a simple machine can perform extremely complex functions when given enough time. Computers are now programmed to perform extremely complicated operations very quickly, but none of them can outdo a basic Turing machine in regards computing a function. Now that we all have computers with us constantly, we can see what Turing only imagined: He came up with the idea of a Universal Turing Machine 10 years before it could even be implemented!

This simple machine is made up of a tape (a ribbon of paper) containing an algorithm and a programmable read-write head (an instrument that can read the symbols on the tape, write a new symbol and move, for example, left/right or up/down). These terms may seem a bit archaic, but they give a sense of what kinds of machines existed when Turing invented this machine. The input on the tape must consist of a finite number of symbols; however, the tape, ideally, is infinitely long. Turing imagined this type of input to show that there are tasks that these machines cannot perform, even with unlimited time and working memory.

The Turing machine starts out in a specific state, then a program is written, on the tape, consisting of a list of transitions, telling the head what the next state should be and where it should move. The transition tells the head to do three things: (1) print something on the tape, (2) move to the right or left by one cell, and (3) change to a new state. The machine can also stop if there is no unique transition, for example, there is nothing on the tape.

There are really only six operations that a basic Turing machine can perform:

How a Turing machine acts is completely dependent on (1) the current state of the machine, (2) the symbol on the tape that is currently being read by the head, and (3) a table of transition rules, or the program, for the machine.

We could write this as Statec_urrent, Symbol, State_next, Action. If the machine is in a Current State and the tape contains the recognized Symbol, the machine will then move into the Next State and take Action.

The tape serves as the memory of the machine while the head is the mechanism by which data is accessed and updates the action of the machine.

Here is an example of a program for a Turing machine which starts with a blank, endless tape. This function tells the machine to perform the process of printing alternating characters, 0s and 1s, on the tape, leaving a blank space in between each numeral. The machine has four possible states, A, B, C, or D.

With this simple programming, the Turing machine will print an endless tape full of alternating 1s and 0s, leaving a blank space in between each numeral.

The advent of the Turing machine got people started thinking about coding theory for computers, what kinds of problems computers are able to solve, and what kinds of programming languages we can use to communicate with them, such as Turing complete. Any computer is, at its base, a Turing machine. It is a model of computation that captures the idea of what computability is very simply, without needing to think about all the parts your computer currently contains. According to the Church-Turing thesis, no computing device is more powerful than a Turing machine. Some scientists even find examples of Turing machines in nature; for example, our cells have ribo-somes that translate RNA into proteins, using much the same process as a Turing machine.

Alan Turing was a large part of the Enigma project during World War II. This project was the subject of several movies such as The Imitation Game and Enigma.

—Marianne Moss Madsen, MS