next up previous
Next: [Author's] Preface Up: Alan Turing's Manual for Previous: Alan Turing's Manual for

Subsections

Transcriber's preface

This is a transcription of a very interesting document from the early history of computer science -- Alan Turing's manual for an early computer built by the English firm Ferranti as a commercialized version of the prototype computer which had been developed by the Manchester University staff. Turing had moved to Manchester from the National Physical Laboratory (where he had been, for a time, architect of the ACE computer project and responsible for the rather unusual architecture of the ACE). At the time he wrote this manual, he was in charge of what we would now call system programming for the machine, including the development of common tools and the establishment of conventions for library routines.

This was the first of at least three manuals for the machine, and was apparently written before the machine was fully installed and operating (the library input routines, for instance, are described in the future tense, and the description of auxiliary paper-tape-handling hardware is frankly speculative). It was quickly superseded by a second manual for the machine, incorporating some of the material from this one (the introductory material was more or less intact), and adding a description of a second set of conventions for shuffling routines from the disk into electronic storage (``Scheme B''; Turing's original routines were described in the second manual as ``Scheme A''), and a couple of interpretive routines. The table of contents of the second manual, and the complete first chapter, are on line at http://www.computer50.org/mark1/; the direct link is http://www.computer50.org/kgill/mark1/mark1book.html.

A note on the machine Turing was describing

The nomenclature of the early Manchester machines is somewhat confused, and so deserves brief elaboration here. The first computer built at Manchester was the ``baby machine'' of Williams and Kilburn. The original ``baby machine'' had a tiny amount of memory, and just barely enough circuitry to run small programs for, e.g., greatest common divisor. In this initial configuration, it was more a test harness for computer components, most notably its cathode-ray-tube memory, than a useful computer in its own right. However, over time, it was elaborated to the point that it could be, and was, used for useful work, via the addition of more memory tubes, more instructions, a multiplier, a magnetic drum, and the first known use of an index register (though a peculiar one to modern ways of thinking, as its contents could modify opcode as well as address bits). The final state of the prototype hardware is documented in an appendix of Turing's manual.

Once the prototype was operating, the English firm Ferranti was hired to produce a productized, commercialized version of the machine. This commercialized version was similar in overall design to the final state of the prototype hardware, but different in detail; it had a different instruction set, more index registers (B-lines), and added a few other facilities (hardware random number generator, arithmetic on the contents of B-lines, etc.). Ferranti referred to this machine as the ``Mark I", since it was the first computer which they had produced. However, Turing refers to it here as the ``Mark II" (or the ``Ferranti machine"), since it was the second computer which he had worked with at Manchester.

Much more information on the two Mark Is in their various incarnations may be found on line at Manchester University's web site on their own history, which also has numerous photographs of the original machinery and a recent reconstruction of the first ``baby machine'' (the URL, once again, is http://www.computer50.org/mark1/). The reader is also referred to Martin Campbell-Kelly's description of the programming environments at Manchester throughout the life of the Mark I, in Annals of the History of Computing, vol. 2, pp. 130-168; this contains much interesting information on ``Scheme B'' and R. A. Brooker's historically significant Autocode system.

A few words on the historical context

As is obvious, this manual describes programming in absolutely raw machine code, making no concessions to the human frailty of the user. Attitudes on this point varied from group to group in early computing; this sort of ``machine centrism'' was not universal. In particular, David Wheeler in the EDSAC group at Cambridge had managed to cram what we'd now call a crude, but useful assembler into the forty instructions' worth of toggle switches comprising what we'd now call the EDSAC's bootstrap ROM. Turing went straight the other way -- even when taking input from paper tape, his input routines were designed to take that input in a format which looked as much as possible like the physical image of data in a storage tube. (See p. [*]).

Indeed, Turing's absolutism on this point (e.g., requiring users to memorize the obscure 32-symbol teleprinter code used pervasively in his manual, and persistently using little-endian numeric notations even in the text of his manual) was something of a puzzle to many of his colleagues; the memoir of EDSAC project leader Maurice Wilkes includes an anecdote of Turing doing little-endian arithmetic on a chalkboard during a conference talk, to the general befuddlement of the other researchers in attendance.

However, there was a method to this seeming madness. As one might infer from Turing's detailed description of the machine's console, operating procedures, and so forth, and his recommendation of their use as the most effective way of debugging a routine (indeed, going so far as to suggest selectively write-protecting the drum against errant writes by physically removing valves, i.e. vacuum tubes), Turing found direct hands-on contact with the machine to be of great value, and thought that programmers should seek it if possible. Obviously, this requires a detailed understanding of the internal hardware representations of just about everything. This is in marked contrast to the attitude present in the EDSAC group, and most other places, at the time, in which physical contact with the machine was generally restricted to a small number of trained staff. This attitude wasn't always appreciated by the programmers themselves, as Steven Levy's book Hackers documents in its discussion of computers and programmers at MIT at few years later.

A particular curiosity is the description of the routine ACTION and its companions in connection with the ``formal mode of operation'' on pp. [*]-[*]. This may well be the first written description of anything resembling an operating system, though its purpose is described mainly as providing an audit trail for what was done in the run of a problem on a machine. In this connection, it is also interesting to note the ``false cue'' facility, which allowed a half-track of the magnetic drum to serve as a directory for routines elsewhere on the drum. In fact, Turing does refer to tracks devoted to this purpose as ``directories'', though the entries in those directories are keyed by number, and not by the English names of the routines (as they might be in the directory of a modern library or file system); in that sense they are less akin to the directories of a modern file system than, say, the tables of offsets in some modern shared library formats.

Another point of interest is the several references to formal proofs of a program's validity. Turing did publish a complete example of a program proof in the proceedings of a 1949 conference on automatic computing machines at Cambridge -- the very paper whose presentation Wilkes described above. Unfortunately, the proof seems to have had little influence on further development, in part, perhaps, because of the confusing nature of the presentation. In his discussion of the paper, Wilkes states

It would enhance Turing's reputation if I could state that he did in some way anticipate the contribution that [theoretician R. W.] Floyd made many years later. This I cannot do, although Turing did use the word ``assertion'' and he did point out the separate need to show that the execution of the program would terminate. What was missing was the concept of the loop invariant; if he had had the concept, he would have had no difficulty in giving the value of the invariant ...
This assertion deserves perhaps a little comment. While Turing's paper does not cite the invariants of the two loops in his routine as being of particular importance, they are present, as the preconditions of the loop heads, amid a large table of similar assertions about other portions of the routine. (If not, it could hardly be a valid proof!)

While admittedly viewing the situation from a considerably farther remove than Dr. Wilkes, I think it might be more accurate to say that Turing was missing the notion of structured programming -- that there is a set of primitive control constructs (if-then-else, while loops, and subroutine invocations) which can be used to synthesize any program. Given this idea, it is straightforward to come up with Floyd-style inference rules for each of the control constructs, which make it more straightforward to construct proofs whose structure mirrors the structure of the program (as opposed to the ad hoc stew of assertions in Turing's paper). This is consistent with Turing's repeated lament (in section [*] and in the conference paper) of the lack of an adequate notation for program proofs, which follows, in my view, from the lack of a suitable notation for programs. On the other hand, it would regrettably be entirely in character for Turing to be aware of the general usefulness of loop invariants to the construction of proofs, but to regard it as an incidental detail not worth taking time to point out in his brief presentation.

Of course, this is all further obscured by the purely notational confusion experienced by Wilkes, and doubly so by subsequent readers of the conference proceedings, who had to contend with a paper on verification of a factorial routine from which all factorial signs had been omitted. Corrected versions may be found in the volume 14 of the Babbage Institute Reprint Series for the History of Computing, which reprints the conference proceedings, or in the reprint of the paper itself, with commentary, in Annals of the History of Computing, vol. 6, pp. 139-143.

One other point deserves mention. The magnetic drum hardware of the Ferranti machine exchanged data with the machine's main memory by transferring a tube full of data at a time, in units which Turing refers to as ``pages''. Turing also describes purely software conventions for allowing routines on one page to call routines stored on another, which does not reside in main memory at the time. Succeeding hardware and software systems at Manchester had similar conventions, for data as well as code, which were increasingly automated (particularly in Brooker's Autocode system), culminating in the Manchester Atlas machine which, as is well known, was the first to support demand paging in the modern sense.

While Turing was not responsible for the design of the magnetic storage hardware he described, he may well have chosen the terms in which he described it; the term ``page'' is used in much the same way, as part of the same metaphor of ``books'' and ``pages'', in a lecture which Turing gave at the London Mathematical Society in 1947, well before he took the job at Manchester, in which he noted, after a somewhat fanciful digression concerning memories based on physical, paper books, that

If we are to have a really fast machine, then, we must have our information, or at any rate a part of it, in a more accessible form than can be obtained with books. It seems that this can only be done at the expense of compactness and economy, e.g., by cutting the pages out of the books and putting each one into a separate reading mechanism. Some of the methods of storage which are being developed at the present time are not unlike this.
(This lecture has been reprinted in volume 10 of the Babbage Institute's reprint series, which also contains Turing's original report on his ACE design). It is therefore possible that Turing, widely considered to be of most significance to computer science as a theoretician, has made at least one lasting contribution to the day-to-day vocabulary of practical systems programming.

Notes on the transcription

For the most part, I have tried to let the document speak for itself; however, I have added some notes on points where Turing's text was less than completely clear. In particular, I have added lists of relevant instructions to Turing's description of various features of the machine; Turing's original intent seems to have been for the reader to refer to the single long list in the appendices. I have also added a few brief notes on how examples in the manual reflect Turing's other interests and activities, and corrected some obvious typographical errors in the listings, and so forth; these are noted as they occur. All my additions to the text are placed in [square brackets]; the rest is Turing's original text.

I'd like to thank Brian Napper of the University of Manchester for his assistance in proofreading the document; he found a number of typos, mostly introduced by myself, which had escaped my attention. The fault for any remaining errors, of course, is my own.

Lastly, a few notes on this draft. I've tried to note and correct typos where I've found them, but I have not yet checked some of the more complicated math; as noted in the body of the text, the Tchebysheff polynomials and the formulae in the description of the Riemann hypothesis are particularly suspect.


next up previous
Next: [Author's] Preface Up: Alan Turing's Manual for Previous: Alan Turing's Manual for
Robert S. Thau 2000-02-13