Abstract

In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will. I focus relatively narrowly on a notion that I call ‘Knightian freedom’: a certain kind of in-principle physical unpredictability that goes beyond probabilistic unpredictability. Other, more metaphysical, aspects of free will I regard as possibly outside the scope of science.

I examine a viewpoint, suggested independently by Carl Hoefer, Cristi Stoica, and even Turing himself, that tries to find scope for ‘freedom’ in the universe's boundary conditions rather than in the dynamical laws. Taking this viewpoint seriously leads to many interesting conceptual problems. I investigate how far one can go toward solving those problems and, along the way, I encounter (among other things) the no-cloning theorem, the measurement problem, decoherence, chaos, the arrow of time, the holographic principle, Newcomb's paradox, Boltzmann brains, algorithmic information theory, and the common prior assumption. I also compare the viewpoint explored here with the more radical speculations of Roger Penrose.

The result of all this is an unusual perspective on time, quantum mechanics, and causation, of which I myself remain skeptical but which has several appealing features. Among other things, it suggests interesting empirical questions in neuro-science, physics, and cosmology; and it takes a millennia-old philosophical debate into some underexplored territory.

When I was a teenager, Alan Turing was at the top of my pantheon of scientific heroes, above even Darwin, Ramanujan, Einstein, and Feynman. Some of the reasons were obvious: the founding of computer science, the proof of the unsolvability of the Entscheidungsproblem, the breaking of the Nazi Enigma code, the unapologetic nerdiness and the near-martyrdom for human rights. But beyond the facts of his biography, I idolized Turing as an ‘ über-reductionist’: the scientist who had gone further than anyone before him to reveal the mechanistic nature of reality. Through his discovery of computational universality, as well as the Turing Test criterion for intelligence, Turing finally unmasked the pretensions of anyone who claimed there was anything more to mind, brain, or the physical world than the unfolding of an immense computation.

The beginning

Turing's seminal 1936 paper ‘On computable numbers, with an application to the Entscheidungsproblem’ is remarkable in several ways: firstly he had set out to solve Hilbert's decision problem of the title, with the definitive discussion of what a ‘human computer’ could do, and what would constitute an ‘effective process’, but secondly because it, well one cannot say ‘almost in passing’ because Turing was keen to put his observations on mechanical processes to work, but it was a second product of the paper that it lay also the foundations for the not yet even nascent theory of ‘computer science’. The main point as Turing saw, was the ‘universality’ of his machine: there is a universal program or machine that can simulate any other. The story of the development of that science from Turing's work is retold elsewhere, and is not the aim or direction of this article. Nor are we going to trace the remarkable history of the theory of ‘recursive functions’ (now reclaimed as ‘computable functions’) thence until the present day. That story would involve not just the study of the Turing complexity of sets of numbers, and the computably enumerable sets, but later generalisations in ‘generalised recursion theory’ or ‘higher type computability theory’ where deep theoretical analyses of notions of induction and logical definability theory came into being in the late 1960s and 1970s. Such theories abstracted away from any machine model to notions of recursion or induction on abstract structures. These results are beautiful and very deep, and turn out to have intimate connections with mathematical logic and set theory.

Whilst this high road of increasing abstraction is very appealing intellectually, we have recently seen a flurry of research work drawing its inspiration from the original conception of Turing's machine model, and which tries to work with that, generalising what it could, in theory, compute when released from spatial and tem- poral boundaries. This article seeks to give some flavour of those ideas. Whilst it has to be said that a stretch of the imagination is required to send a computer off into a black hole, or to transcend ordinary time with its clock ticks of 0,1,2, … into some transfinite stage ‘ ω ’ or even further beyond, thus ‘ transcending ’ the finite, […]

Ever since we understood that living organisms are made of fundamentally the same stuff as the rest of the universe, we have been puzzling about what makes life different, and how that difference arose. Alan Turing made a major contribution in putting forth a model for morphogenesis that attempts to bridge the gap between the molecules we are made of and how we look. This is a huge gap to span in trying to solve the problem of how an embryo builds itself. People are about 1.5m = 1.5×109nm (nanometers) tall and the typical protein molecule is about 30 nm wide, a ratio of 50 000 000 = 5 × 107 to 1. That protein might contain 1000 amino acids and, if we take into account the relative volumes, not just length, say 70 liters for an adult human and 0.15nm3 for an amino acid (Sühnel and Hühne, 2005), this raises the ratio to 5×1026 to 1.

When we build a bridge, unless it's over a small ditch, we use many parts and assemble them in sections called spans (Figure 10.1). In biology this has come to be known as ‘modularity’, and the grand search has been on to discover just what the modules of life are (von Dassow and Munro, 1999; Gilbert and Bolker, 2001; Redies and Puelles, 2001; Newman and Bhat, 2009; Peter and Davidson, 2009; Christensen et al., 2010). At first it was thought that cells represented modules. The ‘cell theory’ was resisted by a minority of 19th century biologists, who thought that the basic module was the whole organism, not the cell. Certain observations support this ‘organismal’ theory. First, single cell organisms, such as Parameciumand diatoms (Figure 10.2), can have quite complex morphologies; see Gordon (2010); Tiffany et al. (2010); Gordon and Tiffany (2011). Second, some green algae have many nuclei that move in cytoplasmic streaming, unhindered by cell boundaries, yet “… exhibit morphological differentiation into structures that resemble the roots, stems, and leaves of land plants and even have similar functions” (Chisholm et al., 1996); see Cocquyt et al., 2010.

In 1950, as a small part of his seminal article “Computing Machinery and Intelligence”, the great British mathematician, logician, computer pioneer, artificial-intelligence founder, and philosopher Alan Mathison Turing wrote out two tiny but marvelously thought-provoking snippets of a hypothetical human-machine dialogue illustrating what he termed the “imitation game” (and which later became known as the Turing Test). Turing presumably believed that those snippets were sufficiently complex to suggest to an average reader all of the fantastic machinery that underlies our full human use of language. To me, Turing's snippets indeed had that effect, but the sad thing is that many people in the ensuing decades read those short imaginary teletype-mediated dialogues and mistakenly thought that very simplistic mechanisms could do all that was shown there, from which they drew the conclusion that even if some Alprogram passed the full Turing Test, it might still be nothing but a patchwork of simple-minded tricks, as lacking in understanding or semantics as is a cash register or an automobile transmission. It is amazing to me that anyone could draw such a preposterous conclusion, but the fact is, it is a very popular view.

Innumerable arcane philosophical debates have been inspired by Turing's proposed Test, and yet I have never seen anyone descend to the mundane, concrete level that Turing himself did, and really spell out an example of what genuine human-level machine intelligence might look like on the screen. I think concrete examples are always needed before arcane arguments are bandied about. And therefore, my attempted “favor” for Alan Mathison Turing consists in having worked out a much longer hypothetical dialogue between a human and a machine, a dialogue that I hope is quite in the spirit of Turing's two little snippets, but that is intended to make far more explicit than he did the degree of complexity and depth that must exist behind the linguistic façade.

As you read the dialogue that follows, it would be good to keep in mind the tacit implication by anti-AI philosopher John Searle in his writings featuring the so-called “Chinese Room” thought-experiment that computers that deal with language — even ones that might someday pass the Turing Test in its full glory, which of course the following hypothetical program certainly would seem to be able to do — necessarily stay stuck on its surface, solely playing syntactic games,[…]

This volume was the inspiration of the mathematical logician Barry Cooper. In 2007 he was already planning a conference to mark the centenary of Alan Turing's birth, but this was just the start of his huge and energetic dedication to a renaissance of Turing studies. In 2009, while taking on the project of a new critical edition of Turing's papers, he also raised with Cambridge University Press (and with me) an idea for a book about ‘Turing and the future of computing ’. After correspondence with David Tranah and Silvia Barbina of the Press, Barry and I conceived it as an opportunity for leading scientific thinkers to bring exciting and challenging aspects of Turing's legacy to a wider readership.

In 2010, we settled on the title of The Once and Future Turing, and extended invitations on this basis. Our enterprise rested on Barry Cooper's networking power, arising from his role as chair of Computability in Europe and countless conference committees. More profoundly, it was steeped in his intellectual quest to see logic interact with new advances in physical and human sciences. His very individual vision of ‘computing the world’ is prominent in the subtitle and introductions for the five Parts of the book, which were mainly his responsibility. My own contributions, including the overall introduction, revolved around the Turing Once. Barry wrote for the Turing Future.

Unfortunately, just as this book was in the last stages of preparation, he met a rather sudden death. It was a particular sadness for him that he was not able to see the publication of this book. He expressed heartfelt thanks to everyone involved at Cambridge University Press, a gratitude I keenly share, and, above all, to the generous work of the distinguished and ever-patient contributors. Their writing, in so many different ways, reflects the magic of time and human life and will speak to a future that neither Alan Turing nor Barry Cooper could live to see.

From the beginning of recorded history, people have worked with numbers using algorithms. Algorithms are processes that can be carried out by following a set of instructions in a completely mechanical manner without any need for creative thought. Until the 1930s no need was felt for a precise mathematical definition or characterization of what it means for something to be algorithmic. The need then did arise, in those years, in connection with attempts to prove that for some problems no algorithmic solution is possible. In 1935 Alan Turing considered this matter in isolation at Cambridge University. Meanwhile, in Princeton, the combined efforts of Kurt G ödel and Alonzo Church with his students Stephen Kleene and J. Barkley Rosser were brought to bear on the same topic. E.L. Post had also been thinking about these things, like Turing also in isolation, since the 1920s. Although the various formulations that were developed seemed superficially to be quite different from one another, they all turned out to be equivalent. This consensus about algorithmic processes has come to be called the Church–Turing Thesis.

Turing's conception differed from all the others in that it was formulated in terms of an abstract machine. What was striking about his characterization is his analysis that showed why even very limited fundamental operations would suffice for all algorithms if supplemented by unlimited data storage capability. Moreover, he demonstrated that a single such machine, Turing's so-called ‘Universal Machine’, could be made to carry out any algorithmic process whatever. These insights have played a key role in the development of modern all-purpose computers. But, as will become clear later, the notion of universality spills over into mathematical domains far removed from computation.

Turing began his investigation with a problem from mathematical logic, a problem, whose importance was emphasized by David Hilbert, that can be described as follows:

By 1935 there were good reasons to believe that no such algorithm exists, and this is what Turing set out to prove. Turing succeeded by first finding an unsolvable problem in terms of his machines, specifically the problem of determining for a given such machine whether it would ever output the digit 0.

Introduction

Alan Turing is remembered for many things. He is widely known as code breaker and cryptographer, and as – at least in some sense – inventor of the computer. He is if anything even more famous as the father of artificial intelligence. Beyond that he was a mathematician, mathematical logician and pioneer in the study of morphogenesis.

Logicians remember Turing for his celebrated Entscheidungsproblem paper (Turing, 1937a), for work on the λ -calculus (Turing, 1937b) and, if they are cognoscenti, for his second great paper (Turing, 1939) in the Proceedings of the London Mathematical Society. All that work was completed by 1940. It is not widely appreciated that Turing's interest in logic continued to the end of his life. His later interest in the theory of types, a central area in the foundations of mathematics, is largely forgotten. That interest has had more influence than is evident. I am going to tell the story: it is an odd one.

The one and only student

My D.Phil. supervisor at Oxford was Robin Gandy: he was the only person to take a doctorate under Turing's supervision, and also one of his closest friends.

While Turing had only one student, Gandy had many. I was one of the the cohort from the early 1970s. Gandy rather liked the thought that his students were intellectual grandchildren of Turing. We mostly cared rather less about that, but from Gandy's reminiscences we all caught a glimpse of Turing through the eyes of someone who had known him very well. Turing met Gandy in 1940 at a party in King's College, Cambridge. Gandy was a third year student, while Turing, who had intermitted his Fellowship of the College at the start of the war, was already engaged in his celebrated work at Bletchley Park. During the war, Gandy became a friend and then much later Turing's student. By the end of Turing's life Gandy had begun his academic career as a Lecturer in Applied Mathematics at Leicester. You can read about their unique relationship in the Turing biography by Andrew Hodges (1983). Here I shall focus on Turing's influence on Gandy as his Ph.D. supervisor.

Introduction

The first half of the twentieth Century was filled with a stunning group of scientists, Einstein, Bohr, von Neumann and others. Alan Turing ranks near the top of this group. I am honored to contribute to this volume commemorating his work. How much do we owe one mind? His was a pivotal role in the cracking of the Nazi war code, which profoundly aided the defeat of Nazism. His invention of the Turing machine has revolutionized modern society, from universal Turing machines to all digital computers and the IT revolution. His model of morphogenesis, the first example of a ‘dissipative structure’, to use Prigogine's phrase, is one I have myself used as a developmental biologist.

I rightly praise Turing, but seek in this chapter to go beyond him. The core issue is the human mind. Two lines of thought, one stemming from Turing himself, the other from none other than Bertrand Russell, have led to a dominant view that the human mind arises as some kind of vast network of logic gates, or classical physicsconsciousness neurons', to use F. Crick's phrase in The Astonishing Hypothesis (Crick, 1994), connected in the 1011 neurons of the human brain.

I think this view could well be right, but is more likely to be wrong. My aim in this chapter is to sketch the lines of thought that lead to the standard view in computer science and much of neurobiology, and note some of the philosophic claims for and doubts about the claim; but most importantly I wish to explore the emerging behavior of open quantum systems in an environment, their new physics, and, centrally, our capacity to construct what I will call non-algorithmic, non-determinate yet non-random Trans-Turing Systems. As we shall see, Trans-Turing Systems are not determinate, for they inherit the indeterminism of their open quantum system aspects, yet they are non-random owing to their classical aspects. They are new to us and may move us decisively beyond the beauty, and limitations, of Turing's justly famous, but purely classical-physics, discrete-time and discrete-state machine.

Beyond the above, I shall make one truly radical proposal that I believe grows out of “sum over all possible histories” formulation of quantum mechanics (Feynman,1948).

Abstract

This chapter explores a topic in the intersection of two fields to which Alan Turing has made fundamental contributions: the theory of computing and cryptography.

A main goal in cryptography is to prove the security of cryptographic schemes. This means that one wants to prove that the computational problem of breaking the scheme is infeasible, i.e., its solution requires an amount of computation beyond the reach of current and even foreseeable future technology. As cryptography is a mathematical science, one needs a (mathematical) definition of computation and of the complexity of computation. In modern cryptography, and more generally in theoretical computer science, the complexity of a problem is defined via the number of steps it takes for the best program on a universal Turing machine to solve the problem.

Unfortunately, for this general model of computation, no proofs of useful lower bounds on the complexity of a computational problem are known. However, if one considers a more restricted model of computation, which captures reasonable restrictions on the power of an algorithm, then very strong lower bounds can be proved. For example, one can prove an exponential lower bound on the complexity of computing discrete logarithms in a finite cyclic group, a key problem in cryptography, if one considers only so-called generic algorithms that cannot exploit the specific properties of the representation (as bit-strings) of the group elements.

Introduction

The task set to the authors of articles in this volume was to write about a topic of (general) scientific interest and related to Alan Turing's work. Here we present a topic in the intersection of computing theory and cryptography, two fields to which Turing has contributed significantly. The concrete technical goal of this chapter is to introduce the issue of provable security in cryptography. The article is partly based on Maurer (2005).

Computation and information are the two most fundamental concepts in computer science, much like mass, energy, time, and space are fundamental concepts in physics. Understanding these concepts continues to be a primary goal of research in theoretical computer science. As witnessed by Turing's work, many underlying questions are of as comparable intellectual depth to the fundamental questions in physics and mathematics, and are still far from being well understood.

Abstract

In his important 1939 paper, Alan Turing introduced novel notions such as ordinal logics and oracle machines. These could be interpreted as possible ingredients of an approach to model human mathematical understanding in a way that goes beyond the conventional ideas of formal systems of axioms and rules of procedure. A hope appears to have been that in this way one might circumvent the limitations to formal reasoning that are revealed by Gödel's incompleteness theorems. In line with such aims, an idea of a cautious oracle device is here introduced (differing, in intention, from related ideas put forward by others previously), which is supposed to give accurate answers to mathematical questions whenever it claims to have an answer, but which may sometimes confess to being unable to provide an answer and sometimes continues trying indefinitely without success. Despite such devices seeming to be somewhat closer to human mathematical capabilities than appears to be provided by a standard Turing machine, or Turing oracle machine, they are still limited by being subject to a Gödel-type diagonalization argument. Although leaving open the question of what actual physical processes might underlie human mathematical insight, these arguments appear to indicate a significant constraint on any such hypothetical process.

Turing's ordinal logics

In early September 1955, I attended a lecture given by Max Newman on the topic of ordinal logic. I found the lecture to be one of the most fascinating that I ever attended. Alan Turing had died only a little over a year earlier and this talk was dedicated to him, being essentially based on Turing's 1939 paper on this topic. Newman also started his lecture by providing, as Turing had done in his paper, an introduction to Church's λ -calculus. It has been said that the somewhat limited initial impact that Turing's 1939 paper had on the mathematical community at that time may have been partly due to his phrasing the paper in terms of the λ -calculus, which is hard to employ in an explicit way and makes the reading difficult. Nonetheless, one of the things that did strike me particularly about Newman's lecture was the extraordinary economy of concept exhibited by Church's calculus.

Introduction

We offer here some historical notes on the conceptual routes taken in the development of recursion theory over the last 60 years, and their possible significance for computational practice. These illustrate, incidentally, the vagaries to which mathematical ideas may be susceptible on the one hand, and – once keyed into a research program – their endless exploitation on the other.

At the hands primarily of mathematical logicians, the subject of effective computability, or recursion theory as it has come to be called (for historical reasons to be explained in the next section), has developed along several interrelated but conceptually distinctive lines. While this began with what were offered as analyses of the absolute limits of effective computability, the immediate primary aim was to establish negative results of the effective unsolvability of various problems in logic and mathematics. From this the subject turned to refined classifications of unsolvability for which a myriad of techniques were developed. The germinal step, conceptually, was provided by Turing's notion of computability relative to an ‘oracle’. At the hands of Post, this provided the beginning of the subject of degrees of unsolvability, which became a massive research program of great technical difficulty and combinatorial complexity. Less directly provided by Turing's notion, but implicit in it, were notions of uniform relative computability, which led to various important theories of recursive functionals. Finally the idea of computability has been relativized by extension, in various ways, to more or less arbitrary structures, leading to what has come to be called generalized recursion theory. Marching in under the banner of degree theory, these strands were to some extent woven together by the recursion theorists, but the trend has been to pull the subject of effective computability even farther away from questions of actual computation. The rise in recent years of computation theory as a subject with that as its primary concern forces a reconsideration of notions of computability theory both in theory and practice. Following the historical sections, I shall make the case for the primary significance for practice of the various notions of relative (rather than absolute) computability, but not of most methods or results obtained thereto in recursion theory.

Alan Turing's exploits in code-breaking, philosophy, artificial intelligence and the foundations of computer science are by now well known to many. Less well known is that Turing was also interested in number theory, in particular the distribution of prime numbers and the Riemann hypothesis. These interests culminated in two programs that he implemented on the Manchester Mark 1 (see Figure 3.1), the first stored-program digital computer, during its 18 months of operation in 1949–1950. Turing's efforts in this area were modest, and one should be careful not to overstate their influence. However, one cannot help but see in these investigations the beginning of the field of computational number theory, bearing a close resemblance to active problems in the field today despite a gap of 60 years. We can also perceive, in hindsight, some striking connections to Turing's other areas of interests, in ways that might have seemed far-fetched in his day. This chapter will attempt to explain the two problems in detail, including their early history, Turing's contributions, some developments since the 1950s, and speculation for the future.

Prime numbers

People have been interested in prime numbers since at least the ancient Greeks. Euclid recorded a proof that there are infinitely many of them around 300 BC (Narkiewicz, 2000, §1.1.2). His proof, still one of the most elegant in all mathematics, can be expressed as an algorithm:

1. Write down some prime numbers.

2. Multiply them together and add 1; call the result n.

3. Find a prime factor of n.

For instance, if we know that 2, 5 and 11 are all prime then, applying the algorithm with these numbers, we get n = 2× 5× 11+1 = 111, which is divisible by the prime 3. By an earlier theorem in Euclid's Elements, the number n computed in step (2) must have a prime factor (and in fact it can be factored uniquely into a product of primes by the Fundamental Theorem of Arithmetic), so step (3) is always possible. On the other hand, from the way that Euclid constructs the number n, the prime factor found in step (3) cannot be any prime written down in step (1). Thus, no list of primes can be complete, i.e. there are infinitely many of them.