Turing’s Legacy

This workshop examined Turing’s legacy in 2012, particularly in the way that his analysis of computation is viewed 77 years after it was first published. Greg Michaelson introduced the background history leading to Turing’s 1936 paper, as well as summarising work on the limits of computation since then. Paul Cockshott followed up with a discussion of how physical theories constrain thinking about computation. In contrast Dominique Chu introduced issues in biological - or cellular - computation, and Ashely Montanaro showed the possibilities of quantum computation, even if no realistic quantum computer is ever built.

Mike Stannett’s survey gave an overview of the physical possibilities that might go beyond Turing computation, while Mark Hogarth contrasted computability with geometry, and argued that the current status of the Church-Turing thesis needs serious re-consideration, just as the pre-eminence of Euclidean geometry was overturned a century ago. In conclusion, Barry Richards re-affirmed Turing’s concrete approach in contrasting his approach in understanding “computational intelligence” to the traditional (GOFAI) position.

Simon Thompson, Workshop Organiser, April 2012

Greg Michaelson (Heriot-Watt) The limits to computation

How do laws of nature and of logic constrain what we can compute?

Paul Cockshott (Glasgow) How physics constrains real value calculation

The talk will look at the Universality of Turing’s computer in the context of the historically preceding 20th century computers. In this context it will mention the prior work of Dumaresq and Dreyer. It then goes on to why Turing considered the digital nature of the computer to be one of its critical features and why what we know about the laws of physics validates this choice. Finally it looks at why the idea of a computer as opposed to a calculus was significant.

Dominique Chu (Kent) The biological cell as a stochastic computer

Computation is essential for biological cells to survive. A successful cell has to be able to sense its environment and adjust its internal states in response to changes of this environment. We do now understand fairly well how biological components can be used to build computational components, such as logic gates. However, the community has only fairly recently started to take a serious interest in the biophysical limits to cellular computation. One of the most important limitations is the stochastic nature of biochemical reactions.

As it turned out, the quality of a computational process is strongly dependent on the resources that the cell is willing to allocate to a particular computation. Ultimately, this means that a better (i.e. more accurate or faster) computation equates to available less resource available for growth. In this talk I will present some approaches to understand the cell as a computer and how the resource allocation impacts on its computational properties. I will discuss both conceptual models and the results of large-scale simulations of the yeast-translation system.

Ashley Montanaro (Cambridge) The Church-Turing thesis in a quantum world

The nascent field of quantum computation poses a significant challenge to (some variants of) the Church-Turing thesis. In this talk, I will briefly discuss several aspects of this challenge: the apparent ability of quantum computers to simulate physical systems which cannot be efficiently simulated classically; models in which quantum computation is provably superior to classical computation; and applications of the study of quantum computation, even if large-scale quantum computers are never built.

Mike Stannett (Sheffield) Computing via Physical Theories

We consider an abstract model of general computation, asking what logical constructs underpin the question "what can be computed?" and the extent to which these constructs can be implemented (ie given a meaningful semantics) relative to different models of physical reality. While Newtonian models permit logical implementations of Turing machines, the existence of n-body non-collision singularities ensures that program correctness can never be guaranteed; while (some) relativistic models permit the logical implementation of super-Turing

behaviours. The relationship between computation and physics goes both ways: by considering what can and can't be computed by a computer moving along a closed timelike curve (CTC) we argue that CTCs can act as information storage devices, but that their capacity is extremely limited.

Mark Hogarth (Cambridge) The Church-Turing Thesis is a pseudo-proposition

The new and flourishing field of unconventional computing (hypercomputing) has prompted some to question the alleged truth of Turing's thesis. I am prompted towards a more radical view. I maintain that what these exciting investigations reveal is that there is no such thing as an 'ideal computer', and consequently Turing's thesis, which in essence asserts the equation of this ideal computer with the Turing machine, should be seen as a pseudo-claim. Aided by an analogy with the concept of geometry, I will attempt to paint a picture of computability in which Turing's thesis – or indeed any thesis that fundamentally privileges a computer – is absent. Time permitting, I will also say something about how this approach reveals that pure mathematics itself is really part of physics.

Barry Richards (Edinburgh and Imperial College, retd.) Turing's Legacy and AI: Two perspectives (revised slides)

I shall consider two questions that continue to vex some in AI. The first is: Can the typical performance of a heuristic search algorithm for an NP-complete problem be characterized / predicted? Here I shall focus on problem solving in AI. The second question is: Is intelligent search characteristic of human problem solving? Here I shall contrast Turing’s approach with that of AI-as-symbolic-computation. The two questions are related but generate different challenges to the computational approach to intelligence.