Alan Turing and
the Development of the Electronic Computer

Jonathan Salinas

The development of the modern computer is based on many innovative contributions by mathematicians, logicians, and other theoreticians. We will argue here that that the theoretical work of one individual, the British mathematician Alan Turing, was criti cal to the development of a theoretical framework for the modern computer. We will first examine Turing's life, from his early schooling through the period of his university studies at Cambridge, and his choice of an academic career that would focus on m athematics, logic and applications to science. As we will see, it is during his mathematical studies at Cambridge that Turing was first presented with some of the difficult questions that motivated his work on a theory of computable numbers. Then we wil l argue that Alan Turing's creation of a theoretical computing machine (which he called an "a-machine") in order to solve David Hilbert's Entscheidungsproblem, also served as a theoretical framework for the modern computer. Finally, we consider Turing's top-secret work at Bletchley Park during World War II, developing the "Turing bombe" that cracked the Nazi military code, arguing that this provides an example in which Turing applied his theoretical model of the computer up to the point of the actual construction of a working machine.

Turing's Early Life and Education

Alan Mathison Turing was born in London on June 23, 1912. Since his father's business required that he work in India most of the year, Alan spent some years of his early childhood at a local school while living with his mother and older brother. Howeve r, Turing was required to attend boarding school at times, when his mother had gone on an extended visit to stay with his father in India. Nevertheless, his constant switching of schools at an early age seems not to have adversely affected Turing's educa tional development.

At the age of fourteen, Alan Turing enrolled in the Sherborne Public School (actually an elite private school in England), and early on Turing began to display his love for mathematics and science [1, p. 143]. Even though the study of mathematics was no t strongly supported by his schoolmasters at Sherborne, Turing performed well in his classes and earned a scholarship to King's College at Cambridge [1, p. 144]. As an undergraduate at Cambridge, Turing found himself at a university that would nurture an d develop his mathematical abilities [1, p. 144]. Turing made many significant academic achievements while studying at Cambridge, and quickly set himself on the path to becoming a "successful research mathematician whose accomplishments would be of inter est only to other specialists" [1, p. 145]. But Turing's attendance at a series of lectures given on the foundations of mathematics in the spring of 1935 abruptly changed the course of his academic career and set him on a new path of intellectual inquiry that influenced his academic work, and subsequently influenced the development of the modern computer [1, p. 145].

Turing's Analysis of Hilbert's "Entscheidungsproblem"

David Hilbert's Entscheidungsproblem, or "decision problem" in English, is to determine whether or not all human deductive reasoning can be reduced to brute calculation [1, p. 146]. (For the precise formulation, Turing refers to Hilbert and Ackerman [6, chapter 3, cited in 4]. In other words, Hilbert posed the following question: Is it possible to reduce all human reason to simple algorithmic expressions? An algorithm is a definite calculation procedure that transforms the elements and variables fo rming a set of initial data into those representative elements and variables forming the set of results [3, p. 43]. The question "What, when added to five, will result in seven?" can be represented by the following algorithmically reducible expression:

In general, a function is considered "computable" if there is an algorithm that allows its values to be calculated [3, p. 43].

Alan Turing was first introduced to Hilbert's Entscheidungsproblem during the spring term of 1935 while attending a lecture on foundations of mathematics given by M.H.A. (Max) Newman at Cambridge. Turing was extremely intrigued by the problem and immedi ately set out to prove that no such algorithm exists [1, p. 147]. Turing set out to prove that there is no algorithm that satisfies Hilbert's problem in an interesting and ingenious manner. First off, Turing focused on the actual thought-process that takes place when an individual attempts to develop an algorithm. As one logician notes, Turing argued that an individual can be limited to a few extremely simple basic actions without changing the final outcome of the computation. [1, p. 14]. While this simple, but important analysis shed much light on the Entscheidungsp roblem, the real innovation can be found in the next step of Turing's work on Hilbert's question: Turing contends that a machine can in fact replace a person performing a calculation. In his paper, "On Computable Numbers, with an Application to the Entsc heidungsproblem" Turing notes, "We may compare a man in the process of computing a real number to a machine..." [4, 117]. In his paper, Turing describes the attributes he envisions for his "automatic" or a-machine. He envisions a machine which:

"... is only capable of a finite number of conditions q1, q2, ..., qR which will be called "m-configurations."

Turing's Analysis of Computation

Overall, Turing's analysis of computation aimed at determining the mental processes fundamentally required by an individual performing a computation. The following example, based upon the explanations of Turing and Martin Davis, aims to clarify Turing's original description found in his paper. To begin, imagine that a person is watching a computation in progress. Now, Turing assumed that when one is performing a mathematical calculation (on a piece of paper) it is out of convenience, not necessity, that one uses a large sheet of paper. Imagine the following example of a multiplication calculation:

Diagram not converted

However, Turing notes that there is no reason that one cannot still perform a computation on such a small piece of paper such that only a single symbol could fit on each piece of paper. As a result, Turing imagines a person performing the calculation on a "tape" or a roll of paper. Furthermore, one can imagine the sheet of paper being divided into individual sections or "squares" each bearing a single "symbol." Martin Davis notes that Turing believed this system using the one-dimensional tape was not t he most convenient method for reasoning, but the system creates no fundamental problem [1, p. 149]. Thus the previous calculation would now be completed as follows:

Diagram not converted

To clarify, Turing utilizes this example of a simple mathematical calculation to create a case study for the actual thought processes that take place when a person performs a calculation. The decision about what new symbol to write next depends not only on which symbol the individual is thinking of, but also depends on the individual's current state of mind [1, p. 149]. In other words, even in the case of the simple multiplication problem, the individual's state of mind determines the computation that i s performed. (The individual's state of mind corresponds to the "m-configuration of Turing's machine). As an individual performs this multiplication of two numbers, his mind breaks the numbers apart into separate numbers in order to perform individual ca lculations one after another, but never simultaneously. (Or, as Turing explains, the "scanned symbol" is the only one of which the machine is "directly aware.") For example, an individual would first multiply the two numbers in the units column of the tw o separate numbers (in the given example, the rightmost "7" of "77" would be multiplied by the rightmost "1" of "4,231." The individual would arrive at a product of "7" and "scan" the new symbol onto a new blank square of the partial product. This new square is in fact the rightmost "7" found in "29,617," one of the numbers that comprise the partial product). The individual performing this computation would repeat this calculating process for the individual units of each multiplier, recording the resu lt of each individual multiplication until the first partial product "29,617" results. The process is then repeated for the leftmost "7," (with the added caveat that a "0" is used to denote the change from multiplying by "7" to actually multiplying by "7 0.") However, as Turing noted, the individual still performs these calculations one symbol at a time, with the mind focused only in one single mental state. Thus, having completed the calculation necessary to find the two partial products of the multipl ication, the individual performing the calculation shift's his state of mind, and begins to perform the mathematical operation of addition. Yet it is important to note that even though the individual has shifted their state of mind, the new operation is still performed one step at a time. For example, the individual first adds the units column of the two partial products, "0" + "7," before moving onto the next addition. In the following example, the individual operations that take place during the add ition of the two partial products are shown. Note that the two numbers being added and the sum are in boldface:

This process continues until the final product is determined. Hence, this simple example of multiplication of two numbers "illuminates crucial features of any computation" [1, p. 150].

Thus, Turing's analysis of computation concludes that the individual operates under some important restraints when performing any computation. Specifically, "at each stage of a computation only a small number of symbols receive attention", and "the acti on taken at each stage depends only on the particular symbols receiving attention and on the current state of mind of the person carrying out the computation" [1, p. 150]. In sum, Turing's analysis leads to the conclusion, summarized by Martin Davis, tha t all computations involve the following conditions: * The computation is carried out by writing symbols in squares on a ruled paper tape. * At each step the person performing the computation pays attention to the symbol written in exactly one of these squares. * The next action will depend only on this symbol and the person's state of mind. * This next action will consist of writing a symbol on the square to which he/she has been paying attention and then possibly shifting his/her attention to the square immediately to the left or immediately to the right. [1, pp. 150-151]. After breaking down the actual reasoning process that takes place during a computation, Turing concluded that it is easy to imagine that a person performing a computation can be replaced by a machine. The following section discusses how Turing's concept ion of an "a-machine" contains many features of a modern computer.

Turing's Analysis and Its Relation to the Modern Computer

We now take up Turing's analysis of computation as a theoretical framework for the development of the modern computer. According to Turing's model, the automatic or a-machine contains a tape that is coded with symbols that represent the information that must be read by the computer in order to perform the computation. The different "m-configurations," or programmed instructions, of the computer represent the individual states of mind of a person. In addition, the design of the machine requires that the computer is sensitive to exactly one symbol on the tape, the "scanned square." Thus, depending on the specific "configuration" set and on the individual scanned symbol being read, the machine writes a new symbol on the tape and then either continues to s can the same square or else shifts to a position immediately to the left or right on the tape [1, p. 151]. This is similar to the actual process of writing "code" that used for the modern computer, which evaluates individual symbols or codes according to specific programs or "configurations." Overall, the important conclusion of Turing's analysis of computation is the suggestion that anything computable by any algorithmic process watsoever can be computed by an a-machine [1, p. 151]. As a result, Turing realized that if one can prove that no a-machine cannot perform a certain computation, then one can conclude that there is no algorithmic process that can accomplish this task [1, p. 151]. From this Turing was able to deduce that there does exist some algorithmic expression, specifically a "c omputable number," defined as a real number whose decimal expression is calculable by finite means, that cannot be represented by his a-machines. Therefore, the answer to the Entscheidungsproblem is that it is not possible to reduce all computation to an algorithm.

The Impact of Turing's Work on the Development of the Modern Computer

Turing's innovative examination of a computing machine greatly affected the development of the modern computer. In Turing's essay "Can a Machines Think?" he notes, "The idea behind digital computers may be explained by saying that these machines are int ended to carry out any operations which could be done by a human computer" [5, p. 2102]. In fact, one of the greatest accomplishments of Turing's work on Hilbert's Entscheidungsproblem is that he simultaneously answered Hilbert's question and also develo ped innovative ideas related to the development of a universal computing machine. Prior to Turing's theory of the a-machine, most of the discussion of computing machines discussed the three components of the computer (machine, program, and data) as entir ely separate parts [1, p. 165]. Davis contends, "Turing's universal machine showed that the distinctness of these three categories is an illusion" [1, p. 165]. According to Turing's description of the a-machine, which has subsequently become known as th e "Turing machine," the machine itself possessing various mechanical parts is the hardware. The code on the tape input into the machine provides instructions specifying the specific "configuration" of the machine and functions as the component that has b ecome known as the program. Finally, the actual symbols scanned and written by the machine are in fact the data. Thus, it is the development of a system that allows for the integration and "fluidity" among these three components that has become fundamen tal to contemporary computer science [1, p. 165]. Thus, while working out his proof that there is no algorithmic solution to the Entscheidungsproblem, Turing also developed a theoretical framework for the modern computer.

Turing's Work during World War II

During World War II, the cream of the crop of British intellectuals were chosen to work on various aspects of intelligence for the war effort at Bletchley Park [2, p. 368]. Alan Turing was one of the British academics recruited for intelligence work. T uring was viewed "with considerable awe" by colleagues at Bletchley, and, ultimately, Turing's contributions helped lead to the Nazi defeat in WWII [2, p. 368].

At Bletchley, Turing was assigned to work on cracking the Nazi code of enciphering messages. The Nazis were using an improved, military version of the commercial Enigma machine created by a German electrical engineer Scherbius in 1918 [2, p. 331]. Turi ng was extremely qualified for his new assignment: cracking complex codes quickly. Prior to the start of the war, Turing's work had focused on the theoretical outline for a computing machine, yet Turing had actually developed some machines that possesse d some of the abilities described in his paper on computable number. In fact, Turing had constructed an analog device for calculating the zeros of the Riemann "zeta function" [2, p. 368]. In addition, Turing had designed and built an electrically op erated enciphering machine [2, p. 368]. Thus, it seems assigning Turing to work on deciphering the German Enigma code was the logical choice. At this point, it is necessary to discuss the basic design of the German Enigma in order to understand the difficult challenge that Turing and his colleagues at Bletchley overcame. The German military Enigma is a machine that electrically enciphers and d eciphers letters of the alphabet. Specific machine settings are required to decipher the message because the number of possible settings is so vast. In greater detail: The German Enigma possesses three circular wheels or rotors labeled with the twenty- six letters of the alphabet. The rotors of the machine are aligned to one of its many settings, and messages are electrically enciphered. In other words, the rotors have been mechanized to perform the enciphering of a message according to a specific pat tern [2, p. 332]. For example, to start the actual letter of the real message is encoded according to the setting of the first rotor (there are 26 different possible settings for the first rotor). Next, "the result of first encoding is fed into a second code rotor which rotates by one step once every 26 times" [2, p. 332]. In addition, by feeding the second coding into a third rotor which rotates by one position once every 262 times one encodes a letter, one obtains a code that has a period of 263 [2, p. 332]. In particular there are 17,576 (26(26(26) different starting positions for rotors of the Enigma machine. Later the Germans added other components to the Enigma machine that made breaking the Nazi code more difficult. The addition of a "reflector" inverted encoded messages and sent them back through the rotors. Furthermore, the addition at the front end (wh ich, after reflection, functioned also as the back end) of a "plugboard," known by the German name "Steckelbrett," added increased complexity to the Enigma. Now, upon entering and leaving the machine, the electrical current carrying the encoded message p assed through this plugboard which, rather than being hard-wired, could be set up to interchange any chosen set of non-overlapping pairs of letters, leaving the remaining letters unchanged [2, p. 344]. At first, the Germans only interchanged six pairs o f letters by the plugboard (leaving 14 letters "self-steckered"). Nevertheless, even when only using six pairs of letters, the use of the plugboard resulted in a total of over 1011 different settings to choose from [2, p. 345]! Before the invasion of Poland by Nazi forces, the Poles were making significant progress cracking the German military code. One of the Polish innovations, known as the Polish bomby, was extremely successful in accomplishing the "brute-force" task of quic kly running though the more than 17,000 possible starting positions of the original Enigma machine, and provided encouragement for the code-breakers at Bletchley [2, p. 370]. The method used required the set up of twelve linked mock Enigmas so that the o uter rotor letter of each Enigma is one step further advanced than that of the previous one [2, p. 370]. These mock Enigmas were commercial products, available to the public, that contained the three rotors and reflector, but not the plugboard, of the Ge rman military Enigma [2, p. 339]. The machine was then driven through all 17,576 possible states. The previous work on cracking the German code, performed by the Poles, relied on the brute force of machines and human subtlety. However, Turing's development of his own bombe combined both qualities within the machine [2, p. 370]. Having acquired a mea ns of running through brute force calculations for over 17,000 starting positions of the rotors from the Poles, Turing and others were faced with the difficult task of eliminating the compliations caused by an unknown plugboard setting. In order to crack the German code, Turing first developed an algorithm that provided a method for breaking the Enigma code, and then in collaboration with others designed and constructed a machine that was able to perform operations equivalent to the huma n computations needed. For a detailed and useful analysis of flaws in the design (and use) of the German Enigma that made the code "breakable in principle" see [2, pp. 370-376]. Turing, well versed in mathematics and logic, realized that one could begin with a form of a "logic grid" that identified the possible encoding of letters according to a given rotor setting. These tables were referred to as "menus" [2, p. 370]. Turing's major realization was that the additional "steckering" of the plugboard was severely limited by the information in such a menu. Steckering relationships and rotor settings, combined with a given menu, could be tested for logical "contradictions" that eliminated many possibilities because of the symmetric relationships between the pairs of steckered letters [2, pp. 370-376] and within the internal coding process of the Enigma machine. Thus, in order to test for contradictions (which implied that the correct plugboard setting could be determined, or a rotor setting eliminated, with all the rotor settings tested successively, as in the brute-force method) Turing constructed his own "bombe", the "Turing bombe." The Turing bombes were large, bronze-colored cabinets approximately eight feet tall and seven feet wide. [2, p. 378]. Each bombe possessed a series of circular drums in front, each drum possessing a different latter labeled on it [2, pp. 378-379]. Insid e the machine and inside each drum was a complicated series of wires. The machines were maintained by "Wrens," members of the Women's Reserve Naval Service [2, p. 378]. The Wrens, working eight-hour shifts at a time, were given a "menu," the complex gri d containing the various combinations possible for the twelve letters possibly steckered in the Nazi code, that was placed in the back of the Turing bombes [2, pp. 378-379]. The Wrens then started the machines, and waited for the machine to stop due to a legal or illegal contradiction of letter relationships [2, p. 379]. Overall, one account describes that "The examination of a 12-letter menu required 12 linked mock Enigmas (forming one bombe) which took perhaps 15 minutes to work through all the possib ilities" [2, p. 336], that is, 15 minutes to perform the logical analysis required, electronically, for each of 15,576 distinct possibilities. Turing's work at Bletchley Park seems shows how his theoretical ideas could contribute to the concrete development of the modern computer. Like the a-machines, described in his paper on Hilbert's Entscheidungsproblem, Turing's bombes were analog machines that were capable of performing computations. Turing's bombes followed the specifications of his original framework for the a-machine such that the each letter or "symbol" was analyzed one at a time, and the actual operation performed by the machine (th e analysis of various letter combinations and relationships) follows the restrictions implied by Turing's m-configuration. (In effect, the Wrens work setting up the bombes simulated the "programming" of a computer that takes place today.) Overall, Turing 's work at Bletchley seems to further substantiate the impact of his ideas on the development of the modern computer.

Conclusion

As we have seen, in the course of providing a solution to David Hilbert's Entscheidungsproblem, Alan Turing seems to have developed a theoretical framework for the modern computer. Turing's solution to Hilbert's "decision problem" required an intricate analysis of "computation," and, as a result, Turing was led to argue that there are distinct features of the computational process that are necessary and universal. Turing asserted that the vital components of any computational procedure performed by a person during a calculation could be identified and replicated through a machine. Turing's description of both the computational process, including the way in which a machine could replicate this process, and his actual design and creation of a similar m achine, the Turing bombe, during World War II illustrate the implementation of his theoretical ideas in an early precursor of the modern computer.

Appendix A

Not converted

Note 1 The diagram is taken from Alan Turing: The Enigma; Simon and Schuster; 1983, by Andrew Hodges. It provides a graphical explanation of what happened when a key was pressed on the Enigma Machine. For the sake of simplicity, the diagram only uses an eight-letter alphabet, whereas the real machine used all twenty-six letters. In the example shown, the German cipher clerk typed a "B" and the machine enciphered it as a "D."

Bibliography

Editor's Remarks

Mathematical notation and displays not converted

Back to the index