Computability Theory

Honours Module in Mathematics of Computer Science.


Lecturer

Vasco Brattka

Laboratory of Foundational Aspects of Computer Science
Department of Mathematics & Applied Mathematics
University of Cape Town

Time Table (2011)

Lectures for this module take place from The last period on Thursdays will be used as tutorial.


Course Description

Computability theory is a basic area of mathematics and computer science and its main goal is to understand up to which extent problems can be solved algorithmically at all. While algorithms have been implicitly studied since ancient times (Euclid's algorithm is an example), it is only since the seminal work of Turing, Gödel and others that there is a precise notion of an algorithm. By studying this precise notion it turns out that certain problems are not solvable algorithmically in principle (for instance, there is no general method to decide whether two programs compute the same function). Topics that will be covered in this module include:
  • Models of computability
  • Church's thesis
  • Computable and Computably enumerable sets
  • Universal Turing machines and Gödel numberings
  • Reducibility and simple sets
  • Creative and productive sets,
  • Arithmetical hierarchy
  • Turing reducibility and Post's problem
  • Gödel's Incompleteness Theorem
  • Applications to logic
  • Hilbert's 10th Problem
  • Computability on infinite sequences
  • Theory of representations
  • Computability on real numbers
  • Borel hierarchy
  • Martin-Löf randomness


"Universal Turing Machine" © 2003 Jin Wicked, USA.
All rights reserved. Used by permission. JinWicked.com


Contents

Part A: Computability on Numbers

  1. Introduction
    • Introduction
    • Hilbert's Tenth Problem
    • The Theorem of Davis, Robinson and Matiyasevich
    • Register machines
  2. Computable Functions
    • Computable functions
    • Terminology for partial functions
    • Generalized register machines
    • Closure schemes for computable functions
  3. Recursive Functions
    • Recursive and primitive recursive functions
    • Cantor's diagonal method
  4. Computability on Natural Numbers and Other Sets
    • Klenee's Normalform Theorem
    • Church's Thesis
    • Numberings
  5. Gödel Numberings
    • Gödel numbering of computable functions
    • Universal machines and Turing's utm-Theorem
  6. Effective Programming
    • Effective programming and Kleene's smn-Theorem
    • Rogers Equivalence Theorem
  7. The Recursion Theorem
    • The Fixpoint Theorem
    • Selfreproducibility
    • The Complexity Theorem
    • Diagonalization
  8. Computable Sets
    • Computable and Computably Enumerable sets
    • Characterizations
    • The Projection Theorem
    • The Complementation Theorem
  9. The Halting Problem
    • The Selfapplicability Problem
    • Russel's Paradox
    • Closure Properties
    • The Graph Theorem
    • Reducibility
    • The Halting Problem
  10. Index Sets
    • Characterization of c.e. sets by reducibility
    • Recursive and c.e. sets with respect to numberings
    • Index sets
    • The Theorem of Rice
    • The Theorem of Myhill and Shepherdson
    • The Correctness Problem
    • The Equivalence Problem
  11. Productive and Creative Sets
    • Post's Problem
    • Completeness
    • Productive and Creative Sets
    • Myhill's Characterization of Creativity
  12. Immune Sets and Simple Sets
    • Immune Sets and Simple Sets
  13. Kolmogorov Complexity
    • Kolmogorov Complexity
    • Random numbers and Lawful Numbers
    • Berry's Paradox
    • Many-one Degrees
    • The Lattice of c.e. Sets
    • Mezoic Sets
  14. Gödel's Incompleteness Theorem
    • First Order Arithmetic
    • Arithmetical Sets and Functions
    • Gödel's Sequence Number Theorem
    • Productivity of Arithmetic Truth
    • Gödel's Incompleteness Theorem
    • Chaitin's Incompleteness Theorem
  15. Hilbert's Tenth Problem
    • Diophantine Sets and Functions
    • A Number Theoretic Characterization of Computability
    • The Theorem of Davis, Robinson and Matyasevich
    • Hilbert's Tenth Problem
    • Davis' Incompleteness Theorem
  16. Turing Reducibility
    • Oracle Machines
    • Relativized Computability
    • Turing Reducibility
  17. Post's Problem
    • The Theorem of Kleene-Post
    • Post's Problem for Turing Reducibility
  18. The Theorem of Friedberg-Muchnik
    • The Theorem of Friedberg-Muchnik
  19. The Jump
    • The Jump
    • The Jump on Degrees
    • The Jump Theorem
  20. The Arithmetical Hierarchy
    • The Arithmetical Hierarchy
    • The Theorem of Kuratowski and Tarski
    • The Theorem of Post
  21. Decidability in the Limit
    • Completeness in the Arithmetical Hierarchy
    • Decidability in the Limit
    • Shoenfield's Limit Lemma
  22. The Boolean Hierarchy
    • Boolean Algebras
    • Differences of Computably Enumerable Sets
    • Trial and Error Predicates
    • Theorem of Putnam
    • Ershov Hierarchy
    • Bounded Truth Table Reducibility

Part B: Computability on Sequences

  1. Computability on Sequences
    • Infinite and Finite Sequences
    • Baire Space and Cantor Space
    • Continuous Functions on Baire Space
    • Computable Functions and Continuity
    • Turing Machines
    • Composition and Computability of Points
    • Computable Functions and Turing Reducibility
    • Computability of Sequences
  2. Approximation and Universal Functions
    • Approximation of Continuous Functions by Word Functions
    • Approximation Theorem
    • Universal Function Theorem
    • Translation Theorem
  3. Open Sets and Effective Continuity
    • Computably Enumerable Open Sets
    • Computable Sequences of C.e. Open Sets
    • Effective Continuity Theorem
    • Wadge Reducibility
    • Theorem of Myhill and Shepherdson
    • Theorem of Kreisel, Lacombe and Shoenfield and Čeitin
  4. Martin Löf Randomness
    • Borel Measures on Topological Spaces
    • The Uniform Borel Measure on Cantor Space
    • Martin-Löf Randomness
    • Computable Points and Random Points
    • C.e. Open Sets of Full Measure
    • Random Sets are Bi-Immune
    • Universal Martin-Löf Test
    • Theorem of Kučera and Gács
    • Kolmogorov Complexity and the Theorem of Schnorr
  5. The Baire Category Theorem
    • Baire Category Theorem
    • Meager and Comeager Sets
    • Computable Baire Category Theorem
    • Effectively Comeager Sets
    • Fibers of Non-Computable Points under Computable Maps
    • The Theorem of Kleene-Post
    • The Theorem of Shoenfield, Kleene and Post
  6. Closed Sets and Trees
    • Trees
    • Trees and Closed Sets
    • Weak Kőnig's Lemma
    • The Kleene Tree
    • Kreisel's Basis Lemma
  7. Low Basis Theorems
    • Isolated Points in Co-c.e. Compact Sets
    • Cardinality of Co-c.e. Sets without Computable Members
    • Bases for Co-c.e. Closed Sets
    • Low Basis Theorem
    • Co-C.e. Closed Sets with Only Random Members
  8. Borel Hierarchy
    • Borel Hierarchy
    • Effective Borel Hierarchy
    • Decidable Subsets
    • The Theorem of Kuratowski-Tarski
    • Extension Theorem for Computable Functions
    • Wadge Reducibility in the Borel Hierarchy
    • Completeness Theorem for the Borel Hierarchy
  9. Effective Borel Measurability
    • Effective Borel Measurability
    • Weihrauch Reducibility
    • A Complete Map
    • Translating Enumerations into Characteristic Functions
    • Completeness of the Limit Map
    • Limit Computable Functions
  10. Computability With Respect to Representations
    • Representations
    • Computability With Respect To Representations
    • Reducibility of Representations
    • Representations of Product and Function Spaces
    • Transposition Theorem
    • Evaluation Theorem
    • Representations of Reals by Base Expansions
    • Multiplication by 3 with the Decimal Representation
  11. Computable Real Number Functions
    • Cauchy Representation
    • Computable Real Number Functions
    • Computable Real Numbers
    • Characterisation of Computable Real Numbers
    • Left Computable and Non-computable Real Numbers
    • Other Classes of Computable Reals
    • The Lattice of Real Number Representations
    • Admissible Representations
    • Theorem of Kreitz-Weihrauch and Schröder
    • Continuity of Computable Real Functions
  12. Computable Subsets of Euclidean Space
    • Computably and Decidable Subsets
    • General Undecidability of Comparisons of Reals
    • Plottable Images
    • Characterizations and Closure Properties
    • Computability of the Mandelbrot Set
  13. Computable Metric Spaces
    • Computable Metric Spaces
    • Hyper and Function Spaces
    • The Computable Intermediate Value Theorem
  14. Computable Theorems

Slides

The course slides simultaneously serve as lecture notes.

Tutorial Sheets

Here are the tutorial sheets with home work that has to be handed in:

References

The following text books are not prescribed to the course but recommended for further reading:

History

Here are some links to biographies of some famous mathematicians (at Mathematics Archive St Andrews): An here is a link (offered by James T. Smith, San Francisco): including the corresponding MP3 file.


© 2008-2011 Vasco Brattka