ABSTRACT
GRAVITATIONAL COMPUTING AND THE FALSITY OF THE CHURCH-TURING THESIS
Dr. Robin Hirsch
Department of Computer Science, UCL
A common version of the Church-Turing Thesis states that every "effective,
algorithmic calculation" can be carried out by an ordinary Turing Machine.
Although not proven, it is fundamental to the whole of theoretical computer
science. In this talk I cast some doubt on this thesis by describing an
effective algorithmic calculation that could solve the halting problem (or
your favourite uncomputable problem). The algorithm runs in constant time!
The only difficulty in carrying out this computation yourself is that you
need
something like a rotating black hole. Other than that, it is very simple.
This work is based on my reading of recent research due to Malament, Hogarth,
Earman, Nemeti, Etesi and others.
Maintained by rbennett@cs.ucl.ac.uk