"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 Computation
There 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 Objects
There 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
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 Interaction
Penrose, 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
4) Definability of Relations on the Natural World
From 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-invariance
There 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 Computation
Penrose, 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
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 Paradigm
The 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
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?