Mathematics and Science Fiction: Turing Machines

(Disclaimer: English is my second language, so I want to apologize in advance for there may be mistakes in the text below. If you find any, please let me know so that I can correct it. I'd really appreciate it. Thanks.)   

'"Welcome to Castle Turing," said the lord in a metallic voice.'

When Nell, one of the protagonists of The Diamond Age by Neal Stephenson, enters Castle Turing in the interactive adventure of her Young Lady's Illustrated Primer she doesn't know that she is going to learn about Turing machines. She will later use this knowledge to solve different problems and puzzles posed by the Primer and also to explore the nature of consciousness and the human mind. But, what are Turing machines?

Turing machines were first defined by Alan Turing, one of the most important scientists and mathematicians of the 20th century. He is considered by many as one of the fathers of modern Computer Science and in 2012 we are celebrating the 100th anniversary of his birth. In 1936, Turing introduced an abstract device capable of performing all kinds of symbolic computations, a precursor of modern computers that would become known as the Turing machine.

In The Diamond Age, Stephenson does a very good job of describing Turing machines. I will quote from this science fiction novel in order to provide a gentle and informal introduction to these devices.

Turing machines have a tape divided into cells where symbols are stored. A tape head reads these symbols and performs different actions according to its set of instructions, its internal state and the content of the tape. In Stephenson's version:

'The lock only had a few parts that she could observe: the crank, the bolt, and a pair of brass drums set into the top with digits from 0 to 9 engraved in them (...). The number on the top changed with every link that went into the machine, and it seemed to determine, in a limited way, what the machine would do next (...)'

A Turing machine with its head in state q1 and scanning a cell which stores 0 (image taken from Wikipedia)

An important characteristic of Turing machines is that their tape (their memory) is potentially infinite. Although they only use a finite number of cells at a given time, there is no upper bound on how much cells they can use. Stephenson explains this with a striking metaphor: 

'The chain containing the Duke's program dangled on either side into these holes. Nell tried throwing stones into the holes and never heard them hit bottom; the chain must be unfathomably long.'

The infinite tape of a Turing machine (image taken from Wikipedia)

As for the way the Turing machine works, this is what Nell finds out:

' (...) she had learned that the number happened to be 09, and if the next link in the chain was in the vertical position (which the Duke referred to as a one), the drums would spin around and change the number to 23. But if the next link was, instead, a zero (as the Duke referred to links with horizontal toggles), the number drums would change to 03. But that wasn't all: In this case, the machine would, for some reason, reverse the direction in which the chain was moving through the machine, and also flick the toggle from zero to one. That is, the machine could write on the chain as well as read from it.'

As we can see, the actions that the machine can execute are reduced to moving left of right (and thus exploring another cell of the tape), replacing the symbol on the tape for another one and changing its internal state. In the video below we can see a Turing machine in action (this is a Lego Mindstorms model developed at Aarhus University).

Despite their humble appearance, these few actions are all that is needed in order to perform any possible computation (this is sometimes known as the Church-Turing thesis). In fact, any other computing device could be simulated (albeit very slowly) by a Turing machine with a suitable set of instructions. This is used by Nell to solve one the puzzles:

'(...) she came to a castle with a magnificent organ, powered by air pressure and controlled by a bewildering grid of push-rods, which could play music stored on a roll of paper tape with holes punched through it. A mysterious dark knight had programmed the organ to play a sad, depressing tune, plunging the place into a profound depression so that no one worked or even got out of bed. With some playing around, Princess Nell established that the behavior of the organ could be simulated by an extremely sophisticated arrangement of water-gates, which meant, in turn, that it could just as well be reduced to an unfathomably long and complicated Turing machine program.'

In particular, adding new tapes or head tapes to the Turing machine model does not increase its computational power. As Nell learns by reading a report written by the Duke of Turing:

  'No matter how complicated his designs became, the Duke always found a way to simulate their behavior by putting a sufficiently long chain into one of the traditional Turing machines. That is to say that while the parallel and multidimensional machines worked more quickly than the original model, they didn't really do anything different.'

One the most important results in Turing's seminal paper is that Turing machines, despite being able to run any algorithm, can't solve all possible problems. This, in turn, implies that not all mathematical problems can be solved by computation alone, a result similar to Gödel's Incompleteness Theorem. In fact, no Turing machine can determine in a finite amount of time whether a given Turing machine will stop its computation with a given input or will compute forever. This autorefential problem is known as the Halting problem and it's central to the study of the limits of computation and to the foundations of Mathematics. In The Diamond Age, Nell also seems to know about these limitations, although they are stated in a rather philosophical way which is also related to another of Turing's ideas, the famous Turing Test:  

'In Castle Turing she had learned that a Turing machine could not really understand a human being. But the Primer was, itself, a Turing machine, or so she suspected; so how could it understand Nell?'

If you want to learn more about Turing machines, there are several good popular accounts. Both Gödel, Escher, Bach by Douglas R. Hofstadter and The Emperor's New Mind by Roger Penrose explore, among many other things, the concept of Turing machine and its implications to the possibility of creating an artificial intelligence. For a formal, mathematical approach I recommend Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman.

(You can read this post in Spanish/Puedes leer esta entrada en castellano)