##
Etesi, G. and Németi, I.

#
Non-Turing computations via Malament-Hogarth space-times

We investigate the Church--Kalmár--Kreisel--Turing Theses concerning
theoretical (necessary) limitations of future computers and of deductive
sciences, in view of recent results of classical general relativity theory.
We argue that (i) there are several distinguished Church--Turing-type
Theses (not only one) and (ii) validity of some of these theses depend on
the background physical theory we choose to use. In particular, if we
choose classical general relativity theory as our background theory, then
the above mentioned limitations (predicted by these Theses) become no more
necessary, hence certain forms of the Church--Turing Thesis cease to be
valid (in general relativity). (For other choices of the background theory
the answer might be different.)
We also look at various ``obstacles'' to computing a
non-recursive function (by relying on relativistic phenomena) published in
the literature and show that they can be avoided (by improving the
``design'' of our future computer). We also ask ourselves, how all this
reflects on the arithmetical hierarchy and the analytical hierarchy of
uncomputable functions.

Retrieve dvi, PostScript or PDF version.