COMPUTER SCIENCE COLLOQUIUM

Real Computation, Hypercomputation, and Continuity

Martin Ziegler Deptartment of Mathematics and Computer Science University of Southern Denmark

Tuesday, April 5, 2005, at 14:15 Seminar Room

ABSTRACT

Leibnitz said, "Natura non facit saltus."

Indeed, according to the Church-Turing Hypothesis any physical process can be simulated by a Turing Machine; and a function over the reals computable by a Turing Machine is necessarily continuous due to the Main Theorem of Recursive Analysis.

But what if the Church-Turing Hypothesis fails?

We investigate three types of Hypercomputation over real numbers. It turns out that even oracle access to the Halting Problem is still not sufficient for computing discontinuous functions whereas, surprisingly, nondeterminism is.

Host: Klaus Meer

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: March 20, 2005.

Joan Boyar (joan@imada.sdu.dk)