HEINZ NIXDORF INSTITUT
University of Paderborn
Theoretical Computer Science
Group of Meyer auf der Heide

Advanced Computability Theory

WS 03/04

Martin Ziegler

Dates

Lecture (V2)

Tue 17.00  - 18.30    D1.303        Martin Ziegler

Tutorial (Ü1)

Tue 16.10  - 16.55    D1.303        Martin Ziegler

Examination as no. 5562.
The lecture is to be continued in WS04/05 on Hypercomputation !

Introduction

What can computers do in principle; and, more important, what is it that they in principle cannot? This question reveals that Computability, other than in Complexity Theory, releases any kind of restriction on resources such as running time or memory consumption; and nevertheless, some important problems are still provably uncomputable as Alan Turing revealed (any student of Computer Science should be able to name such a problem)!
But how about computability over real numbers? It is rarely known that Turing has treated this question, too. We extend his theory from single reals to vectors, to functions, and to sets, and we compare it to other new theories of computability. This turns out to have strong relations to physics which in turn contributes many open computability problems.

Integer Computation
1. WHILE-Programs
2. Universality of WHILE
3. μ-Recursion
4. Turing Machines
5. Gödel Numberings, Prefix Codes
6. Church-Turing's Hypothesis
7. Quines, Recursion Theorem
Languages
1. Semi-/Un-/Decidability
2. Rice's Theorem
3. Arithmetic Hierarchy, Post's Theorem
4. Grammars and Semi-Decidability
5. Regular Languages, Myhill/Nerode
ω-Languages
1. Intermission: Ramsey Theory
2. Büchi Automata
3. are closed under complement
Real Turing-Computability
1. Binarily computable reals
2. Naively computable reals
3. Cauchy-computable reals
4. Markov-computable functions
5. Grzegorczyk-computable functions
6. Markov vs. Grzegorczyk
7. Extensions:
  1. vector-valued functions of several variables
  2. Markov-computable operators
  3. Grzegorczyk-computable operators
  4. Computability of subsets of Reals
  5. over arbitrary structures of cardinality c
Algebraic Computing
1. Straight-Line Programs=Arithmetic Circuits
Analytic Machines

Exercises

to be submitted by Monday 2:15pm into the box in D3 hall, lowest right corner.

are available from here.

Bibliography

K. Weihrauch: «Computable Analysis», Springer 2000.
K. Weihrauch: «Computability», Springer 1987.
L. Blum, F. Cucker, M. Shub, S. Smale: «Complexity and real computation», Springer 1998.
M. Li, P. Vitanyi: «An Introduction to Kolmogorov Complexity and its Applications», Springer.
B.M. Moret: «The Theory of Computation», Addison-Wesley.
D.S. Bridges: «Computability», Springer 1994.
M. Sipser: «Introduction to the Theory of Computation», PWS (1997).
M. Nivat, D. Perrin: «Automata on Infinite Words», Springer LNCS 192 (1985).
J. van Leeuwen: «Handbook of Theoretical Computer Science», vol.B (Formal Models and Semantics), Elsevier (1990).
E. Smith: «Elementare Berechenbarkeitstheorie», Springer (1996).
Engeler, Läuchli: «Berechnungstheorie für Informatiker», Teubner (1992).
P. Odifreddi: «Classical Recursion Theory», vol.125, North-Holland (1989).
R.I. Soare: «Recursively Enumerable Sets and Degrees», Springer (1987).
N. Pippenger «Theories of Computability», Cambridge (1997).

Martin Ziegler