ELFT HÍRADÓ

[Laszlo E Szabo <leszabo AT hps.elte.hu>]

Department of HISTORY AND PHILOSOPHY OF SCIENCE
Eotvos University, BudapestPazmany P. setany 1/A Budapest
Phone/Fax: (36-1) 372 2924 
Department's Home Page:http://hps.elte.huhttp://hps.elte.hu

PHILOSOPHY OF SCIENCE COLLOQUIUM                
Room 6.54 (6th floor) Monday 4:00 PM 
___________________________
 11 March 4:00 PM 6th floor 6.54 
Language: English, except all participants speak Hungarian

G a b o r   E t e s i*  ** (lecturer) and
I s t v a n   N e m e t i**
*   Yukawa Institute, Kyoto University, Japan
**  Alfred Renyi Institute of Mathematics, Budapest

General relativistic- (and/or quantum-) computability; computing
non-Turing-computable functions in Malament-Hogarth spacetimes

It used to be a (meta) theorem of mathematical logic that
mankind will never know that ZFC (which forms the foundation
of mathematics) is consistent, assuming it is. We will argue
that this meta-theorem is gone, it is no more provable.
We will report on (convergent) results of various research
groups at various parts of the world coming, independently,
to the same conclusion which is, roughly, that Turing computability
may not (after all) be the final limit of the capabilities
of artificial computing devices. Some of the above mentioned
researchers are e.g. Hogarth (Cambridge), Malament, Earman,
ourselves, Kieu (Australia), F. Tipler, to mention only
a few.

We investigate the Church--Kalmar--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.
(We note that the goal of ``computing the uncomputable''
is distincly more modest than executing so called supertasks.
Indeed, we do not claim possibility of the second.)

A paper advocating carefully and it detail the view we adopt
here -- that developments in the background physical theory
can influence profoundly the fundamentals of the theories
of computability and logic -- appeared in Bull. Symbolic
Logic Vol. 6 No 3 (2000), pp.265-283 by Deutsch et al. Our
paper on this subject is available on the following internet
address: 
[http://ipsapp008.lwwonline.com/ips/frames/menu.asp?J=4779&S=36698&M=40800#]
A further useful reference is Hogarth, M.: ``Predictability,
Computability, and Spacetime'', pp.1-123, available from
[mh10026 AT cam.ac.uk].

 
____________________________
 The 60-minute lecture is followed by a 5-minute break. Then
we held a 30-60-minute discussion. 
The participants may comment the talks and initiate discussion
on the Internet. The comments should be written in the language
of the presentation. 
The organizer of the seminar: Laszlo E. Szabo 
-- 

Laszlo E. Szabo
Department of Theoretical Physics
Department of History and Philosophy of Science
Eotvos University, Budapest
H-1518 Budapest, Pf. 32, Hungary
Phone/Fax: (36-1)372-2924
Home: (36-1) 200-7318
Mobil/SMS: (36) 20-366-1172
http://hps.elte.hu/~leszabo