O'Reilly logo

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5  Machines at Work

Turing undoubtedly realized that the introduction of an imaginary computing machine into a mathematical paper was both novel and daring. Like a good mathematician, he has provided definitions and a formal description of these machines. It's not necessary for him to show any examples, but I imagine he knew that his readers wouldn't be satisfied with the merely abstract. They needed something concrete. He will now satisfy that craving.

3. Examples of computing machines.

I. A machine can be constructed to compute the sequence 010101 . . . .

The machine prints a tape that looks like this:

images

Well, not exactly. As Turing will later explain, he prefers his machines to use only alternate squares for printing numeric sequences. The first example machine will actually print a tape like this:

images

To denote the m-configurations of his machines, Turing uses lower-case letters of a German gothic font. These may take some getting used to, so I'll take care to point out potentially troublesome characters. The letters that Turing uses for this first machine are b, c, k, and e. (Watch out: The German k looks like an f.)

The machine is to have the four m-configurations images and is capable ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required