On Mahoney's Accounts of Turing

Dated: 

August 2013

The late Michael Mahoney warned his fellow historians of computing not to fall into the trap of viewing everything with the same glasses. The computer, Mahoney said specifically, is not one thing but many different things. He continued as follows:

[T]he same holds true of computing. There is about both terms a descriptive singularity to which we fall victim when, as is now common, we prematurely unite its multiple historical sources into a single stream, treating Charles Babbage's analytical engine and George Boole's algebra of thought as if they were conceptually related by something other than twentieth-century hindsight. [1, p.25-26]

Instead of taking a “machine-centered” view of history, “tracing its origins back to the abacus and the first mechanical calculators and then following its evolution through the generations of mainframe, mini, and micro”, we should examine actual computing practices, including programming practices — as Thomas Haigh elaborated by citing Mahoney in the introduction of Mahoney's collected works [1, p.5,8]. In my words, then, the multitude of programming styles should come to the fore. Terms like “general purpose” and “universal” had different meanings for different historical actors and I thus take Mahoney's challenge to mean that we, historians, need to handle each and every term with great care. Using “general purpose” as a synonym for “Turing universal” is only justified if it conforms to the historical context.

Unfortunately, Mahoney “never took up his own invitation”, said Haigh. Men like McCarthy, Scott, Strachey, Turing, and von Neumann appear in almost every chapter in Mahoney's collected works, but, as Haigh continued,

[Haigh:] [W]e never really learn who these people are, how their ideas were formed and around what kind of practice, what their broader agendas were, or whether anything they said had a direct influence on the subsequent development of programming work. [1, p.8]

 

1. Turing's Stream

Instead of using historical actors as subjects, Mahoney much more often preferred technological concepts. The following paragraph, published in 2002, illustrates Mahoney's typical writing style:

The operating system became the master choreographer in an ever-more complex dance of processes, coordinating them to move tightly among one another, singly and in groups, yet without colliding. The task required the development of sophisticated techniques of exception-handling and dynamic data management, but the possibility of carrying it out at all rested ultimately on the computer's capacity to rewrite its own tape. [1, p.83-84, my emphasis]

Mahoney chose “the operating system” and “the task” at hand as subject matters. And, although his prose is exceptional, it is not clear to me who abode with “the task” and who did not. Or did Mahoney intend to convey that everyone shared a common technological point of view? Moreover, did everyone explain their technology in terms of a tape? — a Turing tape? Or was this solely Mahoney's personal interpretation?

Likewise, in 1990 Mahoney took the computer as the subject matter. He explained “what was new” (but not to whom!) about the computer by resorting to a theoretical concept and, more specifically, a universal Turing machine.

In the case of the computer, what was new was the reliable electronic circuitry that made its underlying theoretical structure realizable in practice. At heart, it was a [universal] Turing machine that operated within the constraints of real time and space. [1, p.87]

In the same paper, Mahoney wrote:

The [universal] Turing machine was an open schema for a potentially infinite range of particular applications. How the computer was going to be used depended on the experience and expectations of the people who were going to use it or were going to design it for others to use. [1, p.87, my emphasis]

It is rather unfortunate that Mahoney kept making this association between universal Turing machines and computers throughout most of his writings. (More examples will follow.) Several historical actors in academia and industry did not think in terms of Turing machines, not even in the 1990s. (Strictly speaking I do not even need to substantiate my counter-claim. The burden of the proof lies on Mahoney who used the universal Turing machine as an overarching theoretical concept to explain history. Nevertheless, in my book [2] I present several sources to support my case.) 

In 1988, Mahoney stated that:

The dual nature of the computer is reflected in its dual origins: hardware in the sequence of devices that stretches from the Pascaline to the ENIAC, software in the series of investigations that reaches from Leibniz's combinatorics to Turing's abstract machines. [1, p.26, my emphasis]

While in principle all computers have the same capacities as universal Turing machines, [...]  [1, p.28]

Similarly, in 1997 Mahoney described Turing's 1936 paper as the origin of the computer:

To a large extent, theoretical computer science continued the line of inquiry that had led to the computer in the first place, namely, the establishments of the limits of what can be computed. [1, p.146]

Moreover, according to my interpretation of Mark Priestley's account, Priestley claims that Mahoney — along with the logician Martin Davis — painted the history of computing in terms of a stream from Turing's 1936 paper to the stored-program computer.

[Priestley:] A widely accepted account sees the adoption of the stored-program design as being the crucial innovation on the way to the development of the `computer as we know it', an innovation in which logic played a crucial role in guiding the direction of development. This view was clearly expressed by the historian of computing, Michael Mahoney [...] [3, p.124]

It would oversimplify a complex historical situation to suggest, with Mahoney and Davis, that the stored-program design emerged simply as a byproduct of theoretical research in logic. [3, p.136-137]

In support of his claim, Priestley cites Mahoney's 1988 words as follows:

[Mahoney:] [I]t is really only in von Neumann's collaboration with the ENIAC team that two quite separate historical strands come together: the effort to achieve high-speed, high-precision, automatic calculation and the effort to design a logic machine capable of significant reasoning. [1, p.26]

According to Mahoney, von Neumann's theoretical insights were based on Turing's 1936 paper and these insights were crucial for the development of stored-program computers.

 

Mahoney Followed Davis

As we have just seen, Priestley puts Mahoney alongside the logician Davis with regard to the ENIAC-EDVAC historiography. To further support the association between Mahoney and Davis, I now turn to a long excerpt (*) from Mahoney's oeuvre — a 2005 excerpt that I will scrutinize again later on and which is presented at the end of this blog post — in which Mahoney referred to “fig. 2” from A.W. Burks & A.R. Burks's 1981 article, The ENIAC: First General Purpose Electronic Computer [4] and in which Mahoney also referred to Davis's 2000 book The Universal Computer: The Road from Leibniz to Turing [5].

In their 1981 article, the Burks explicitly tried to use the words “general purpose” in accordance with the way some historical actors around 1946 did [4, p.336-337]. Towards the end of their article, the authors also gave a formal definition of “general purpose” machine, expressed in terms of what we today call indexing [4, p.385]. Throughout the whole article no reference is made to Turing, nor to Turing machines. In other words, the Burks did not equate “general purpose” with “Turing universal” or “universal” for short.

Davis, on the other hand, frequently does — if not always — associate the words “all purpose” with “universal” in both his book [5] and in his Turing centennial presentation at Princeton. At the latter event in Princeton, Davis bluntly stated 39 minutes into his talk, without giving any references, that Arthur Burks did associate the “all purpose” ENIAC with a “universal” computer. But the Burks did not use the terms “all purpose” or “universal” in their 1981 article. Furthermore, Arthur Burks explicitly stated in his 2001 paper [6, p.181] that he did not view the ENIAC as a Turing universal computer! (In his paper, Arthur Burks also discussed and complained about the myth that has been created about Turing and the invention of the computer — a myth that has come to fruition around the turn of the century, according to Burks [6, p.186-187].)

Unfortunately, also Mahoney disregarded Burks' historiography in a manner very similar to Davis. On the one hand, Mahoney cited the 1981 article and re-used a figure from that article (cf. “fig. 2”) in his own work. On the other hand, he blindly equated “general purpose” with “universal”, as the long excerpt (*), presented at the end of this blog post, evidently shows.

It is thus now clear that Mahoney uncritically followed Davis's account to quite a large extent, disregarding the carefully chosen words of the Burks. Or, to put it crudely, Mahoney viewed the computer with the same, logical, glasses over and over again — glasses that explain everything in terms of universal Turing machines.

 

2. Some Technicalities

As Priestley notes in his book, it is not uncommon to come across technical flaws in historical accounts. Priestley gives an example from Paul Ceruzzi's earlier work in which Ceruzzi confused between the idea of universality and the stored-program principle [3, p.137-138]. In the same spirit, I now scrutinize Mahoney's oeuvre as well.

In 1992, Mahoney wrote:

Because computers store [ — note the present tense! — ] programs and data in the same memory, programming languages allowed unrestricted procedures which could have unrestricted procedures as values; in particular a procedure could be applied to itself. “To date”, Scott claimed, [...] [1, p.155]

Unrestricted procedures here seem to mean, or at least include, recursive procedure calls. Mahoney's association between common storage of instructions (“programs”) and data on the one hand, and programming languages that allow for recursive procedure calls on the other hand, is puzzling to say the least. Was he incorrectly suggesting that recursive procedures can only be implemented on “stored-program” computers? Far better would be to let Scott tell the story; that is, to use Scott's wordings from the start. If it then turns out that Scott did indeed view common storage as a necessary and sufficient condition for recursive procedure calls, then we, historians, would gain insight into how the “stored program” concept influenced Scott's theoretical reasoning.

In 1997, Mahoney wrote that common random-access storage of pure data and instructions implies that the instructions can be modified at runtime. In his own words:

The discipline of computer science has evolved dynamically since the creation of the device that now generally goes by that name, that is, the electronic digital computer with random-access memory in which instructions and data are stored together and hence the instructions can change as the program is running. [1, p.128, my emphasis] 

But more than common random-access storage is needed to actually allow for self-modifying programs. Many programs that have been written during the past decades were not self-modifying even though they were placed in common random-access storage. (Likewise, today there are several computers with random-access memory in which instructions and data are stored together but which intentionally do not provide the specific programming constructs that are needed to ensure that instructions can be changed as the programming is running.) Finally, Mahoney also seemed to suggest, incorrectly, that self-modifying programs cannot be implemented when data and instructions are stored separately or externally (e.g., on paper tape). The problem, in essence, lies once again in Mahoney's choice of subject matter: if he had chosen the historical actor “Dana Scott” as subject, then he would not have been trying to state a universal fact about computing. It is even questionable whether such facts can be stated at all: many historical actors were trying to create a science of programming. Mahoney's writing style suggests that such a science existed, let alone that it (already) exists today.

In 2002, Mahoney wrote that:

As a form of [a universal] Turing machine, the stored-program computer is in principle a self-programming device, limited in practice by finite memory. [1, p.78-79]

Again, a “stored-program” computer is not necessarily a “self-programming” device and a “self-programming” device is not necessarily a “stored-program” computer. Moreover, which historical actors actually used those words?

In 2002 Mahoney also wrote that:

The idea of programs that write programs is inherent in the concept of the universal Turing machine, set forth by Alan M. Turing in 1936. [1, p.78-79, my emphasis]

But Turing's universal machine was not at all about programs that write programs. Compilers are programs that write programs. Interpreters, by contrast, emulate programs — loosely speaking. If one really wants to anachronistically link a universal Turing machine to automatic-programming technology, then the choice should be the interpreter, not the compiler.

 

3. The ENIAC-EDVAC Controversy

Several practitioners and historians alike have attempted to document the roles von Neumann and Turing played in the transition from the ENIAC to the EDVAC. The popular claims vary but one of the strongest ones is of the following over-simplified form: Turing's theoretical 1936 paper greatly influenced von Neumann in that it triggered him to build the first practical realization of a universal Turing machine during the 1940s; namely the EDVAC. (Slightly weaker claims have been made as well; e.g. by referring to the later IAS machine instead of to the EDVAC.) Another formulation states that it was von Neumann's theoretical appreciation for Turing's paper that made the transition from the ENIAC to the EDVAC feasible in the first place.

I now turn to Mahoney's account, shown in (*) below. From the first sentences in (*), it is perhaps not yet entirely clear what Mahoney intended to convey. Was he referring to programming practice, claiming that EDVAC's common store (of both numbers and instructions) and its ability to modify its own instructions drastically simplified the otherwise-tedious task of instructing a computing machine? (If so, I wholeheartedly agree.) Or was he making the stronger claim that the transition was theoretical in nature, that ENIAC's calculational power was intrinsically inferior to that of the EDVAC? As the previous discussion and the rest of (*) indicate, Mahoney was definitely referring to the latter. Moreover, following Davis, he attributed the incentive to transition from the ENIAC to the EDVAC in no small part to developments in mathematical logic, and, specifically, to von Neumann's appreciation for Turing's 1936 paper.

In response to a draft version of the previous paragraph, I have received the following comment from a reviewer.

The excerpt (*) says that unlike ENIAC the 1945 draft EDVAC could “make logical decisions based on the calculations it was carrying AND modify its own instructions.” (capitalization mine). Now, clearly ENIAC could do the first of these. Even in its original configuration there was an elaborate hack involving the use of data output pulses as program control input pulses. [I]t could perform something akin to a conditional branch based on the results of evaluating an expression. As Daylight is aware [...] a computer does not have to incorporate a stored program to be Turing complete, and thus this mechanism has been argued by several to qualify ENIAC for this honor. However, ENIAC could not in its original mode do the second of these things: modifying its own instructions, except in a very limited sense where the address read from a function table would be determined by the contents of memory. In fact the very concept of an “instruction” is hard to map onto the original ENIAC programming method. 

To characterize the ENIAC, or any other machine for that matter, as “a practical realization of a universal Turing machine”, it is not mandatory that it could modify its own instructions in the particular way the reviewer alludes to. Turing's 1936 universal machine does not modify its own instructions, nor does it modify the instructions of the other machines that it simulates. Moreover, Turing's vital perception was that data and instructions can be codified alike. As a result, because universal Turing machines can modify data, they can also modify instructions (albeit in a peculiar manner if perceived from a practical computer-building standpoint).

Now, if Mahoney intended to convey (which I doubt) that the EDVAC could and the ENIAC could not modify its own instructions in that particular manner, then his statement is correct and confusing at the same time. It is confusing because he then makes a statement about programming practice in a paragraph that tries to convey the (incorrect) theoretical message that the EDVAC was computationally superior to the ENIAC. (An alternative is that Mahoney was solely trying to convey a practical message, but this does not fit in with the rest of his oeuvre and with his references to Davis's book and a “universal Turing machine” in (*).)

If Mahoney intended to convey (which I also doubt) that specific historical actors started to view the EDVAC as a practical realization of a universal Turing machine, then he should have specified at least once whom he was writing about. Irrespective of Mahoney's intentions, his expositions about the ENIAC-EDVAC transition and about universal Turing machines in general are unclear and based on a lack of understanding.

The comment from the reviewer continued as follows:

The actual limitations [of the ENIAC] were much more obvious and pressing than the theoretical ones — when a machine has 20 accumulators who cares what it could do with unlimited storage but no other changes?

Theoretically-inclined men like von Neumann, van der Poel, Turing, and Wang might very well have cared about such matters, regardless of the practical irrelevance. Therefore, I do not want to dismiss this theoretical discussion completely; at least not at this stage of my research.


Bibliography

[1] M.S. Mahoney. Histories of Computing. Harvard University Press, 2011.

[2] E.G. Daylight. The Dawn of Software Engineering: from Turing to Dijkstra. Lonely Scholar, 2012.

[3] M. Priestley. A Science of Operations: Machines, Logic and the Invention of Programming. Springer, 2011.

[4] A.W. Burks. The ENIAC: First General Purpose Electronic Computer. IEEE Annals of the History of Computing, 3(4):310389, October 1981.

[5] M. Davis. The Universal Computer: The Road from Leibniz to Turing. Norton, 1st edition, 2000.

[6] A.W. Burks. Turing's theory of infinite computing machines (1936-1937) and its relation to the invention of finite electronic computers (1939-1949). In Theory and Practical Issues on Cellular Automata. Springer, 2001.

 

(*) Long Excerpt from Mahoney's Oeuvre [1, p.59, my emphasis]:

Look at a picture of the ENIAC, the first electronic digital calculator (not yet a full computer, but its immediate predecessor). It is a new device constructed from existing components, as the scheme by Arthur Burks shows (fig. 2). Those components embody its history, or rather the history of which it was a product. At this point it was merely doing electronically, albeit for that reason much more quickly, what other devices of the period were doing electromechanically and previous devices had done mechanically, and one can find indications of that throughout its design. Only in the next iteration of its design, the EDVAC, could it do things no earlier machine had been able to do, namely, make logical decisions based on the calculations it was carrying out and modify its own instructions. The elements of that design have another history, as different from that of ENIAC as the schematic version (fig. 3) is from its circuit diagrams. That is the history of logic machines, reaching back to Leibniz and running through Boole and Turing. The combination of those two histories made the computer in concept a universal Turing machine, limited in practice by its finite speed and capacity. But making it universal, or general-purpose, also made it indeterminate. Capable of calculating any logical function, it could become anything but was in itself nothing (well, as designed, it could always do arithmetic).(**)

(**) For that history, see inter alia Martin Davis, The Universal Computer: The Road from Leibniz to Turing (New York: W.W. Norton, 2000), and Sybille Krämer, Symbolische Maschinen: Die Idee der Formalisierung in geschichtlichem Abriss (Darmstadt: Wissenschaftliche Buchgesellschaft, 1988).

Tags: