# Happy Birthday, Alan Turing

Today (June 23, 2010) would have been Alan Turing‘s 98^{th} birthday—if he had not died in 1954, at the age of 41.

I never met Alan Turing; he died five years before I was born. But somehow I feel I know him well—not least because many of my own intellectual interests have had an almost eerie parallel with his.

And by a strange coincidence, *Mathematica*‘s “birthday” (June 23, 1988) is aligned with Turing’s—so that today is also the celebration of *Mathematica*‘s 22^{nd} birthday.

I think I first heard about Alan Turing when I was about eleven years old, right around the time I saw my first computer. Through a friend of my parents, I had gotten to know a rather eccentric old classics professor, who, knowing my interest in science, mentioned to me this “bright young chap named Turing” whom he had known during the Second World War.

One of the classics professor’s eccentricities was that whenever the word “ultra” came up in a Latin text, he would repeat it over and over again, and make comments about remembering it. At the time, I didn’t think much of it—though I did remember it. Only years later did I realize that “Ultra” was the codename for the British cryptanalysis effort at Bletchley Park during the war. In a very British way, the classics professor wanted to tell me something about it, without breaking any secrets. And presumably it was at Bletchley Park that he had met Alan Turing.

A few years later, I heard scattered mentions of Alan Turing in various British academic circles. I heard that he had done mysterious but important work in breaking German codes during the war. And I heard it claimed that after the war, he had been killed by British Intelligence. At the time, at least some of the British wartime cryptography effort was still secret, including Turing’s role in it. I wondered why. So I asked around, and started hearing that perhaps Turing had invented codes that were still being used.

I’m not sure where I next encountered Alan Turing. Probably it was when I decided to learn all I could about computer science—and saw all sorts of mentions of “Turing machines”. But I have a distinct memory from around 1979 of going to the library, and finding a little book about Alan Turing written by his mother, Sara Turing.

And gradually I built up quite a picture of Alan Turing and his work. And over the 30 years that have followed, I have kept on running into Alan Turing, often in unexpected places.

In the early 1980s, for example, I had become very interested in theories of biological growth—only to find (from Sara Turing’s book) that Alan Turing had done all sorts of largely unpublished work on that.

And for example in 1989, when we were promoting an early version of *Mathematica*, I decided to make a poster of the Riemann zeta function—only to discover that Alan Turing had at one time held the record for computing zeros of the zeta function. (Earlier he had also designed a gear-based machine for doing this.)

Recently I even found out that Turing had written about the “reform of mathematical notation and phraseology”—a topic of great interest to me in connection with both *Mathematica* and Wolfram|Alpha.

And at some point I learned that a high school math teacher of mine (Norman Routledge) had been a friend of Turing’s late in his life. But even though my teacher knew my interest in computers, he never mentioned Turing or his work to me. And indeed, 35 years ago, Alan Turing and his work were little known, and it is only fairly recently that Turing has become as famous as he is today.

Turing’s greatest achievement was undoubtedly his construction in 1936 of a universal Turing machine—a theoretical device intended to represent the mechanization of mathematical processes. And in some sense, *Mathematica* is precisely a concrete embodiment of the kind of mechanization that Turing was trying to represent.

In 1936, however, Turing’s immediate purpose was purely theoretical. And indeed it was to show not what could be mechanized in mathematics, but what could not. In 1931, Gödel’s theorem had shown that there were limits to what could be proved in mathematics, and Turing wanted to understand the boundaries of what could ever be done by any systematic procedure in mathematics.

Turing was a young mathematician in Cambridge, England, and his work was couched in terms of mathematical problems of his time. But one of his steps was the theoretical construction of a universal Turing machine capable of being “programmed” to emulate any other Turing machine. In effect, Turing had invented the idea of universal computation—which was later to become the foundation on which all of modern computer technology is built.

At the time, though, Turing’s work did not make much of a splash, probably largely because the emphasis of Cambridge mathematics was elsewhere. Just before Turing published his paper, he learned about a similar result by Alonzo Church from Princeton, formulated not in terms of theoretical machines, but in terms of the mathematics-like lambda calculus. And as a result Turing went to Princeton for a year to study with Church—and while he was there, wrote the most abstruse paper of his life.

The next few years for Turing were dominated by his wartime cryptanalysis work. I learned a few years ago that during the war Turing visited Claude Shannon at Bell Labs in connection with speech encipherment. Turing had been working on a kind of statistical approach to cryptanalysis—and I am extremely curious to know whether Turing told Shannon about this, and potentially launched the idea of information theory, which itself was first formulated for secret cryptanalysis purposes.

After the war, Turing got involved with the construction of the first actual computers in England. To a large extent, these computers had emerged from engineering, not from a fundamental understanding of Turing’s work on universal computation.

There was, however, a definite, if circuitous, connection. In 1943 Warren McCulloch and Walter Pitts in Chicago wrote a theoretical paper about neural networks that used the idea of universal Turing machines to discuss general computation in the brain. John von Neumann read this paper, and used it in his recommendations about how practical computers should be built and programmed. (John von Neumann had known about Turing’s paper in 1936, but at the time did not recognize its significance, instead describing Turing in a recommendation letter as having done interesting work on the Central Limit Theorem.)

It is remarkable that in just over a decade Alan Turing was transported from writing theoretically about universal computation, to being able to write programs for an actual computer. I have to say, though, that from today’s vantage point, his programs look incredibly “hacky”—with lots of special features packed in, and encoded as strange strings of letters. But perhaps to reach the edge of a new technology it’s inevitable that there has to be hackiness.

And perhaps too it required a certain hackiness to construct the very first universal Turing machine. The concept was correct, but Turing quickly published an erratum to fix some bugs, and in later years, it’s become clear that there were more bugs. But at the time Turing had no intuition about how easily bugs can occur.

Turing also did not know just how general or not his results about universal computation might be. Perhaps the Turing machine was just one model of a computational process, and other models—or brains—might have quite different capabilities. But gradually over the course of several decades, it became clear that a wide range of possible models were actually exactly equivalent to the machines Turing had invented.

It’s strange to realize that Alan Turing never appears to have actually simulated a Turing machine on a computer. He viewed Turing machines as theoretical devices relevant for proving general principles. But he does not appear to have thought about them as concrete objects to be explicitly studied.

And indeed, when Turing came to make models of biological growth processes, he immediately started using differential equations—and appears never to have considered the possibility that something like a Turing machine might be relevant to natural processes.

When I became interested in simple computational processes around 1980, I also didn’t consider Turing machines—and instead started off studying what I later learned were called cellular automata. And what I discovered was that even cellular automata with incredibly simple rules could produce incredibly complex behavior—which I soon realized could be considered as corresponding to a complex computation.

I probably simulated my first explicit Turing machine only in 1991. To me, Turing machines were built a little bit too much like engineering systems—and not like something that would likely correspond to a system in nature. But I soon found that even simple Turing machines, just like simple cellular automata, could produce immensely complex behavior.

In a sense, Alan Turing could easily have discovered this. But his intuition—like my original intuition—would have told him that no such phenomenon was possible. So it would likely only have been luck—and access to easy computation—that would have led him to find the phenomenon.

Had he done so, I am quite sure he would have become curious about just what the threshold for his concept of universality would be, and just how simple a Turing machine would suffice. In the mid-1990s, I searched the space of simple Turing machines, and found the smallest possible candidate. And after I put up a $25,000 prize, in 2007 Alex Smith showed that indeed this Turing machine is universal.

No doubt Alan Turing would quite quickly have grasped the significance of such results for thinking about both natural processes and mathematics. But without the empirical discoveries, his thinking did not progress in this direction.

Instead, he began to consider from a more engineering point of view to what extent computers should be able to emulate brains, and he invented ideas like the Turing Test. Reading through his writings today, it is remarkable how many of his conceptual arguments about artificial intelligence still need to be made—though some, like his discussion of extrasensory perception, have become quaintly dated.

And looking at his famous 1950 article on “Computing Machinery and Intelligence” one sees a discussion of programming into a machine the contents of *Encyclopaedia Britannica*—which he estimates should take 60 workers 50 years. I wonder what Alan Turing would think of Wolfram|Alpha, which, thanks to progress over the past 60 years, and perhaps some cleverness, has so far taken at least slightly less human effort.

In addition to his intellectual work, Turing has in recent times become something of a folk hero, most notably through the story of his death. Almost certainly it will never be known for sure whether his death was in fact intentional. But from what I know and have heard I must say that I rather doubt that it was.

When one first hears that Alan Turing died by eating an apple impregnated with cyanide one assumes it must have been intentional suicide. But when one later discovers that he was quite a tinkerer, had recently made cyanide for the purpose of electroplating spoons, kept chemicals alongside his food, and was rather a messy individual, the picture becomes a lot less clear.

I often wonder what Alan Turing would have been like to meet. I do not know of any recording of his voice (though he did once do a BBC radio broadcast). But I gather that even near the end of his life he giggled a lot, and talked with a kind of stutter that seemed to come from thinking faster than he was talking. He seemed to have found it easiest to talk to mathematicians. He thought a little about physics, though doesn’t seem to have ever gotten deeply into it. And he seemed to have maintained a child-like enthusiasm and wonder for many intellectual questions throughout his life.

He was something of a loner, working successively on his own on his various projects. He was gay, and lived alone. He was no organizational politician, and towards the end of his life seems to have found himself largely ignored both by people working on computers and by people working on his new interest of biological growth and morphogenesis.

He was in some respects a quintessential British amateur, dipping his intellect into different areas. He achieved a high level of competence in pure mathematics, and used that as his professional base. His contributions in traditional mathematics were certainly perfectly respectable, though not spectacular. But in every area he touched, there was a certain crispness to the ideas he developed—even if their technical implementation was sometimes shrouded in arcane notation and masses of detail.

In some ways he was fortunate to live when he did. For he was at the right time to be able take the formalism of mathematics as it had been developed, and to combine it with the emerging engineering of his day, to see for the first time the general concept of computation.

It is perhaps a shame that he died 25 years before computer experiments became widely feasible. I certainly wonder what he would have discovered tinkering with *Mathematica*. I don’t doubt that he would have pushed it to its limits, writing code that would horrify me. But I fully expect that long before I did, he would have discovered the main elements of NKS, and begun to understand their significance.

He would probably be disappointed that 60 years after he invented the Turing test, there is still no full human-like artificial intelligence. And perhaps long ago he would have begun to campaign for the creation of something like Wolfram|Alpha, to turn human knowledge into something computers can handle.

If he had lived a few decades longer, he would no doubt have applied himself to a half dozen more areas. But there is still much to be grateful for in what Alan Turing did achieve in his 41 years, and his modern reputation as the founding father of the concept of computation—and the conceptual basis for much of what I, for example, have done—is well deserved.

Happy posthumous birthday, Alan Turing. Get ready for your 100^{th}.

Turing machine history in *A New Kind of Science* »

`TuringMachine` function in *Mathematica* »

Turing machines in the Wolfram Demonstrations Project »

Turing machines in Wolfram|Alpha »

I think the most crucial turning Turing missed in his lifetime was the one that would immediately have led him to showing that the first-order Peano Arithmetic has a sound, algorithmic, interpretation over the structure of the natural numbers.

Note that if [A(x1, x2, ..., xn)] is an atomic formula of PA then, for any given sequence of numerals [b1, b2, ..., bn], the PA formula [A(b1, b2, ..., bn)] is an atomic formula of the form [c=d], where [c] and [d] are atomic PA formulas that denote PA numerals. Since [c] and [d] are recursively defined formulas in the language of PA, it follows from a standard result that, if PA is consistent, then [c=d] is algorithmically computable as either true or false in N.

In other words, if PA is consistent, then [A(x1, x2, ..., xn)] is algorithmically decidable over N in the sense that there is a Turing machine TM_A that, for any given sequence of numerals [b1, b2, ..., bn], will accept the natural number m if, and only if, m is the Goedel number of the PA formula [A(b1, b2, ..., bn)], and halt with output 0 if [A(b1, b2, ..., bn)] interprets as true in N; and halt with output 1 if [A(b1, b2, ..., bn)] interprets as false in N.

Moreover, since Tarski has shown that the satisfaction and truth of the compound formulas of PA (i.e., the formulas involving the logical connectives and the quantifiers) under an interpretation of PA is definable inductively in terms of only the satisfaction (non-satisfaction) of the atomic formulas of PA, it follows that the satisfaction and/or truth of the formulas of PA under the usual interpretation of the PA symbols is algorithmically decidable.

This is the finitary interpretation of PA sought by Hilbert, which follows immediately from Turing’s 1936 paper on computable numbers.

Perhaps Turing was unduly influenced by Goedel’s powerful presentation—and Goedel’s persuasive, admittedly Platonic, interpretation of his own formal reasoning—in Goedel’s seminal 1931 paper on formally undecidable arithmetical propositions.

Be that as it may, in his 1939 paper on ordinal-based logics, Turing applied his computational method—which he had developed in his 1936 paper—in seeking a categorical interpretation of Cantor’s ordinal arithmetic (as defined in a set theory such as ZF), rather than in seeking a categorical interpretation of PA. Turing apparently viewed his 1936 paper as complementing and extending Goedel’s and Cantor’s reasoning.

Turing thus missed the fact that his 1936 paper actually conflicts with Goedel’s and Cantor’s interpretations of their own, formal, reasoning.

Goedel’s and Cantor’s reasoning implicitly presumes that Aristotle’s particularisation holds over the natural numbers (hence PA and ZF may safely be assumed to be omega-consistent), and so the satisfaction and truth of compound PA formulas under the standard interpretation of PA can only be defined in terms of subjective, self-evident, truth.

However, as Brouwer had noted in a seminal 10908 paper, the presumption that Aristotle’s particularisation holds over infinite domains such as that of the natural numbers does not lie (as self-evident) within a common human intuition; and such a presumption has no logical basis in the objective decidability and computability of number-theoretic relations and functions over the domain of the natural numbers.

The validity of Brouwer’s objection is seen in the following investigation, where the satisfaction and truth of compound PA formulas is inductively defined under an algorithmic interpretation of PA solely in terms of objective Turing-computability, with significant consequences.

Turing plays a significant role in a great book by Neal Stephenson, Cryptonomicon, published in 1999.

I came across this blog only today via a philosophers’ e-list, Philos-L, so don’t know whether the following has been mentioned to date. There is a beautiful, elegant paper by Joshua Gold and Mike Shadlen ‘Banburismus and the Brain: Decoding the Relationship between Sensory Simuli, Decisions and Reward’, *Neuron* 36 (2002): 299-308, which shows that the function of a particular neural mechanism central to subconscious decision-making is isomorphic to the Banburismus function devised by Alan Turing at Bletchley Park for a preliminary sifting of the promising from the unpromising coding hypotheses.

Speaking of anniversaries and the manipulation of symbols contained on a strip of tape, on this day in 1868 patent number 79,265 was granted for the first typewriter to be commercially successful, see http://en.wikipedia.org/wiki/Sholes_and_Glidden_typewriter

Dear Mr. Wolfram,

I enjoyed your post on Turing and am glad to learn of your website. I look forward to integrating your monograph when possible for students here.

It is thoroughly considerate and not self-aggrandizing, on my view, when people bother to reflect and popularise and share with a general public. That’s a very different impression of your post: it’s public service. people jealous of your success must be borne with, like mosquitoes.

I always think of your mom who was very very dear to me. We met in 1987 about two years before she died; I still miss her. I was visiting Oxford as a recognised student and was interesting to her because i was headed for a job in Ghana, where I have remained since then. We still use her Intro to Philosophical Logic, which was published just before or after you did Mathematica.

She was very very proud of you, and even much more fond.

Helen Lauer

assoc. prof.

Head of Dept.

Philosophy and Classics

University of Ghana, Legon

How does donating money to a foster house help them?

Sent from my iPad 4G

Science is bottom-up, while engineering is top-down.

Thus social science has different connotations from social engineering,

the former being more individually driven while the latter state-directed.

The rise of Turing has something to do with such sutleties, ie,

there is a kind of euphoria about computer being able to solve everything

and the state is getting on the bandwagon. It’s like when the steam engine

was invented and everyone was onto it. Especially with the Internet which

connects computers world-wide, the railroad is firmly laid. The most

difficult question is, what do you do with it. I do the blogging. What about

you guys? Surely Turing didn’t even imagine that that was what people

would do with his invensions :-)

Honour, loyalty, dignity and integrity are a few of human traits that cannot be computed, at least not in today’s measure. At a time when Alan Turing could have been easily excused from unjust accusations by the society, simply by disclosing his contribution to turning the tides of Second World War in Europe, he chose to remain in silence, to honour the oath of secrecy he took, to leave his dignity in question in the face of the world. At some point in his life, he must had faced with the computation between honour and dignity, between loyalty and integrity. To me, that would have been like the ultimate Turing Test, difficult enough not just for testing of artificial intelligence, but even way more than genuine human intelligence can handle. To me, being tested is one thing, being a brave soul to be responsible for the outcomes and consequences of the test, will mark if the tested subject is a true human.