Alan Turing: a universal Turing machine?
The British mathematician Alan Turing
(1912-1954) is widely regarded as the father of the modern computer. One of his key ideas was that of the Turing machine,
which is a theoretical, idealized version of an actual computer.
A Turing machine is attached to a string of symbols written on a tape
. These symbols can be read and altered by a head
, which can also move the tape one step to the left or to the right, all in accordance with instructions given by a program.
This picture by Jin Wicked
shows a Turing machine in which the role of the machine's head is being played (rather creepily) by Turing's own head.
The tape of a Turing machine is of unlimited length, although at any given point in time, all but finitely many of the positions on the tape are blank. The others are filled with one of a finite collection of symbols, shown in the picture as 0 and 1. A physical computer has a finite amount of storage space, so a Turing machine provides an idealized model of a computer with an infinite amount of storage space.
At any given time, a Turing machine may be in one of a finite number of states
, which can be thought of as the “states of mind” a person performing calculations might be in. The program of a Turing machine is a finite set of instructions. Each instruction tells the machine what to do if it is in state Q1 and reads a symbol A1 from the tape. In this situation, the machine performs the following three operations:
1. Replace symbol A1 on the tape with symbol A2. (These symbols may be the same, and one or both of them may be blank.)
2. Move the tape: either one step to the left, or one step to the right, or not at all.
3. Put the machine into the new state Q2. (This may be the same as Q1.)
If there is no instruction specifying what to do if the machine reads symbol A1 when it is in state Q1, then the machine halts
, and the final state of the tape is regarded as the output.
Turing showed that machines of this form are extremely versatile. One of his key insights is that it is possible to have a universal Turing machine
, which is capable of emulating any other Turing machine. This is widely regarded as the insight that led to the concept of the modern stored-program computer.
The American mathematician Alonzo Church
(1903-1995) also made key contributions to the foundations of computer science. The Church-Turing
thesis is named jointly after him and Turing. It refers to the hypothesis that if an algorithm exists to carry out a calculation, then the same calculation can be carried out by a Turing machine, in particular, by a universal Turing machine.
Given how powerful Turing machines are, it may be surprising that they have theoretical limitations. For example, Turing proved that it is impossible, even in principle, to write a computer program that will always determine whether or not a given Turing machine will eventually halt when given a specified input. This is known as the Halting Problem
. The branch of mathematical science dealing with questions of this type is called computability.
A philosophically interesting question is that of whether a Turing machine is capable of emulating a conscious mind. Some of Douglas Hofstadter's writings, such as his book Gödel, Escher, Bach,
take the point of view that this is in principle possible. Other scholars, such as Roger Penrose, are of the opinion that a conscious mind cannot be emulated by a Turing machine. Penrose once pointed out to Hofstadter that a consequence of Hofstadter's point of view is that it is possible for an integer to be conscious!
However, Hofstadter was already comfortable with this idea.#mathematics #computerscience #sciencesunday