**From:** Christopher Barton (*CJB153@mercury.anglia.ac.uk*)

**Date:** Fri Apr 27 2001 - 13:26:26 MDT

**Next message:**Jordan Dimov: "RE: Computational reflection"**Previous message:**Patrick McCuller: "RE: 10 atoms across"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Below is an abstract of a paper I thought some of you might find interesting. It's not light on mathematics, but it might be a new angle on the recent dicussions on the limits of computing.

I've got a postscript if anyone wants a look.

James

--------------------------------------------------------------------------------------------------------

Title: Non-Turing computations via Malament-Hogarth space-times

Authors: Gabor Etesi (Yukawa Institute, Japan), Istvan Nemeti (Renyi

Institute, Hungary)

Comments: 24 pages, LaTex with two eps-figures

We investigate the Church-Kalm\'ar-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. (37kb)

**Next message:**Jordan Dimov: "RE: Computational reflection"**Previous message:**Patrick McCuller: "RE: 10 atoms across"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:00:36 MDT
*