Logical Approaches to Computational Barriers

Uncomputability below and up to the Real Halting Problem

Speaker:
| Martin Ziegler |

Author(s): |
Klaus Meer and Martin Ziegler |

Slot: |
Array, 11:10-11:30, col. 4 |

Most of the existing work in real number computation theory concentrates on
complexity issues rather than computability aspects. Though some natural
problems like deciding membership in the Mandelbrot set or in the set of
rational numbers are known to be undecidable in the Blum-Shub-Smale (BSS) model
of computation over the reals, there has not been much work on different
degrees of undecidability. A typical question into this direction is the real
version
of Post's classical problem: Are there some explicit undecidable problems
below the real Halting Problem?

In this paper we study three different topics related to such questions: First
an extension of a positive answer to Post's problem to the linear setting.
We then analyze how additional real constants increase the power of a BSS
machine. And finally a real variant of the classical word problem for groups is
presented which we establish reducible to and from (that is, complete for) the
BSS Halting problem.

websites: Arnold Beckmann | 2006-05-10 |