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.

  1. 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
  2. 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
  3. ω-Languages
    1. Intermission: Ramsey Theory
    2. Büchi Automata
    3. are closed under complement
  4. 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
  5. Algebraic Computing
    1. Straight-Line Programs=Arithmetic Circuits
  6. Analytic Machines

Exercises

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

Bibliography


Martin Ziegler