Workshop Overview
"The Incomputable" - Workshop Overview
|
The aim of this
Turing centenary workshop is to bring together, mathematicians working on the abstract theory of incomputability and randomness, with other scientists, philosophers and computer scientists grappling with the realities of an apparent incomputability in the real world. In prospect is a uniquely synergetic gathering, with long-term consequences for the breaking down of inter-disciplinary barriers, and the establishing of new collaborations around a number of 'big questions': |
||
1) Challenging Turing: Extended Models of ComputationThere is growing evidence from computer science, physics, biology, the humanities, that not all features of the real world are captured by classical models of computability.To what extent can we develop new computational paradigms based on natural processes, and characterise their computational scope? There are theoretical obstacles to identifying 'natural examples' of incomputable mathematical objects - How does this play out in the physical world? Can we find new mathematical techniques for identifying incomputability, or discover new results explaining the obstacles we encounter? |
||
2) The Search for 'Natural' Examples of Incomputable ObjectsThere is a definition of "natural" understood by everyone. The New Oxford Dictionary of English (1998 edition), describes it as: "natural - existing in or caused by nature". Natural numbers - in fact, the whole of school arithmetic - certainly qualifies as 'natural'. In 1970, Yuri Matiyasevich put the finishing touches to a remarkable proof, many years in the making, that the sort of arithmetical questions a school student might ask lead directly to a rich diversity of incomputable sets - a diversity which went far beyond the original examples from the 1930s. The negative solution to Hilbert's Tenth Problem, collectively due to Martin Davis, Matiyasevich, Hilary Putnam, and, crucially, Julia Robinson, demonstrated that all the incomputable sets which could be artificially enumerated by recursion-theoretic techniques were not artificial at all - they arose naturally as solution sets of the familiar diophantine equations.The main unsolved question is: Can one discover a specific natural set, a computably enumerable set, which is incomputable but not computably equivalent to the halting set of a universal Turing machine? Related to this is Slaman's long-standing question: Are there incomputable computably enumerable sets of definable Turing degree, not computably equivalent to the halting set of a universal Turing machine? For the working scientist, naturalness is captured within a rather different kind of mathematics, that of real numbers and differential equations. One of the most widely-known and enduring discoveries, due to Pour-El and Richards, was a differential equation with computable boundary conditions leading to incomputable solutions. More recently, researchers such as Roger Penrose and Stephen Smale have been associated with investigations of the computability of well-known mathematical objects with known connections with complexity in nature, such as the Mandelbrot and Julia sets. The main question requiring a generally acceptable answer is: Is the Mandelbrot set computable? |
||
3) The Importance of InteractionPenrose, Sorkin, Smolin and others have suggested that causality is fundamental to a comprehensive understanding of the nature of the physical universe. From a mathematical perspective, interactive computation is a basic feature of all areas of science and of computer science, and is modeled in a wide range of contexts (including Newtonian mechanics) by the notion of an oracle Turing machine.To what extent can we further develop the explanatory power of the theory of this extended model to throw light on natural phenomena? Are there higher order features of this extended Turing model that provide triggers to the putative incomputability of the large-scale universe? |
||
4) Definability of Relations on the Natural WorldFrom Hans Reichenbach onwards, a select band of scientists have sought to clarify scientific theory via the notion of mathematical definability. A primary task is to apply and extend our understanding of definability over computational models of the real world. The clarification of the status of the long-standing 'Bi-interpretability Conjecture', hypothesising a close mathematical relationship between second-order arithmetic and the Turing causal model, is essential to further progress.What is the basic character of the automorphism group over the Turing universe? What consequences does this have for the nature of the causal structure of the real universe? Is there an identifiable local theory which is more appropriate for such a modeling? |
||
5) Randomness, Non-locality and Non-invarianceThere are a number of basic assumptions of physics in need of foundational underpinnings. More ad hoc frameworks, such as those related to string theory, have proved insufficiently basic to uniquely define, for instance, the geometry of time and space. It may be that work towards computability-theoretic models of causality, having automorphism groups in accord with what we observe in the real world, may clarify foundational aspects of the science.What does the rapidly expanding mathematical theory of randomness tell us about quantum 'randomness' - Is quantum randomness really random, or merely incomputable? What is the significance of the new definable classes emerging from computability theory and the study of effective randomness? How does real non-locality relate to higher-order properties of appropriate computational models? How do invariant relations over computational models of causality explain the emergence of natural laws and the quasi-classical world of everyday experience? |
||
6) Mind, Matter and ComputationPenrose, Stapp and others have identified analogies between mental and quantum phenomena. An interest in the possibility of such a connection, physical or theoretical, goes back to Turing himself.Can we develop the mathematics of computable causality, and its higher-order features, to give substance to these intuitions? Can we elucidate the role of emergence and representation in mental processes via suitably well-understood computational models? Can we further appreciate the limitations of scientific thought through an understanding of how 'computational effects' have real substance? And can we get more understanding of how it is that even when we understand the 'design' of our computational models, the actual properties of those models can access levels beyond what the scientific method can reach? To what extent do existing connectionist models transcend other more classical ones? And manifest observable outcomes similar to those encountered in higher mentality? |
||
7) Embodied Computation, and the Universality ParadigmThe Turing machine, so simple in its embodiment, has underpinned a widely accepted subsuming of computation by mathematics. The focus of Turing in his 1936 paper on the specifics of embodied computation in the formulating of his model have been seen as historical, a useful feature of a 'proof' of the Church-Turing Thesis. This functionalist outlook on computation has been thrown in doubt by experiences of computation and physical phenomena in many different contexts, from the internet to mental phenomena.What is the mathematics validating the usefulness of evolving computing hardware? Do suitable models of physical and mental computation reinforce the well-established paradigm of the universal machine? What is the mathematics capable of encompassing an embodiment resurrected? What is the relevance of the mathematics of morphogenesis and emergence? |
||
