Why is the Turing Machine important?
Why is the Turing Machine important?
Some ideas in the paper that Alan Turing presented in 1936 are included in the architecture of our modern computers.
1936
Scientists have discovered Pluto, cars are not yet mainstream, and most families spend their Friday nights huddled around a radio for entertainment. That was the 1930s, the time when Alan Turing wrote his famous paper on the Turing Machine.
In 1936, after graduating from King’s College, Cambridge, with a degree in mathematics, Alan presented a paper to one of his professors. Turing’s paper was about a problem in mathematical logic. The goal was to prove that there is no general decision procedure for first-order logic, or what is also known as the Entscheidungsproblem.
In this paper, Turing created an imaginary machine. He had no intention of building this machine. He didn't even think that something like that could or should be created. For him, the machine served only as a tool in the mathematical proof.
Why is the Universal Turing Machine so important?
If it weren’t for the ideas in this paper, we would need to buy a different computer depending on what we want to do. For example, a computer to manage accounts, a computer to play League of Legends, another to use Gmail, etc.
Current computer systems work similarly to what Turing envisioned in his paper. It influenced the architecture used by most of the current computers, the von Neumann architecture.
How does a Turing Machine Work?
A Turing Machine is a machine that can print on a very long tape. It can print characters (a, b, x, ...) and 0s and 1s.
The machine has a head that is always on top of one cell. Apart from that, these are the functionalities of the machine:
The machine can read the symbol in the cell.
It can print a symbol in that cell or change it.
It can move to the left, right, or not move at all.
The machine is playing a game in turns with itself. In each turn, the machine can perform one, some, or all steps mentioned above. For example, it can read the symbol, print a 0, and move right. Or it can just move left. The configurations of the machine define what to do in each step.
Each configuration has:
A name or identifier. This is used to refer to it.
Symbols to be matched.
A set of operations for each symbol matched.
The following configuration to run.
A simple Turing Machine:
It’s always better with examples, so let’s take a look at a machine printing 0s and 1s alternatively.
Identifier Symbol Operations Next Configuration B None P0, R C C None P1, R B
The machine always starts at configuration B –for "begin"– and at the cell we choose. In our example, the machine starts with a blank tape.
It starts at configuration B
It reads the symbol in the cell: blank.
It moves to the operations.
P0 Prints 0
R Moves right.
It sets the following configuration: C.
It starts at configuration C
It reads the symbol in the cell: blank.
It moves to the operations.
P1 Prints 1.
R Moves right.
It sets the following configuration: B
It starts at configuration B again and keeps going like this forever.
This is actually how simple a Turing Machine operates. The beauty lies in the configuration. What we would now call "software."
A complex Turing Machine
It’s fascinating to realize that from the previous simple functionality, we can compute complex calculations.
Find below another example of a configuration printing an increasing amount of 1s separated by 0s. This would be an irrational number, one that very likely is also transcendental.
The elements in both configurations are the same: print something, move right, move left, etc. The complexity comes from combining those simple concepts.
Note: Px means to print an "x"; Pf, print an "f"; PNone, empty the cell.
Identifier Symbol Operations Next Configuration B None P0, R, Px, R, P1, R, R, P0, R, Pf F C e, f, 1, None L C C 0 - E C x PNone D D None, 0, 1, x R D D e, f Px, R, P1, R, Pe F F e, 1, None, x L F F 0 L C F f L, L C
The previous configuration table prints 0s and 1s in alternate cells. One cell with a number, one cell empty. Printing the figures in alternate cells is a trick that Turing proposes to configure the machine more easily. The cells between the 0s and 1s are used to keep track of what's going on.
This is the outcome after many steps:
The Universal Turing Machine
The most significant contribution of this paper comes with the Universal Turing Machine.
The Universal Turing Machine is just a regular Turing Machine with a special configuration that makes it unique. This machine, one single machine, has such a configuration that can replicate any other Turing Machine.
The way to accomplish this is by writing down the configuration of the Turing Machine we want to duplicate in the tape. The Universal Turing Machine reads first the tape and then keeps going depending on what it is reading.
To write down the configuration in the tape, Alan Turing came up with a language to encode the configuration that we saw above in the tables. With this language, we would be able to encode the tape of every machine.
We won’t go into the details of this (programming) language, but it’s worth checking an example.
The following would be the tape supplied to a Universal Turing Machine for the simple configuration seen earlier, alternating 0s and 1s.
Using the characters "D," "C," "A," "R," "L," "N," ";" and following some rules, we can encode any configuration into a tape.
That means that this Universal Turing machine can do anything that the others can. But it's just as simple as the others in its functionality. It just changes the configuration of it.
This idea of storing the configuration in the tape is one of the main contributions to Computer Science.
Conclusion
Having a universal configuration that can adapt makes it possible for our computers to do so many things. Storing the instructions –aka, the software– in the tape, instead of having them implemented directly in the machine, allows the same computer to manage a company's accounting or help a designer draw a logo.
Turing's paper laid the ground for most of the computer systems we use today. Alan is not the father of computer systems, but he was like a grandfather to many computer scientists. Everybody agrees that the Turing Machine has been very influential in Computer Science.