Turing the Father of Computer Science

XXVI

I conjecture that von Neumann knew that both the ENIAC and the EDVAC were

“Turing complete” and he knew that this insight had no immediate practical

relevance on his computer-building aspirations.

35

Thanks in no small part to the writings of Burks (cf. [41, p.25]).

36

Gorn continued by stating that the as yet ill-defined, universal command

language is “probably, in terms of mathematical logic” equivalent with “the class

of expressions obtainable by ‘general recursive definitions”’. In the early 1960s,

the recursive-function theorist Henry Gordon Rice substantiated Gorn’s hunch

by making an explicit connection between ALGOL 60’s computational power and

the class of general recursive functions [41, Ch.8]. Important to note here is that,

once again, the theoretical insights came after programming practice.

37

Post’s work was, together with Davis’s 1958 book [35], also largely respon-

sible for the advent of “decision procedures” [28, p.223, 225] in automatic pro-

gramming, automata theory, and mathematical linguistics in general — a topic

that lies outside the scope of this article but which is very relevant to understand-

ing the emergence of (what many people seem to call) “theoretical” computer

science.

It was researchers in computational linguistics (like Chomsky, Bar-Hillel,

and especially Perles and Shamir) and soon-to-be-called theoretical computer

scientists (like Rabin, Scott, Ginsburg, and Rice) who demonstrated a thorough

reception of Turing’s work and especially Post’s “correspondence problem” dur-

ing the late 1950s and 1960s (see e.g. [15, 50, 96]).

38

Note that some of these insights were already several years old. I am dis-

cussing Carr’s 1959 work here because I have yet to come across much of his

earlier writings.

39

Turing’s 1936 paper and his follow-up correction [103, 104] were reprinted in

Appendix One of the proceedings [52].

40

I conjecture that Turing never viewed his 1936 paper from this angle —

i.e., that he was not (and did not want to be) a space cadet — and that Booth

and other space cadets did not completely grasp Turing’s work. On the one

hand, of course, that is exactly where the force of Turing’s theory lies; it helped

some researchers — and, more importantly, practitioners working in or with

industry — to see the wood for the trees in unanticipated ways. On the other

hand, many practitioners were not really helped by Turing’s work: there is no

evidence suggesting that if Turing had not existed, that these practitioners would

then have been doing something else. Many advocates of various programming

languages knew that these languages were equivalent. Several languages were

implemented by translating into another competing language. The real issue was

their suitability for human use. (— I thank Parnas for discussing this matter with

---

XXVII

me.) Having said that, I now refer to Robert Bemer’s experience with equivalent

languages. In 1957 he wrote:

Although the ultimate in language does not exist yet, we can console ourselves

meanwhile with compatible (as against common) language. There is much

current evidence that existing algebraic languages are all mappable into one

another by pre-processors. [17, p.115][85]

Bemer’s words make me conclude that some researchers were in need of a solid,

theoretical, unifying principle, such as the universal Turing machine or the uni-

versal programming language ALGOL. Others were satisfied with experimental

evidence. My conclusion here is merely another way of expressing my respect

for the multitude of personal styles in tackling technical problems (— a topic

that I have discussed at length with Peter Naur [40]). Unsurprisingly, it was

the theoretically-inclined space cadets (like Carr, Gorn, and Perlis) who talked

about some implications of Turing’s work during the 1950s.

41

In line with Nofre et al. [85], I am introducing the word “metaphor” here

instead of the historical actors. Nofre et al. elegantly discuss the origins of the

metaphor, going back to postwar cybernetics and Stibitz’s role in 1947 in this

regard. I take gentle issue with their supposition that the language metaphor

had become a central metaphor in the computer programming arena by the

early 1950s. Carr and his space cadets were few in number, exactly because they

took the language metaphor seriously.

42

Regardless of whether Gill was the first to articulate the onion-skin metaphor,

it should at least not go unnoticed here that hierarchical design would become

a hot research topic in later years. In what I take as support for my narrative,

Priestley’s ‘The Invention of Programming Languages’ [94, Ch.8] suggests that

(i) men like Turing (1951), Wilkes (1952), and others understood the idea of “an

interpretive routine enabling one machine to simulate another” and that (ii) in

later years, Booth, Gill, and others associated the universal Turing machine

concept with interpreters for high level programming languages [94, p.191–192].

43

Gorn’s technical reports from the 1960s and onwards were all about: Chom-

sky — Algol — Turing — G¨

odel — Wang — Curry — Carnap — Quine —

Rosenbloom — . . . and so on.

44

There are other examples. Philip R. Bagley, for instance, connected the Uni-

versal Computer-Oriented Language (UNCOL) to Turing’s work. I take his under-

standing of Turing’s work to be weak (and without much practical significance

to him), as his words from 1960 partially indicate:

If UNCOL can express the basic computing steps required by a [universal]

Turing machine, then since all present-day computers are equivalent to [finite

realizations of universal] Turing machines, it can lay claim to being “univer-

sal” from the standpoint of computation alone. [. . .] The limitation of UNCOL

---