John V. Tucker
University of Wales at Swansea
[web page]
TITLE: Computability via experimental procedures applied to classical mechanical systems
ABSTRACT: In this lecture I will survey some old and new results that try to answer these
questions:
1. What are the functions computable by experimental procedures applied to
physical systems?
2. How do they compare with the functions computable by algorithms?
3. Does there exist a physical system that exhibits non algorithmically
computable behaviour?
First, I will give some brief background on computability with continuous data, such
as real numbers, and will report on my recent work with J I Zucker (McMaster).
Second, I will describe my new research programme with Edwin J Beggs (Swansea)
investigating notions of experimental computation using
mechanics. One aim is to study the embedding of computational models and non-computable
behaviours into small simple subtheories of physical theories in order
to explore the boundary between the computable and non-computable in physical theories.
Some new theorems show there exists simple kinematic systems that can decide membership
for any set of natural numbers, under
Newtonian and Relativistic mechanics. These results give technical insight into the
questions above, and shows they are painfully subtle; it also
|
![[Oxford Spires]](http://web.comlab.ox.ac.uk/im/spires.gif){kind=small}
Introduction to OASIS
Michaelmas 2004