(

*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

*by***The Diamond Age***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***does a very good job of describing***Stephenson***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) |

*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

Despite their humble appearance, these few actions are all that is needed in order to perform

In particular, adding new tapes or head tapes to the

*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

**(this is sometimes known as the***any possible computation***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*In fact, no***Gödel's Incompleteness Theorem**.*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**and it's central to the study of the limits of computation and to the foundations of Mathematics. In***Halting problem***,***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*by***Gödel, Escher, Bach***Douglas R. Hofstadter*and*by***The Emperor's New Mind***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*by***Introduction to Automata Theory, Languages and Computation***John E. Hopcroft, Rajeev Motwani*and*Jeffrey D. Ullman.*(

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

Alan Turing Machines are very useful for all. Thanks for sharing this with us.

ResponderEliminar