PEOPLE IN COMPUTING · FOUNDATION LESSON

Alan Turing

Mathematical computation, wartime cryptanalysis, computer design, and machine intelligence.

Alan Mathison Turing lived from 1912 to 1954. His work connects several subjects in computing history. This lesson introduces those connections, explains a small computational model, and distinguishes mathematical ideas from the machines and research programmes in which he participated.

What you will learn

  • Describe the components of a Turing machine and trace a complete example.
  • Distinguish a universal computational model, a cryptanalytic device, and a stored-program computer.
  • Identify Turing's work within the teams and institutions involved.
  • Describe the question addressed by his 1950 paper using the paper's own historical setting.

No programming knowledge is assumed. The symbols and rules used in the example are explained below.

Education and mathematical work

Turing began studying mathematics at King's College, Cambridge, in 1931. He graduated in 1934 and became a Fellow in 1935. He subsequently studied at Princeton and obtained his doctorate in 1938.

His paper On Computable Numbers, with an Application to the Entscheidungsproblem introduced the machine model now named after him. The model provides a precise way to describe a machine following a sequence of rules.

How a Turing machine works

A Turing machine has a tape of symbol cells, a reading and writing head, and finite states and rules. Actions depend on the current state and scanned symbol. Its tape provides unbounded working memory.

In the example below, a cell holds either a mark, written as 1, or a blank, written as □. We describe a configuration by recording the tape, the head position, and the current state. The rule table specifies every action that our example can take before stopping.

A complete worked example

This original HamTron exercise uses a tape representation called unary. Three consecutive marks represent the number three. The task is to append one mark, changing three marks into four. Start with 111 followed by blank cells. Place the head on the leftmost mark and set the state to Scan.

Rules for the HamTron append-one exercise
StateReadWriteMoveNext state
Scan11RightScan
Scan□1RightHalt

The first rule preserves a mark and moves to the next cell. The second rule fills the first blank and enters the stopping state. Number the cells from zero so the head starts at position 0.

Trace for an input of three marks
ConfigurationVisible cellsHead positionState
Initial111□□0Scan
After action 1111□□1Scan
After action 2111□□2Scan
After action 3111□□3Scan
After action 41111□4Halt

The head moves during the final action and then stops because the new state is Halt. Four marks remain on the tape. For an input of n consecutive marks, the machine takes n actions to pass those marks and one action to append the new mark. The total is n + 1 actions.

Try an empty input. The head immediately reads a blank, writes one mark, moves right, and halts. Our representation therefore treats an empty run of marks as zero and produces one. This behaviour follows directly from the two rules.

Now try two marks, a blank, and another mark. The machine stops after filling that first blank. The rule table does not instruct it to find later marks. The example therefore specifies a contiguous unary input. This illustrates why the input format belongs in an algorithm's definition.

Universal machines and limits

A universal Turing machine simulates another machine from its encoded description. One fixed machine can therefore execute different descriptions.

The halting problem asks whether a described machine stops on a given input. No Turing-machine procedure answers correctly for every machine and input. Individual cases remain analysable, including our append-one example.

Wartime work and collaboration

Turing worked at Bletchley Park during the Second World War on cryptanalysis involving Enigma. He worked with Gordon Welchman and collaborated closely with Joan Clarke on German Naval Enigma.

Polish work preceded the British Bombe. At the July 1939 meeting near Warsaw, Polish cryptanalysts shared advances with French and British representatives. In January 1940, Turing met Polish cryptanalysts in Paris. His conversations with Marian Rejewski helped inform the development of the British Bombe.

The Bombe supported a larger cryptanalytic operation. Its use formed part of the work of the codebreakers and their colleagues. Turing later worked on secure speech, including the Delilah project.

ACE and Manchester

After the war, Turing joined the National Physical Laboratory in 1945 and developed plans for the Automatic Computing Engine, or ACE. He produced the plans in 1946 and worked at NPL until 1948, including a period of leave at Cambridge.

Turing subsequently worked at Manchester. The Small-Scale Experimental Machine, called Baby, first ran a program on 21 June 1948. Its development involved Frederic Williams, Tom Kilburn, and Geoff Tootill. Turing joined the Manchester programme later in 1948 and worked on programming and applications.

A stored-program computer keeps instructions in memory so the machine can fetch and execute them. The universal-machine model describes computation mathematically. The ACE proposal specifies a computer design. The Baby demonstrates a working implementation that executes instructions stored in memory.

The 1950 paper

Computing Machinery and Intelligence appeared in Mind in October 1950. Turing began by examining a question about machine thinking and proposed an imitation game as a way to reformulate the investigation. The opening describes an interrogator communicating through written answers, then asks what changes when a machine takes a participant's place.

The paper also distinguishes a digital computer's store, executive unit, and control, and discusses instructions and universality. These details connect the proposed experiment to the computing technology and concepts under examination. Its questions, arguments, and predictions belong to that historical paper. Studying them requires separating what Turing proposed from what an experiment actually demonstrates.

Later work and historical context

At Manchester, Turing also investigated how interacting and diffusing chemicals could generate biological patterns. His research student Bernard Richards also worked with reaction-diffusion equations. This places his later research at the intersection of mathematics, computation, and biology.

In 1952, Turing was convicted for homosexual activity under the law then in force. He underwent hormonal treatment as a condition of probation. He died in 1954. He received a posthumous royal pardon on 24 December 2013.

Practice and explained answers

Work out each answer before expanding it. Use the explanations and worked examples on this page.

1. What happens to an input of five consecutive marks?

The machine passes the five marks, fills the next blank, and halts with six marks. It takes six actions. The same first rule applies at each existing mark.

2. Does a universal machine need a separate rule table for every task?

Its rules stay fixed while it simulates the machine described by its input.

3. Why should a timeline distinguish an ACE proposal from a machine running a program?

A proposal documents a design. A successful run documents an implementation executing instructions. Those are different historical events, supported by different records.

4. Who contributed to the cryptanalytic work described here?

Earlier Polish work included Marian Rejewski's contributions. Turing and Gordon Welchman contributed to the British work. Joan Clarke worked closely with Turing on Naval Enigma. The operation involved many colleagues.

Editorial credits

Prepared by HamTron Learn. Research checked 5 November 2026.

Research draws on original publications and institutional records held by King's College Cambridge, MIT, the University of Manchester, the National Physical Laboratory, GCHQ, and the Ministry of Justice. The worked example and exercises were developed for this lesson.

Return to Half Echo Learn