Turing the Father of Computer Science

XI

metamathematical — and in their eyes, grander — picture of their practical

accomplishments.

In the same spirit, Gorn noted that two fundamental principles had been

recognized in recent years.

35

First, that hardware and programming were within-

limits interchangeable. Second, that “our general purpose machines” are equiv-

alent with “a certain, as yet ill-defined, universal command language”. During

the late 1950s, Gorn, Carr, and Perlis played leading roles in the USA in the

development of the universal programming language ALGOL 60 (cf. [83]).

36

Gorn and Carr were engaged with Burks’s research agenda on cellular au-

tomata, and with the overarching theme of thinking and learning machines. The

“mathematical machine of the future”, Carr wrote in 1959, “may well be an even

more general purpose machine” than what we have today [28, p.12, my empha-

sis]. Carr’s dream was to achieve “Completely Automatic Programming”. This

meant that, once a proper algorithm was developed, it should be possible for the

machine to decide on its own machine code. The machine of the future “should

be allowed to engineer its own construction”, in contrast to present “fixed code

machines” that are “not self-encoding” [28, p.11].

Emil Post

Researchers in the Soviet Union were also interested in the generation of al-

gorithms by other algorithms; that is, in the design of “compiler-producing

compilers”. Versed in Russian, and having visited several computer laboratories

in the Soviet Union, Carr was aware of the Russian state of the art. Partic-

ularly impressed by Markov’s 1954 book Theory of Algorithms [72], Carr de-

scribed Markov’s “language” as something that “could be used directly as an

input to compilers which are to perform symbol manipulation (such as compiler-

producing compilers)”. Moreover, Carr mentioned that several Russian papers [61,

63, 98] discussed the “extension of such language application to [. . .] other indi-

rect reasoning processes [such] as theorem proving, natural language translation,

and complex decision making” [28, p.190, my emphasis].

Responsive to the books of Rosenbloom and Markov (and to the Russian

literature in general), Carr became attracted to the strong underlying kinship

between Perlis’s work on automatic programming and Chomsky’s research in

mathematical linguistics [29–31]. The kinship was due in no small part to Post

whose work, as Carr observed, had influenced Perlis via Markov and Chomsky

via Rosenbloom [28, p.230, 259].

37

The fields of automatic programming and machine translation were converg-

ing. Perlis’s “string language manipulator”, for example, was proposed to be

used not only with “symbolic operational programs”, but also with “algebraic

language compiler-translators” and “natural language translators” [28, p.230].

Likewise, Carr noted, the construction of automatic dictionaries had “already

begun” with “algebraic languages as Fortran, Unicode, and GP at one end, and

with the language translation experiment at the other [end]” [28, p.259–260].

---

XII

Alan Turing

In 1959, Carr used the notion of a “Universal Turing Machine” to explain a

fundamental insight about automatic programming: one can “simulate a new

not-yet produced digital computer” on an older computer, provided that there

is sufficient storage for the simulation. The first such situation, Carr reflected,

“was the preparation of an interpretative program simulating the IBM 704 on

the IBM 701 before the former was completed” [28, p.236, 239].

Much in line with Carr and Gorn’s 1954 reception of metamathematics and

self-referential arguments in particular, Carr elaborated on the idea of having a

computer simulate itself.

If one universal machine can simulate any other machine of a somewhat smaller

storage capacity (which is what Turing’s statement on universal machines

means), it should therefore be possible for a computer to simulate a version of

itself with a smaller amount of storage.

The practical implication of self simulation, Carr continued, is that it allows

programs to be run that “would perform in the standard fashion, and at the

same time print out pertinent information such as location, instruction, previous

contents of [the accumulator], and the previous contents of the address of the

instruction” [28, p.240].

Insights into interpreters, compilers, and — what we today call — program

portability was, in short, what a universal Turing machine had to offer to Carr

and some of his space cadets.

38

Also British space cadets, like Booth and Stanley Gill, used Turing’s 1936

paper to paint the bigger picture of what they had been accomplishing inde-

pendently of Turing, and what they were going to accomplish with Turing’s

theory as a road map. Booth accredited Turing as the founder of automatic

programming in his opening address at the Working Conference on Automatic

Programming of Digital Computers, held at Brighton in 1959.

39

It was Turing,

Booth proclaimed, who “first enunciated the fundamental theorem upon which

all studies of automatic programming are based” [52, p.1]. Booth continued as

follows:

In its original form the theorem was so buried in a mass of mathematical

logic that most readers would find it impossible to see the wood for the trees.

Simply enunciated, however, it states that any computing machine which has

the minimum proper number of instructions can simulate any other computing

machine, however large the instruction repertoire of the latter. All forms of au-

tomatic programming are merely embodiments of this rather simple theorem

and, although from time to time we may be in some doubt as to how FOR-

TRAN, for example, differs from MATHMATIC or the Ferranti AUTOCODE

from FLOW-MATIC, it will perhaps make things rather easier to bear in mind

that they are simple consequences of Turing’s theorem. [52, p.1]

Booth was appropriating Turing’s work in the field of automatic programming,

and he most likely did this on the basis of Carr and Gorn’s earlier metamathe-

matical insights.

40

---