The articles in this issue span a remarkable range of topics that testify to the richness of Alan Turing's intellectual legacy in the modern conception of computation. There are deep connections with fundamental issues in physics, mathematics, artificial intelligence, philosophy and beyond.

One group of articles studies the aspects of classical foundations of computation that show surprising connections to a wide range of topics of current concern. In particular, the basic concept of viewing programs as data, in which Turing anticipated the von Neumann architecture of the stored program computer, opens up a huge range of possibilities, which are still far from being completely explored or understood.

— From mathematician Robert I. Soare [1], we have a major reappraisal of Turing's classical 1930s work on machine computation, and the balance between program and information. Quoting Feferman's reference to the oracle Turing machine as a ‘new idea that was to change the face of the general theory of computation’, Soare traces the historical and contemporary significance of the oracle machine over a range of fields.

— The article by Jones & Simonsen [2] discusses the ramifications of the programs as data concept and considers general desirable features of models of computation. It discusses a recently proposed model, motivated by biology, the ‘blob’ model, and to what extent it meets these ideal features and how the remaining desiderata could be addressed.

— The article by Marion [3] is motivated by applications of Kleene's second recursion theorem, which is the key mathematical fact expressing the power of the program-as-data concept, to modelling computer viruses. The key features of viruses are self-replication and mutation. The paper discusses a concrete computational model of these features in the form of self-modifying register machines.

— The article by Dershowitz [4] discusses the classical Turing notion of universality, with a careful foundational consideration of the constraints that need to be imposed on the coding of programs and on pairing in order to avoid ‘cheating’, which would vitiate the analysis of computation, leading to a notion of ‘honest universality’.

Another group of articles discusses various aspects of the connections between computation and physics.

— The article by Dowek [5] discusses the physical Church–Turing thesis and the issue of non-deterministic computation represented in terms of effectively enumerable relations as an algorithmic basis for expressing non-deterministic physical theories.

— Beggs and co-workers [6] investigate an abstract framework for interfacing algorithms and physical systems, with the notion of oracle again taking centre stage. There are basic motivational questions to this work, including: ‘How much information can be extracted from a physical process? How quickly can it obtained?’.

— Hardy [7] describes a novel formulation for quantum mechanics that is based much more directly on operational concepts than on the traditional Hilbert-space formalism. This formalism makes extensive use of diagrammatic representations of ‘operator tensors’. It is close in spirit to computationally inspired formalisms.

— Ekert

*et al.*[8] show how Bell's theorem in the foundations of quantum mechanics leads to a fundamentally novel approach to the whole issue of cryptography, another central concern of Turing's scientific career.— Vazirani & Vidick [9] show that quantum mechanics can be used to produce a source of genuine randomness, with an accompanying kind of ‘Turing test’ that uses no-signalling properties of the device to certify that true randomness has been achieved. Again, there are connections with Bell's theorem in the foundations of quantum mechanics.

Much of Turing's early work in logic is related to real computation, with subsequent anticipations of the important role of randomness.

— Proof-mining delivers new information via the process of logically bringing out the constructive elements of proofs described in a natural language. Kohlenbach & Leustean [10] describe some recent developments in the context of Turing's seminal work on computable real numbers.

— Montalbán [11] reviews recent work applying the technical framework of classical computability to measure the complexity of relations over particular structures. The viewpoint developed in this article aims to make the area approachable to a wider community of researchers.

— The article by Barmpalias & Dowe [12] arises from Wallace's work on information theory, with regard to his interest in the notion of a real preserving universality with respect to a prefix-free machine, and in particular the probability of this event.

— Allender

*et al.*[13] relate their work to Turing's interest in probabilistic computation, and to the role of random elements. The article is a useful addition to recent developments in the area of derandomization.

A key element of the Turing legacy is his work on information and intelligent machines, and their philosophical, theoretical and practical dimensions. The articles that conclude this Theme Issue are diverse, innovative and sure to be provocative.

— We start this part with a scene-setting philosophical paper on information and levels of abstraction, a key concept to Turing's extraction of meaningful questions from their more ill-defined everyday versions. Floridi [14] relates three main philosophical questions on the nature and role of information to what ‘promises to be one of the most exciting and beneficial areas of philosophical research of our time’.

— Smolensky [15] starts out from the widespread assumption, going back to Turing, that thought is computation over ideas. This article presents a computational account of cognition, modelling the computation of symbolic mental functions with subsymbolic neural computation.

— Focusing on computational learning theory, Case & Kötzing [16] pay tribute to ‘Alan Turing's wonderfully profound and influential ideas about mind and mechanism’, and proceed to analyse the problem of algorithmically learning a description for an infinite sequence presented via larger and larger initial segments of that sequence.

— Seth Lloyd [17] contributes the final article in this remarkable collection, with the enticing title ‘A Turing test for free will’. According to this test, ‘a decision maker who passes this test will tend to believe that he, she or it possesses free will, whether the world is deterministic or not’.

It is in the nature of centenaries that they present the celebrants with fast approaching deadlines of disturbing solidity. Even as we write this, we are thankful to our authors and anonymous reviewers, and to Suzanne Abbott, our encouraging and ever-patient editor at the Royal Society, for making this Turing Theme Issue possible. We are happy to see such an appropriate tribute to Alan Turing materialize, and can only wish to still be here to see what new developments the bi-centenary Theme Issue will bring!

## Footnotes

One contribution of 18 to a Theme Issue ‘The foundations of computation, physics and mentality: the Turing legacy’.

- This journal is © 2012 The Royal Society