Communications of the ACM
Turing's 1936 Paper and the First Dutch Computers
Did Alan Turing's 1936 paper 'On Computable Numbers' influence the early history of computer building?
Credit: theinquirer.com
The following question has polarized the computer-science community: Did Alan Turing's 1936 paper 'On Computable Numbers' influence the early history of computer building? "Yes, certainly" and "no, definitely not" are often-heard answers. A third, more nuanced, response acknowledges a diversity of local computing habits in the 1940s-1950s.
Some historical actors became acquainted with Turing's 1936 paper early on, while others did not. Some researchers depended directly or indirectly on its contents, while others accomplished great feats even without knowing who Turing was. The successful Dutch computer builder Willem van der Poel is one of those few men who not only read about, but also applied, Turing's 1936 universal-machine concept in the history of early post-war computers. Van der Poel thought and programmed very much like Turing himself and was industrially more successful than Turing. Van der Poel's story is told here for the first time.
Around 1947, Nicolaas de Bruijn, just appointed professor at the Hogeschool of Delft (the Netherlands), wrote a research proposal for the construction of an "all-round calculating machine", a "thinking" machine, which would be put to use in the optics department. The accepted proposal was assigned to Willem L. van der Poel, a young physics student at Delft.
Born in 1926, van der Poel was both extremely handy and studious. During the Second World War, he frequently visited his local library where he may have come across Turing's 1936 paper (according to a 2010 interview with the present author). Van der Poel thoroughly understood what computers had and had not to offer. For example, he noted that automatically reducing an equation to a most simple form for humans to understand was not possible. "We have yet to design truly thinking machines," he wrote in his report for de Bruijn [6, p.1]. That report, which is about computer building, also contains references to Hilbert & Ackermann (1938), Turing (1936), and Shannon (1938).
His appeal for logical minimalism in that same report already partially illustrates his ability to connect practice to theory: "Solving a programming problem amounts to finding a necessary, yet minimal, set of instructions. The crux lies in accomplishing as much as you can with as small a number of instructions as possible." [6, p.60, my translation] The term "logical minimalism" is borrowed here from [4].
Leen Kosten, head of the mathematical department of the Dutch government's post and telephone company (PTT) contributed to de Bruijn's project by obtaining several relays for the computer's construction. Those relays led van der Poel to construct the ARCO (Automatische Relais Calculator voor Optische berekeningen) during the late 1940s. A selector switch would allow the user to choose one of multiple "recipes" which the machine would then execute.
Van der Poel graduated at Delft and joined Kosten's laboratory in 1950, leaving the final implementation stages of the ARCO to other physics students, who later called the ARCO the TESTUDO (= turtle) due to its slow speed. Kosten, in turn, had obtained his Ph.D. during the Second World War on the design of analog machines with the purpose of simulating congestion problems in connection with telephone traffic. With van der Poel now at his side, the choice was quickly made to construct a radically new, digital, machine. They designed the PTERA (PTT Elektronische Reken Automaat). Many years later, van der Poel described the transition from the TESTUDO to the PTERA by acknowledging von Neumann's role: "The TESTUDO was still a pre-von-Neumann machine. At that time, I did not yet have the idea of storing instructions and numbers in the same memory. I got that idea after reading the famous `Preliminary discussion of the logical design of an electronic computing instrument' by Burks, Goldstine, and von Neumann [...]" [9, p.8, my translation]
Choosing to store both instructions and numbers in the same store was primarily due to practical concerns, not theoretical reasoning [1, p.115-116]. And there is no reason to believe that this was any different for the theoretically-inclined van der Poel.
As the previous quote suggests, von Neumann's team played a pivotal role on the international scene. To illustrate this further, we remark that the British computer builder Andrew Booth together with his wife Kathleen expressed in the preface of their 1953 book `Automatic Digital Calculators' "their indebtedness to John von Neumann and his staff" at Princeton for "the stimulating period spent as the guests of their Project". Reflecting on the history of computer building, the Booths referred to Leibniz, Pascal, Babbage, Jacquard, and Hollerith. No mention was made of Turing throughout their whole book, except for a brief reference to the ACE computer which had been "under the direction of Womersley, Turing and Colebrook."
(Turing's involvement with computer building was popularized only in later years, by Randell (1973), Hodges (1983), Robinson (1994), Davis (2000), Dyson (2012), and others. Kahn's 1967 book `The Codebreakers' did not cover much about Turing either; I thank Vinton Cerf for bringing it to my attention.)
Moreover, in the section "The universal machine," the Booths referred to "the Analytical Engine" of Babbage and essentially described him as the father of the universal computer. In this regard, they mentioned the machines built by Howard Aiken (1937-1944) and at Bell Labs (1938-1940, 1944), describing them as "universal" and "general purpose".
Based on the Booths' book and many other primary sources, it seems fair to say that computer designers who did consider using a small instruction set did not do this in connection with practically realizing a universal Turing machine. An exception, other than Turing himself, was van der Poel. In the 1952 design of the arithmetical unit of his new ZERO computer, van der Poel referred to Turing's 1936 universal-machine concept, expressing his desire for the simplest computer that was still universal in Turing's theoretical sense [7, p.376] which he elaborated extensively in his Ph.D. dissertation [8].
The ZERO — Zeer Eenvoudig Reken Orgaan (Very Simple Calculating Machine) — was van der Poel's "most beautiful machine" [7], even though it was only built for temporarily usage while awaiting more equipment to construct the PTERA. The ZERO's beauty exemplified logical minimalism and frugality, as the following four examples show. First, van der Poel used the same register to serve both as accumulator and control register. Second, he avoided expensive multiplication and division components in hardware by programming them in terms of addition. Third, he implemented the addition of two numbers in one and the same electronic component by resorting to bit-wise addition sequentialized in time [7][10, p.31]. Fourth, van der Poel pursued further simplicity by opting for four "functionally independent bits" [7]. One bit b1 expressed whether the instruction had to read something from (b1 = 0) or write something to (b1 = 1) the store. Another bit b2 independently expressed whether the accumulator had to be cleared (b2 = 0) or not (b2 = 1). The two bits together (b1b2) then defined four possible combinations: 00, 01, 10, and 11. Because the value of the first bit did not depend on that of the second and vice versa, no decoder was required and, hence, less equipment was needed. The price paid, however, was that "not all combinations were practically useful"; indeed, only four of the seven instructions in the ZERO made practical sense.
Van der Poel later used the same idea for his ZEBRA computer — Zeer Eenvoudig Binair Rekenapparaat (Very Simple Binary Calculating machine) — where 15 bits constituted an instruction. Following similar principles of aesthetics, he strove for "complete duality", realizing full well that "this is seldom of practical importance" [8, p.18-19].
Compared to most machines fabricated in the USA, van der Poel's aesthetic machines were small and cheap, but also extremely slow — as reported in Dutch newspaper articles (see e.g. Nieuw Utrechts Dagblad, 15 September 1953). Nevertheless, the PTERA remained in operation for 12 years. And his follow-up ZEBRA computer, fabricated by STANTEC in England from 1957 onwards, was an even larger success, selling over a dozen machines in Europe. How, then, did van der Poel's relatively small and slow machines compete with the large and fast computers from America?
The answer lies in van der Poel's insistence to program in a thoroughly machine-specific manner. He perfectionized two techniques, optimum coding and underwater programming, and thereby demonstrated a strong similarity with Turing's own programming habits (see e.g. [2]). Optimum coding essentially meant accessing the drum economically; e.g., by interleaving instructions and data on the drum in conformance with the way the program would behave. Underwater programming amounted to minimizing the drum accesses; e.g., by copying an instruction I from the drum to the registers and subsequently modifying the contents of the registers in order to transform I into the next instruction I', and I' into I'', and so forth. Until the drum was accessed a second time, the program was executing "under water," using van der Poel's own terminology.
Van der Poel's machine-specific programming style stood in sharp contrast to what his colleagues at the Mathematical Centre of Amsterdam were delivering. There, Aad van Wijngaarden and Edsger Dijkstra were intentionally trying to abstract from their own computing machines — machines that had started to operate properly in the Dutch computing arena only after van der Poel had already acclaimed international success. Nevertheless, it was the quest for machine-independent programming languages that got momentum during the second half of the 1950s, not van der Poel's fixation on the machine itself.
Around 1960, the Amsterdamers played a significant role in the design and implementation of ALGOL. Two years later, van der Poel's computer-building days ended: he became professor at the Technische Hogeschool Delft and started participating in IFIP's working group on ALGOL. As professor, van der Poel also taught logic and followed up on his Ph.D. dissertation in which he had associated the Sheffer stroke with his own one-instruction Turing universal computer — a computer that existed only on paper and which idealized his four-instruction ZERO machine [8, p.105].
Although logic was dear to him, van der Poel intentionally did not abstract from the finiteness of his physical machinery. In his own words: "TURING does not exercise restraint as regards the size of the machine or the extent of the store. [...] From a practical point of view it is, however, better to restrict oneself to finite machines. Then the latter can no longer be called universal in the sense of TURING [...]" [8, p.102] This quote stands in sharp contrast to the reception of universal Turing machines by the ACM actors Carr, Gorn, and Perlis during the 1950s [3].
Finally, allow me to now speculate that van der Poel, Turing, and von Neumann knew very well what theoreticians know today; namely, that a store is not a necessary condition (nor a sufficient condition) for realizing a practical version of a universal Turing machine. Or, as the historian Olley befittingly puts it, "the stored program is not the only way to achieve a Turing complete machine" [5]. Indeed, these three men were in a position to see that a universal Turing machine was a mathematical model of both the EDVAC and the ENIAC and of other machines. There is no primary sources supporting the popular belief that any of these three men thought they were building the first practical realization of a universal Turing machine.
Guest blogger Edgar G. Daylight is a historian of computing currently working at Eindhoven University of Technology.
[1] A. Akera. Calculating a Natural World: Scientists, Engineers, and Computers During the Rise of U.S. Cold War Research. MIT Press, 2007.
[2] M. Campbell-Kelly. Alan Turing's Other Universal Machine: Reflections on the Turing ACE computer and its influence. Communications of the ACM, 55(7):31-33, 2012.
[3] E.G. Daylight. Towards a Historical Notion of "Turing — the Father of Computer Science." History and Philosophy of Logic. Paper available here.
[4] L. De Mol and M. Bullynck. A short history of small machines. In CiE 2012 - How the World Computes, 2012.
[5] A. Olley. Existence Precedes Essence - Meaning of the Stored-Program Concept. In IFIP Advances in Information and Communication Technology, pages 169-178. Springer, 2010.
[6] W. van der Poel. Inzending 1946/47 van Van der Poel op de prijsvraag genaamd "1+1=10". Technical report, Delft, 1948.
[7] W.L. van der Poel. A Simple Electronic Digital Computer. Applied Scientific Research, 2:367-399, 1952.
[8] W.L. van der Poel. The Logical Principles of Some Simple Computers. PhD thesis, Universiteit van Amsterdam, February 1956.
[9] W.L. van der Poel. Een leven met computers. TU Delft, October 1988.
[10] C.J.D.M. Verhagen. Rekenmachines in Delft. Uitgave van de Commissie Rekenmachines van de Technische Hogeschool te Delft, 1960.
No entries found