A Book from Alan Turing… and a Mysterious Piece of Paper

A Book from Alan Turing...

How I Got the Book

In May 2017, I got an email from a former high-school teacher of mine named George Rutter: “I have a copy of Dirac’s big book in German (Die Prinzipien der Quantenmechanik) that was owned by Alan Turing, and following your book Idea Makers it seemed obvious that you were the right person to own this.” He explained that he’d got the book from another (by then deceased) former high-school teacher of mine, Norman Routledge, who I knew had been a friend of Alan Turing’s. George ended, “If you would like the book, I could give it to you the next time you are in England.”

A couple of years passed. But in March 2019 I was indeed in England, and arranged to meet George for breakfast at a small hotel in Oxford. We ate and chatted, and waited for the food to be cleared. Then the book moment arrived. George reached into his briefcase and pulled out a rather unassuming, typical mid-1900s academic volume.

P. A. M. Dirac's Die Prinzipien der Quantenmechanik

I opened the front of the book, wondering if it might have a “Property of Alan Turing” sticker or something. It didn’t. But what it did have (in addition to an inscription saying “from Alan Turing’s books”) was a colorful four-page note from Norman Routledge to George Rutter, written in 2002.

I had known Norman Routledge when I was a high-school student at Eton in the early 1970s. He was a math teacher, nicknamed “Nutty Norman”. He was charmingly over the top in many ways, and told endless stories about math and other things. He’d also been responsible for the school getting a computer (programmed with paper tape, and the size of a desk)—that was the very first computer I ever used.

At the time, I didn’t know too much about Norman’s background (remember, this was long before the web). I knew he was “Dr. Routledge”. And he often told stories about people in Cambridge. But he never mentioned Alan Turing to me. Of course, Alan Turing wasn’t famous yet (although, as it happens, I’d already heard of him from someone who’d known him at Bletchley Park during the Second World War).

Alan M. Turing by Sara Turing

Alan Turing still wasn’t famous in 1981 when I started studying simple programs, albeit in the context of cellular automata rather than Turing machines. But looking through the card catalog at the Caltech library one day, I chanced upon a book called Alan M. Turing by Sara Turing, his mother. There was lots of information in the book—among other things, about Turing’s largely unpublished work on biology. But I didn’t learn anything about a connection to Norman Routledge, because the book didn’t mention him (although, as I’ve now found out, Sara Turing did correspond with Norman about the book, and Norman ended up writing a review of it).

A decade later, very curious about Turing and his (then still unpublished) work on biology, I arranged to visit the Turing Archive at King’s College, Cambridge. Soon I’d gone through what they had of Turing’s technical papers, and with some time to spare, I thought I might as well ask to see his personal correspondence too. And flipping through it, I suddenly saw a couple of letters from Alan Turing to Norman Routledge.

By that time, Andrew Hodges’s biography—which did so much to make Turing famous—had appeared, and it confirmed that, yes, Alan Turing and Norman Routledge had indeed been friends, and in fact Turing had been Norman’s PhD advisor. I wanted to ask Norman about Turing, but by then Norman was retired and something of a recluse. Still, when I finished A New Kind of Science in 2002 (after my own decade of reclusiveness) I tracked him down and sent him a copy of the book with an inscription describing him as “My last mathematics teacher”. Some correspondence ensued, and in 2005 I was finally in England again, and arranged to meet Norman for a quintessentially English tea at a fancy hotel in London.

We had a lovely chat about many things, including Alan Turing. Norman started by saying that he’d really known Turing mostly socially—and that that was 50 years ago. But still he had plenty to say about him. “He was a loner.” “He giggled a lot.” “He couldn’t really talk to non-mathematicians.” “He was always afraid of upsetting his mother.” “He would go off in the afternoon and run a marathon.” “He wasn’t very ambitious (though ‘one wasn’t’ at King’s in those days).” Eventually the conversation came back to Norman. He said that even though he’d been retired for 16 years, he still contributed items to the Mathematical Gazette, in order, he said, “to unload things before I pass to a better place”, where, he added, somewhat impishly, “all mathematical truths will surely be revealed”. When our tea was finished, Norman donned his signature leather jacket and headed for his moped, quite oblivious to the bombings that had so disrupted transportation in London on that particular day.

That was the last time I saw Norman, and he died in 2013. But now, six years later, as I sat at breakfast with George Rutter, here was this note from him, written in 2002 in his characteristically lively handwriting:

Norman's letter

Norman's letter, page 1 Norman's letter, page 2 Norman's letter, page 3 Norman's letter, page 4 Image Map

I read it quickly at first. It was colorful as always:

I got Alan Turing’s book from his friend & executor Robin Gandy (it was quite usual at King’s for friends to be offered books from a dead man’s library—I selected the collected poems of A. E. Housman from the books of Ivor Ramsay as a suitable memento: he was the Dean & jumped off the chapel [in 1956])…

Later in the note he said:

You ask about where, eventually, the book should go—I would prefer it to go to someone (or some where) wh. wd. appreciate the Turing connection, but really it is up to you.

Stephen Wolfram sent me his impressive book, but I’ve done no more than dip into it…

He ended by congratulating George Rutter for having the courage to move (as it turned out, temporarily) to Australia in his retirement, saying that he’d “toyed with moving to Sri Lanka, for a cheap, lotus-eating existence”, but added “events there mean I was wise not to do so” (presumably referring to the Sri Lankan Civil War).

What’s In the Book?

OK, so here I was with a copy of a book in German written by Paul Dirac, that was at one time owned by Alan Turing. I don’t read German, and I’d had a copy of the same book in English (which was its original language) since the 1970s. Still, as I sat at breakfast, I thought it only proper that I should look through the book page by page. After all, that’s a standard thing one does with antiquarian books.

I have to say that I was struck by the elegance of Dirac’s presentation. The book was published in 1931, yet its clean formalism (and, yes, despite the language barrier, I could read the math) is pretty much as one would write it today. (I don’t want to digress too much about Dirac, but my friend Richard Feynman told me that at least to him, Dirac spoke only monosyllabically. Norman Routledge told me that he had been friends in Cambridge with Dirac’s stepson, who became a graph theorist. Norman quite often visited the Dirac household, and said the “great man” was sometimes in the background, always with lots of mathematical puzzles around. I myself unfortunately never met Dirac, though I’m told that after he finally retired from Cambridge and went to Florida, he lost much of his stiffness and became quite social.)

But back to Turing’s copy of Dirac’s book. On page 9 I started to see underlinings and little marginal notes, all written in light pencil. I kept on flipping pages. After a few chapters, the annotations disappeared. But then, suddenly, tucked into page 127, there was a note:

German note

It was in German, with what looked like fairly typical older German handwriting. And it seemed to have something to do with Lagrangian mechanics. By this point I’d figured out that someone must have had the book before Turing, and this must be a note made by that person.

I kept flipping through the book. No more annotations. And I was thinking I wouldn’t find anything else. But then, on page 231, a bookmark—with a charmingly direct branding message:

Heffers bookmark

Would there be anything more? I continued flipping. Then, near the end of the book, on page 259, in a section on the relativistic theory of electrons, I found this:

Folded note

I opened the piece of paper:

Opened note

I recognized it immediately: it’s lambda calculus, with a dash of combinators. But what on Earth was it doing here? Remember, the book is about quantum mechanics. But this is about mathematical logic, or what’s now considered theory of computation. Quintessential Turing stuff. So, I immediately wondered, did Turing write this page?

Even as we were sitting at breakfast, I was looking on the web for samples of Turing’s handwriting. But I couldn’t find many calculational ones, so couldn’t immediately conclude much. And soon I had to go, carefully packing the book away, ready to pursue the mystery of what this page was, and who wrote it.

About the Book

Before anything else, let’s talk about the book itself. Dirac’s The Principles of Quantum Mechanics was published in English in 1930, and very quickly also appeared in German. (The preface by Dirac is dated May 29, 1930; the one from the translator—Werner Bloch—August 15, 1930.) The book was a landmark in the development of quantum mechanics, systematically setting up a clear formalism for doing calculations, and, among other things, explaining Dirac’s prediction of the positron, which would be discovered in 1932.

Why did Alan Turing get the book in German rather than English? I don’t know for sure. But in those days, German was the leading language of science, and we know Alan Turing knew how to read it. (After all, the title of his famous Turing machine paper “On Computable Numbers, with an Application to the Entscheidungsproblem” had a great big German word in it—and within the body of the paper he referred to the rather obscure Gothic characters he used as “German letters”, contrasting them, for example, with Greek letters.)

Did Alan Turing buy the book, or was he given it? I don’t know. On the inside front cover of Turing’s copy of the book is a pencil notation “20/-”, which was standard notation for “20 shillings”, equal to £1. On the right-hand page, there’s an erased “26.9.30”, presumably meaning 26 September, 1930—perhaps the date when the book was first in inventory. Then to the far right, there’s an erased “20-.”, perhaps again the price. (Could this have been a price in Reichsmarks, suggesting the book was sold in Germany? Even though at that time 1 RM was worth roughly 1 shilling, a German price would likely have been written as, for example, “20 RM”.) Finally, on the inside back cover there’s “c 5/-”—maybe the (highly discounted) price for the book used.

Let’s review the basic timeline. Alan Turing was born June 23, 1912 (coincidentally, exactly 76 years before Mathematica 1.0 was released). He went as an undergraduate to King’s College, Cambridge in the fall of 1931. He got his undergraduate degree after the usual three years, in 1934.

In the 1920s and early 1930s, quantum mechanics was hot, and Alan Turing was interested in it. From his archives, we know that in 1932—as soon as it was published—he got John von Neumann’s Mathematical Foundations of Quantum Mechanics (in its original German). We also know that in 1935, he asked the Cambridge physicist Ralph Fowler for a possible question to study in quantum mechanics. (Fowler suggested computing the dielectric constant of water—which actually turns out to be a very hard problem, basically requiring full-fledged interacting quantum field theory analysis, and still not completely solved.)

When and how did Turing get his copy of Dirac’s book? Given that there seems to be a used price in the book, Turing presumably bought it used. Who was its first owner? The annotations in the book seem to be concerned primarily with logical structure, noting what should be considered an axiom, what logically depends on what, and so on. What about the note tucked into page 127?

Well, perhaps coincidentally, page 127 isn’t just any page: it’s the page where Dirac talks about the quantum principle of least action, and sets the stage for the Feynman path integral—and basically all modern quantum formalism. But what does the note say? It’s expanding on equation 14, which is an equation for the time evolution of a quantum amplitude. The writer has converted Dirac’s A for amplitude into a ρ, possibly reflecting an earlier (fluid-density analogy) German notation. Then the writer attempts an expansion of the action in powers of (Planck’s constant over 2π, sometimes called Dirac’s constant).

But there doesn’t seem to be a lot to be gleaned from what’s on the page. Hold the page up to the light, though, and there’s a little surprise—a watermark reading “Z f. Physik. Chem. B”:

Z f. Physik. Chem. B watermark

That’s a short form of Zeitschrift für physikalische Chemie, Abteilung B—a German journal of physical chemistry that began publication in 1928. Was the note perhaps written by an editor of the journal? Here’s the masthead of the journal for 1933. Conveniently, the editors are listed with their locations, and one stands out: Born · Cambridge.

Zeitschrift für physikalische Chemie, Abteilung B

That’s Max Born, of the Born interpretation, and many other things in quantum mechanics (and also the grandfather of the singer Olivia Newton-John). So, was this note written by Max Born? Unfortunately it doesn’t seem like it: the handwriting doesn’t match.

OK, so what about the bookmark at page 231? Here are the two sides of it:

Heffers bookmark

The marketing copy is quaint and rather charming. But when is it from? Well, there’s still a Heffers Bookshop in Cambridge, though it’s now part of Blackwell’s. But for more than 70 years (ending in 1970) Heffers was located, as the bookmark indicates, at 3 and 4 Petty Cury.

But there’s an important clue on the bookmark: the phone number is listed as “Tel. 862”. Well, it turns out that in 1939, most of Cambridge (including Heffers) switched to 4-digit numbers, and certainly by 1940 bookmarks were being printed with “modern” phone numbers. (English phone numbers progressively got longer; when I was growing up in England in the 1960s, our phone numbers were “Oxford 56186” and “Kidmore End 2378”. Part of why I remember these numbers is the now-strange-seeming convention of always saying one’s number when answering the phone.)

But, OK, so the bookmark was from before 1939. But how much before? There are quite a few scans of old Heffers ads to be found on the web—and from at least 1912 (along with “We solicit the favour of your enquiries…”) they list “Telephone 862”, helpfully adding “(2 lines)”. And there are even some bookmarks with the same design to be found in copies of books from as long ago as 1904 (though it’s not clear they were original to the books). But for our purposes it seems as if we can reasonably conclude that our book came from Heffers (which was the main bookstore in Cambridge, by the way) sometime between 1930 and 1939.

The Lambda Calculus Page

OK, so we know something about when the book was bought. But what about the “lambda calculus page”? When was it written? Well, of course, lambda calculus had to have been invented. And that was done by Alonzo Church, a mathematician at Princeton, in an initial form in 1932, and in final form in 1935. (There had been precursors, but they hadn’t used the λ notation.)

There’s a complicated interaction between Alan Turing and lambda calculus. It was in 1935 that Turing had gotten interested in “mechanizing” the operations of mathematics, and had invented the idea of a Turing machine, and used it to solve a problem in the foundations of mathematics. Turing had sent a paper about it to a French journal (Comptes rendus), but initially it was lost in the mail; and then it turned out the person he’d sent it to wasn’t around anyway, because they’d gone to China.

But in May 1936, before Turing could send his paper anywhere else, Alonzo Church’s paper arrived from the US. Turing had been “scooped” once before, when in 1934 he created a proof of the central limit theorem, only to find that there was a Norwegian mathematician who’d already given a proof in 1922.

It wasn’t too hard to see that Turing machines and lambda calculus were actually equivalent in the kinds of computations they could represent (and that was the beginning of the Church–Turing thesis). But Turing (and his mentor Max Newman) got convinced that Turing’s approach was different enough to deserve separate publication. And so it was that in November 1936 (with a bug fix the following month), Turing’s famous paper “On Computable Numbers…” was published in the Proceedings of the London Mathematical Society.

To fill in a little more of the timeline: from September 1936 to July 1938 (with a break of three months in the summer of 1937), Turing was at Princeton, having gone there to be, at least nominally, a graduate student of Alonzo Church. While at Princeton, Turing seems to have concentrated pretty completely on mathematical logic—writing several difficult-to-read papers full of Church’s lambdas—and most likely wouldn’t have had a book about quantum mechanics with him.

Turing was back in Cambridge in July 1938, but already by September of that year he was working part-time for the Government Code and Cypher School—and a year later he moved to Bletchley Park to work full time on cryptanalysis. After the war ended in 1945, Turing moved to London to work at the National Physical Laboratory on producing a design for a computer. He spent the 1947–8 academic year back in Cambridge, but then moved to Manchester to work on building a computer there.

In 1951, he began working in earnest on theoretical biology. (To me it’s an interesting irony that he seems to have always implicitly assumed that biological systems have to be modeled by differential equations, rather than by something discrete like Turing machines or cellular automata.) He also seems to have gotten interested in physics again, and by 1954 even wrote to his friend and student Robin Gandy that “I’ve been trying to invent a new Quantum Mechanics” (though he added, “but it won’t really work”). But all this came to an end on June 7, 1954, when Turing suddenly died. (My own guess is that it was not suicide, but that’s a different story.)

OK, but back to the lambda calculus page. Hold it up to the light, and once again there’s a watermark:

Excelsior watermark

So it’s a British-made piece of paper, which seems, for example, to make it unlikely to have been used in Princeton. But can we date the paper? Well, after some help from the British Association of Paper Historians, we know that the official manufacturer of the paper was Spalding & Hodge, Papermakers, Wholesale and Export Stationers of Drury House, Russell Street off Drury Lane, Covent Garden, London. But this doesn’t help as much as one might think—because their Excelsior brand of machine-made paper seems to have been listed in catalogs all the way from the 1890s to 1954.

What Does the Page Say?

What does the page say?

OK, so let’s talk in more detail about what’s on the two sides of the page. Let’s start with the lambdas.

These are a way of defining “pure” or “anonymous” functions, and they’re a core concept in mathematical logic, and nowadays also in functional programming. They’re common in the Wolfram Language, and they’re pretty easy to explain there. One writes f[x] to mean a function f applied to an argument x. And there are lots of named functions that f can be—like Abs or Sin or Blur. But what if one wants f[x] to be 2x+1? There’s no immediate name for that function. But is there still something we can write for f that will make f[x] be this?

The answer is yes: in place of f we write Function[a, 2a+1]. And in the Wolfram Language, Function[a, 2a+1][x] is defined to give 2x+1. The Function[a, 2a+1] is a “pure” or “anonymous” function, that represents the pure operation of doubling and adding 1.

Well, λ in lambda calculus is the exact analog of Function in the Wolfram Language—and so for example λa.(2a+1) is equivalent to Function[a, 2a+1]. (It’s worth noting that Function[b, 2b+1] is equivalent; the “bound variable” a or b is just a placeholder—and in the Wolfram Language it can be avoided by using the alternative notation (2#+1)&.)

In traditional mathematics, functions tend to be thought of as things that map inputs (like, say, integers) to outputs (that are also, say, integers). But what kind of a thing is Function (or λ)? It’s basically a structural operator that takes expressions and turns them into functions. That’s a bit weird from the point of view of traditional mathematics and mathematical notation. But if one’s thinking about manipulating arbitrary symbols, it’s much more natural, even if at first it still seems a little abstract. (And, yes, when people learn the Wolfram Language, I can always tell they’ve passed a certain threshold of abstract understanding when they get the idea of Function.)

OK, but the lambdas are just part of what’s on the page. There’s also another, yet more abstract concept: combinators. See the rather obscure-looking line PI1IIx? What does it mean? Well, it’s a sequence of combinators, or effectively, a kind of abstract composition of symbolic functions.

Ordinary composition of functions is pretty familiar from mathematics. And in Wolfram Language one can write f[g[x]] to mean “apply f to the result of applying g to x”. But does one really need the brackets? In the Wolfram Language f@g@x is an alternative notation. But in this notation, we’re relying on a convention in the Wolfram Language: that the @ operator associates to the right, so that f@g@x is equivalent to f@(g@x).

But what would (f@g)@x mean? It’s equivalent to f[g][x]. And if f and g were ordinary functions in mathematics, this would basically be meaningless. But if f is a higher-order function, then f[g] can itself be a function, which can perfectly well be applied to x.

OK, there’s another piece of complexity here. In f[x] the f is a function of one argument. And f[x] is equivalent to Function[a, f[a]][x]. But what about a function of two arguments, say f[x, y]? This can be written Function[{a,b}, f[a, b]][x, y]. But what about Function[{a}, f[a, b]]? What would this be? It’s got a “free variable” b just hanging out. Function[{b}, Function[{a}, f[a, b]]] would “bind” that variable. And then Function[{b}, Function[{a}, f[a, b]]][y][x] gives f[x, y] again. (The process of unwinding functions so that they have single arguments is called “currying”, after a logician named Haskell Curry.)

If there are free variables, then there’s all sorts of complexity about how functions can be composed. But if we restrict ourselves to Function or λ objects that don’t have free variables, then these can basically be freely composed. And such objects are called combinators.

Combinators have a long history. So far as one knows, they were first invented in 1920 by a student of David Hilbert’s named Moses Schönfinkel. At the time, it had only recently been discovered that one didn’t need And and Or and Not to represent expressions in standard propositional logic: it was sufficient to use the single operator that we’d now call Nand (because, for example, writing Nand as ·, Or[a, b] is just (a·a)·(b·b)). Schönfinkel wanted to find the same kind of minimal representation of predicate logic, or in effect, logic including functions.

And what he came up with was the two “combinators” S and K. In Wolfram Language notation, K[x_][y_] x and S[x_][y_][z_] x[z][y[z]]. Now, here’s the remarkable thing: it turns out to be possible to use these two combinators to perform any computation. So, for example, S[K[S]][S[K[S[K[S]]]][S[K[K]]]] can be used as a function to add two integers.

It is, to put it mildly, quite abstract stuff. But now that one’s understood Turing machines and lambda calculus, it’s possible to see that Schönfinkel’s combinators actually anticipated the concept of universal computation. (And what’s more remarkable still, the definitions of S and K from 1920 are almost minimally simple, reminiscent of the very simplest universal Turing machine that I finally suggested in the 1990s, and was proved in 2007.)

But back to our page, and the line PI1IIx. The symbols here are combinators, and they’re all intended to be composed. But the convention was that function composition should be left-associative, so that fgx should be interpreted not like f@g@x as f@(g@x) or f[g[x]] but rather like (f@g)@x or f[g][x]. So, translating a bit for convenient Wolfram Language use, PI1IIx is p[i][one][i][i][x].

Why would someone be writing something like this? To explain that, we have to talk about the concept of Church numerals (named after Alonzo Church). Let’s say we’re just working with symbols and with lambdas, or combinators. Is there a way we use these to represent integers?

Well, how about just saying that a number n corresponds to Function[x, Nest[f, x, n]]? Or, in other words, that (in shorter notation) 1 is f[#]&, 2 is f[f[#]]&, 3 is f[f[f[#]]]&, and so on. This might seem irreducibly obscure. But the reason it’s interesting is that it allows us to do everything completely symbolically and abstractly, without ever having to explicitly talk about something like integers.

With this setup, imagine, for example, adding two numbers: 3 can be represented as f[f[f[#]]]&, and 2 is f[f[#]]&. We can add them just by applying one of them to the other:

f[f[f[#]]] & [f[f[#]] &]
&#10005

f[f[f[#]]] & [f[f[#]] &]

OK, but what is the f supposed to be? Well, just let it be anything! In a sense, “go lambda” all the way, and represent numbers by functions that take f as an argument. In other words, make 3 for example be Function[f, f[f[f[#]]]&] or Function[f, Function[x, f[f[f[x]]]]. (And, yes, exactly when and how you need to name variables is the bane of lambda calculus.)

Here’s a fragment from Turing’s 1937 paper “Computability and λ-Definability” that sets things up exactly as we just discussed:

Fragment from "Computability and λ-Definability"

The notation is a little confusing. Turing’s x is our f, while his x' (the typesetter did him no favor by inserting space) is our x. But it’s exactly the same setup.

OK, so let’s take a look at the line right after the fold on the front of the page. It’s I1IIYI1IIx. In Wolfram Language notation this would be i[one][i][i][y][i][one][i][i][x]. But here, i is the identity function, so i[one] is just one. Meanwhile, one is the Church numeral for 1, or Function[f, f[#]&]. But with this definition one[a] becomes a[#]& and one[a][b] becomes a[b]. (By the way, i[a][b], or Identity[a][b], is also a[b].)

It keeps things cleaner to write the rules for i and one using pattern matching rather than explicit lambdas, but the result is the same. Apply these rules and one gets:

i[one][i][i][y][i][one][i][i][x] //. {i[x_] → x, one[x_][y_] → x[y]}
&#10005

i[one][i][i][y][i][one][i][i][x] //.
					 {i[x_] -> x, one[x_][y_] -> x[y]}

And that’s exactly the same as the first reduction shown:

Excerpt 1

OK, let’s look higher on the page again now:

Excerpt 2

There’s a rather confusing “E” and “D”, but underneath these say “P” and “Q”, so we can write out the expression, and evaluate it (note that here—after some confusion with the very last character—the writer makes both [ ... ] and ( … ) represent function application):

Function[a, a[p]][q]
&#10005

Function[a, a[p]][q]

OK, so this is the first reduction shown. To see more, let’s substitute in the form of Q:

q[p] /. q → Function[f, f[i][one][i][i][x]]
&#10005

q[p] /.
					 q -> Function[f, f[i][one][i][i][x]]

We get exactly the next reduction shown. OK, so what about putting in the form for P?

Excerpt 3

Here’s the result:

p[i][one][i][i][x] /. {p → Function[r, r[Function[s, s[one][i][i][y]]]]}
&#10005

p[i][one][i][i][
  x] /.
   {p -> Function[r, r[Function[s, s[one][i][i][y]]]]}

And now using the fact that i is the identity, we get:

i[Function[s, s[one][i][i][y]]][one][i][i][x] /. {i[x_] → x}
&#10005

i[Function[s, s[one][i][i][y]]][one][i][i][x] /.
					 {i[x_] -> x}

But oops. This isn’t the next line written. Is there a mistake? It’s not clear. Because, after all, unlike in most of the other cases, there isn’t an arrow indicating that the next line follows from the previous one.

OK, so there’s a mystery there. But let’s skip ahead to the bottom of the page:

Excerpt 4

The 2 here is a Church numeral, defined for example by the pattern two[a_][b_] a[a[b]]. But notice that this is actually the form of the second line, with a being Function[r, r[p]] and b being q. So then we’d expect the reduction to be:

two[Function[r, r[p]]][q] //. {two[x_][y_] → x[x[y]]}
&#10005

two[Function[r, r[p]]][q] //.
					 {two[x_][y_] -> x[x[y]]}

Somehow, though, the innermost a[b] is being written as x (probably different from the x earlier on the page), making the final result instead:

Function[r, r[p]][x]
&#10005

Function[r, r[p]][x]

OK, so we can decode quite a bit of what’s happening on the page. But at least one mystery that remains is what Y is supposed to be.

There’s actually a standard “Y combinator” in combinatory logic: the so-called fixed-point combinator. Formally, this is defined by saying that Y[f] must be equal to f[Y[f]], or, in other words, that Y[f] doesn’t change when f is applied, so that it’s a fixed point of f. (The Y combinator is related to #0 in the Wolfram Language.)

In modern times, the Y combinator has been made famous by the Y Combinator startup accelerator, named that way by Paul Graham (who had been a longtime enthusiast of functional programming and the LISP programming language—and had written an early web store using it) because (as he once told me) “nobody understands the Y combinator”. (Needless to say, Y Combinator is all about avoiding having companies go to fixed points…)

The Y combinator (in the sense of fixed-point combinator) was invented several times. Turing actually came up a version of it in 1937, that he called Θ. But is the “Y” on our page the famous fixed-point combinator? Probably not. So what is our “Y”? We see this reduction:

Excerpt 5

But that’s not enough information to uniquely determine what Y is. It’s clear Y isn’t operating just on a single argument; it seems to be dealing with at least two arguments. But it’s not clear (at least to me) how many arguments it’s taking, and what it’s doing.

OK, so even though we can interpret many parts of the page, we have to say that globally it’s not clear what’s been done. But even though it’s needed a lot of explanation here, what’s on the page is actually fairly elementary in the world of lambda calculus and combinators. Presumably it’s an attempt to construct a simple “program”—using lambda calculus and combinators—to do something. But as is typical in reverse engineering, it’s hard for us to tell what the “something”— the overall “explainable” goal—is supposed to be.

There’s one more feature of the page that’s worth commenting on, and that’s its use of brackets. In traditional mathematics one basically (if confusingly) uses parentheses for everything—both function application (as in f(x)) and grouping of terms (as in (1+x)(1-x), or, more ambiguously, a(1-x)). (In Wolfram Language, we separate different uses, with square brackets for function application—as in f[x]—and parentheses only for grouping.)

And in the early days of lambda calculus, there were lots of issues about brackets. Later, Alan Turing would write a whole (unpublished) paper entitled “The Reform of Mathematical Notation and Phraseology”, but already in 1937 he felt he needed to describe the (rather hacky) current conventions for lambda calculus (which were due to Church, by the way).

He said that f applied to g should be written {f}(g), unless f is just a single symbol, in which case it can be f(g). Then he said that a lambda (as in Function[a, b]) should be written λ a[b], or alternatively λ a . b. By perhaps 1940, however, the whole idea of using { … } and [ ... ] to mean different things had been dropped, basically in favor of standard-mathematical-style parentheses.

Look at what’s near the top of the page:

Excerpt 6

As written, this is a bit hard to understand. In Church’s convention, the square brackets would be for grouping, with the opening bracket replacing the dot. And with this convention, it’s clear that the Q (finally labeled D) enclosed in parentheses at the end is what the whole initial lambda is applied to. But actually, the square bracket doesn’t delimit the body of the lambda; instead, it’s actually representing another function application, and there’s no explicit specification of where the body of the lambda ends. At the very end, one can see that the writer changed a closing square bracket to a parenthesis, thereby effectively enforcing Church’s convention—and making the expression evaluate as the page shows.

So what does this little notational tangle imply? I think it strongly suggests that the page was written in the 1930s, or not too long thereafter—before conventions for brackets became clearer.

Whose Handwriting Is It?

OK, so we’ve talked about what’s on the page. But what about who wrote it?

The most obvious candidate would be Alan Turing, since, after all, the page was inside a book he owned. And in terms of content there doesn’t seem to be anything inconsistent with Alan Turing having written it—perhaps even when he was first understanding lambda calculus after getting Church’s paper in early 1936.

But what about the handwriting? Is that consistent with Alan Turing’s? Here are a few surviving samples that we know were written by Alan Turing:

Samples of Alan Turing's handwriting Samples of Alan Turing's handwriting Samples of Alan Turing's handwriting Image Map

The running text definitely looks quite different. But what about the notation? At least to my eye, it didn’t look so obviously different—and one might think that any difference could just be a reflection of the fact that the extant samples are pieces of exposition, while our page shows “thinking in action”.

Conveniently, the Turing Archive contains a page where Turing wrote out a table of symbols to use for notation. And comparing this, the letter forms did look to me fairly similar (this was from Turing’s time of studying plant growth, hence the “leaf area” annotation):

Table of Symbols

But I wanted to check further. So I sent the samples to Sheila Lowe, a professional handwriting examiner (and handwriting-based mystery writer) I happen to know—just presenting our page as “sample A” and known Turing handwriting as “sample B”. Her response was definitive, and negative: “The writing style is entirely different. Personality-wise, the writer of sample B has a quicker, more intuitive thinking style than the one of sample A.” I wasn’t yet completely convinced, but decided it was time to start looking at other alternatives.

So if Turing didn’t write this, who did? Norman Routledge said he got the book from Robin Gandy, who was Turing’s executor. So I sent along a “Sample C”, from Gandy:

Sample C

But Sheila’s initial conclusion was that the three samples were likely written by three different people, noting again that sample B came from “the quickest thinker and the one that is likely most willing to seek unusual solutions to problems”. (I find it a little charming that a modern handwriting expert would give this assessment of Turing’s handwriting, given how vociferously Turing’s school reports from the 1920s complained about his handwriting.)

Well, at this point it seemed as if both Turing and Gandy had been eliminated as writers of the page. So who might have written it? I started thinking about people Turing might have lent the book to. Of course, they’d have to be capable of doing calculations in lambda calculus.

I assumed that the person would have to be in Cambridge, or at least in England, given the watermark on the paper. And I took as a working hypothesis that 1936 or thereabouts was the relevant time. So who did Turing know then? We got a list of all math students and faculty at King’s College at the time. (There were 13 known students who started in 1930 through 1936.)

And from these, the most promising candidate seemed to be David Champernowne. He was the same age as Turing, a longtime friend, and also interested in the foundations of mathematics—in 1933 already publishing a paper on what’s now called Champernowne’s constant: 0.12345678910111213… (obtained by concatenating the digits of 1, 2, 3, 4, …, 8, 9, 10, 11, 12, …, and one of the very few numbers known to be “normal” in the sense that every possible block of digits occurs with equal frequency). In 1937, he even used Dirac gamma matrices, as mentioned in Dirac’s book, to solve a recreational math problem. (As it happens, years later, I became quite an aficionado of gamma matrix computations.)

After starting in mathematics, though, Champernowne came under the influence of John Maynard Keynes (also at King’s), and eventually became a distinguished economist, notably doing extensive work on income inequality. (Still, in 1948 he also worked with Turing to design Turbochamp: a chess-playing program that almost became the first ever to be implemented on a computer.)

But where could I find a sample of Champernowne’s handwriting? Soon I’d located his son Arthur Champernowne on LinkedIn, who, curiously, had a degree in mathematical logic, and had been working for Microsoft. He said his father had talked to him quite a lot about Turing’s work, though hadn’t mentioned combinators. He sent me a sample of his father’s handwriting (a piece about algorithmic music composition):

Champernowne's handwriting

One could immediately tell it wasn’t a match (Champernowne’s f’s have loops, etc.)

So who else might it be? I wondered about Max Newman, in many ways Alan Turing’s mentor. Newman had first got Turing interested in “mechanizing mathematics”, was a longtime friend, and years later would be his boss at Manchester in the computer project there. (Despite his interest in computation, Newman always seems to have seen himself first and foremost as a topologist, though his cause wasn’t helped by a flawed proof he produced of the Poincaré conjecture.)

It wasn’t difficult to find a sample of Newman’s handwriting. And no, definitely not a match.

Tracing the Book

OK, so handwriting identification hadn’t worked. And I decided the next thing to do was to try to trace in a bit more detail what had actually happened to the book I had in my hands.

So, first, what was the more detailed story with Norman Routledge? He had gone to King’s College, Cambridge as an undergraduate in 1946, and had gotten to know Turing then (yes, they were both gay). He graduated in 1949, then started doing a PhD with Turing as his advisor. He got his PhD in 1954, working on mathematical logic and recursion theory. He got a fellowship at King’s College, and by 1957 was Director of Studies in Mathematics there. He could have stayed doing this his whole life, but he had broad interests (music, art, architecture, recreational math, genealogy, etc.) and in 1960 changed course, and became a teacher at Eton—where he entertained (and educated) many generations of students (including me) with his eclectic and sometimes outlandish knowledge.

Could Norman Routledge have written the mysterious page? He knew lambda calculus (though, coincidentally, he mentioned at our tea in 2005 that he always found it “confusing”). But his distinctive handwriting style immediately excludes him as a possible writer.

Could the page be somehow associated with a student of Norman’s, perhaps from when he was still in Cambridge? I don’t think so. Because I don’t think Norman ever taught about lambda calculus or anything like it. In writing this piece, I found that Norman wrote a paper in 1955 about doing logic on “electronic computers” (and creating conjunctive normal forms, as BooleanMinimize now does). And when I knew Norman he was quite keen on writing utilities for actual computers (his initials were “NAR”, and he named his programs “NAR…”, with, for example, “NARLAB” being a program for creating textual labels using hole patterns punched in paper tape). But he never talked about theoretical models of computation.

OK, but let’s read Norman’s note inside the book a bit more carefully. The first thing we notice is that he talks about being “offered books from a dead man’s library”. And from the wording, it sounds as if this happened quite quickly after a person died, suggesting that Norman got the book soon after Turing’s death in 1954, and that Gandy didn’t have it for very long. Norman goes on to say that actually he got four books in total, two on pure math, and two on theoretical physics.

Then he says that he gave “the other [physics] one (by Herman Weyl, I think)” to “Sebag Montefiore, a pleasant, clever boy whom you [George Rutter] may remember”. OK, so who is that? I searched for my rarely used Old Etonian Association List of Members. (I have to report that on opening it, I could not help but notice its rules from 1902, the first under “Rights of Members” charmingly being “To wear the Colours of the Association”. I should add that I would probably never have joined this association or got this book but for the insistence of a friend of mine at Eton named Nicholas Kermack, who from the age of 12 planned how he would one day become Prime Minister, but sadly died at the age of 21.)

But in any case, there were five Sebag-Montefiores listed, with quite a distribution of dates. It wasn’t hard to figure out that the appropriate one was probably Hugh Sebag-Montefiore. Small world that it is, it turned out that his family had owned Bletchley Park before selling it to the British Government in 1938. And in 2000, Sebag-Montefiore had written a book about the breaking of Enigma—which is presumably why in 2002 Norman thought to give him a book that had been owned by Turing.

OK, so what about the other books Norman got from Turing? Not having any other way to work out what happened to them, I ordered a copy of Norman’s will. The last clause in the will was classic Norman:

Excerpt from Norman's will

But what the will ultimately said was that Norman’s books should be left to King’s College. And although the complete collection of his books doesn’t seem to be anywhere to be found, the two Turing-owned pure math books that he mentioned in his note are now duly in the King’s College archive collection.

But, OK, so the next question is: what happened to Turing’s other books? I looked up Turing’s will, which seemed to leave them all to Robin Gandy.

Gandy was a math undergraduate at King’s College, Cambridge, who in his last year of college—in 1940—had become friends with Alan Turing. In the early part of the war, Gandy worked on radio and radar, but in 1944 he was assigned to the same unit as Turing, working on speech encipherment. And after the war, Gandy went back to Cambridge, soon starting a PhD, with Turing as his advisor.

Gandy’s war work apparently got him interested in physics, and his thesis, completed in 1952, was entitled “On Axiomatic Systems in Mathematics and Theories in Physics”. What Gandy seems to have been trying to do is to characterize what physical theories are in mathematical logic terms. He talks about type theory and rules of inference, but never about Turing machines. And from what we know now, I think he rather missed the point. And indeed my own work from the early 1980s argued that physical processes should be thought of as computations—like Turing machines or cellular automata—not as things like theorems to be deduced. (Gandy has a rather charming discussion of the order of types involved in physical theories, saying for example that “I reckon that the order of any computable binary decimal is less than eight”. He says that “one of the reasons why modern quantum field theory is so difficult is that it deals with objects of rather high type—functionals of functions…”, eventually suggesting that “we might well take the greatest type in common use as an index of mathematical progress”.)

Gandy mentions Turing a few times in the thesis, noting in the introduction that he owes a debt to A. M. Turing, who “first called my somewhat unwilling attention to the system of Church” (i.e. lambda calculus)—though in fact the thesis has very few lambdas in evidence.

After his thesis, Gandy turned to purer mathematical logic, and for more than three decades wrote papers at the rate of about one per year, and traveled the international mathematical logic circuit. In 1969 he moved to Oxford, and I have to believe that I must have met him in my youth, though I don’t have any recollection of it.

Gandy apparently quite idolized Turing, and in later years would often talk about him. But then there was the matter of the Turing collected works. Shortly after Turing died, Sara Turing and Max Newman had asked Gandy—as Turing’s executor—to organize the publication of Turing’s unpublished papers. Years went by. Letters in the archives record Sara Turing’s frustration. But somehow Gandy never seemed to get the papers together.

Gandy died in 1995, still without the collected works complete. Nick Furbank—a literary critic and biographer of E. M. Forster who Turing had gotten to know at King’s College—was Turing’s literary executor, and finally he swung into action on the collected works. The most contentious volume seemed to be the one on mathematical logic, and for this he enlisted Robin Gandy’s first serious PhD student, a certain Mike Yates—who found letters to Gandy about the collected works that had been unopened for 24 years. (The collected works finally appeared in 2001—45 years after they were started.)

But what about the books Turing owned? In continuing to try to track them down, my next stop was the Turing family, and specifically Turing’s brother’s youngest child, Dermot Turing (who is actually Sir Dermot Turing, as a result of a baronetcy which passed down the non-Alan branch of the Turing family). Dermot Turing (who recently wrote a biography of Alan Turing) told me about “granny Turing” (aka Sara Turing), whose house apparently shared a garden gate with his family’s, and many other things about Alan Turing. But he said the family never had any of Alan Turing’s books.

So I went back to reading wills, and found out that Gandy’s executor was his student Mike Yates. We found out that Mike Yates had retired from being a professor 30 years ago, but was now living in North Wales. He said that in the decades he was working in mathematical logic and theory of computation, he’d never really touched a computer—but finally did when he retired (and, as it happens, discovered Mathematica soon thereafter). He said how remarkable it was that Turing had become so famous—and that when he’d arrived at Manchester just three years after Turing died, nobody talked about Turing, not even Max Newman when he gave a course about logic. Though later on, Gandy would talk about how swamped he was in dealing with Turing’s collected works—eventually leaving the task to Mike.

What did Mike know about Turing’s books? Well, he’d found one handwritten notebook of Turing’s, that Gandy had not given to King’s College, because (bizarrely) Gandy had used it as camouflage for notes he kept about his dreams. (Turing kept dream notebooks too, that were destroyed when he died.) Mike said that notebook had recently been sold at auction for about $1M. And that otherwise he didn’t think there was any Turing material among Gandy’s things.

It seemed like all our leads had dried up. But Mike asked to see the mysterious piece of paper. And immediately he said, “That’s Robin Gandy’s handwriting!” He said he’d seen so much of it over the years. And he was sure. He said he didn’t know much about lambda calculus, and couldn’t really read the page. But he was sure it had been written by Robin Gandy.

We went back to our handwriting examiner with more samples, and she agreed that, yes, what was there was consistent with Gandy’s writing. So finally we had it: Robin Gandy had written our mysterious piece of paper. It wasn’t written by Alan Turing; it was written by his student Robin Gandy.

Of course, some mysteries remain. Presumably Turing lent Gandy the book. But when? The lambda calculus notation seems like it’s from the 1930s. But based on comments in Gandy’s thesis, Gandy probably wouldn’t have been doing anything with lambda calculus until the late 1940s. Then there’s the question of why Gandy wrote it. It doesn’t seem directly related to his thesis, so maybe it was when he was first trying to understand lambda calculus.

I doubt we’ll ever know. But it’s certainly been interesting trying to track it down. And I have to say that the whole process has done much to heighten my awareness of just how complex the stories may be of all those books from past centuries that I own. And it makes me think I’d better make sure I’ve gone through all their pages, just to find out what curious things might be in there…


Thanks for additional help to Jonathan Gorard (local research in Cambridge), Dana Scott (mathematical logic) and Matthew Szudzik (mathematical logic).

8 comments

  1.  

    Thank you for writing this article, to this librophile and science geek it was the most thrilling who-dunnit I’ve ever read. All this richness is, unfortunately, disappearing in our ever digital world.

  2.  

    What a fun read for summer’s afternoon.

    Herbert Sauro
  3.  

    “My own guess is that it was not suicide, but that’s a different story.” ???!

    Stephen J. Carnam
  4.  

    Thanks for sharing this story, what an amazingly interesting read!

    Mikko Sorsa
  5.  

    Although it’s widely believed that Turing died by suicide, there’s strong evidence that it was an accident (as Stephen suspects). I read the story in a biography of Turing (possibly the one by Andrew Hodges, but I don’t really remember). The author did his own quite extensive research, since he found the police report’s suicide verdict to be hasty and unconvincing. It turns out that Turing maintained an amateur’s laboratory in a small room next to his bedroom. At the time of his death, he was experimenting with gold-plating some teaspoons, using cyanide as the electrolyte. When the police were called to investigate the death, they found the electroplating experiment still running – Turing had forgotten to shut it off when he went to sleep the previous evening!
    Confusing the situation was Turing’s habit of eating some apple just before bedtime, and a partially eaten apple was found on his bedside table. But the neglected electroplating not only generated fatal fumes but also contaminated the apple, such that the police assumed that he had deliberately poisoned the apple before eating it!
    Very sad that such a major intellectual figure has for so long been mistakenly labeled a suicide.

    Richard Werthamer
  6.  

    Is it possible that the note by Gandy was given to Turing, who “filed” it in the Dirac book, which was never seen by Gandy?

    Charles Blair
    •  

      Thank you for the comment, Charles! Stephen says that’s an interesting possibility, that hadn’t occurred to him…

      —The Office of Stephen Wolfram

      Administrator