Turing machines and computable functions. Universal machine. Undecidable problems and non-computable functions.

Basic theorems and notions: s-m-n and u-t-m theorems, recursion theorem, computable and computably enumerable sets and their properties, non-separable sets, Rice's theorem, Rice-Shapiro theorem.

Oracle computations, Turing reducibility and degrees.

If time permits: computable functionals, continuity of functionals, KLS theorem, computable real numbers, basic results in computable analysis.

# Computability theory

Prof. Dr. Andrej Bauer, Prof. Dr. Marko Petkovšek

J. E. Hopcroft, J. D. Ullman: Uvod v teorijo avtomatov, jezikov in izračunov, FER, Ljubljana, 1990.

P. Odifreddi: Classical Recursion Theory, North-Holland, 1989.

Knowledge of basic notions and results in computability theory.

Knowledge and understanding:

Understanding of the connections between computability notions, such as Turing machines, and basic mathematical notions, such as sets of numbers.

Application:

The subject matter provides a general theoretical foundation for computer science.

Reflection:

The influence of the notion of computability on foundations of mathematics.

Transferable skills:

Analytic and abstract thinking about the theoretical frontiers of computer science.

Lectures, exercises, homeworks, consultations

2 midterm exams instead of written exam, written exam

Oral exam

grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Andrej Bauer:

AWODEY, Steve, BAUER, Andrej. Propositions as [Types]. Journal of logic and computation, ISSN 0955-792X, 2004, vol. 14, no. 4, str. 447-471. [COBISS-SI-ID 13374809]

BAUER, Andrej. First steps in synthetic computability theory. V: Proceedings of the 21st Annual Conference on Mathematical Foundations of Programming Semantics (MFPS XXI), (Electronic notes in theoretical computer science, ISSN 1571-0661, Vol. 155). Amsterdam: Elsevier, 2006, str. 5-31. [COBISS-SI-ID 14631001]

BAUER, Andrej. A ralationship between equilogical spaces and Type Two Effectivity. Mathematical logic quarterly, ISSN 0942-5616, 2002, vol. 48, suppl. 1, str. 1-15. [COBISS-SI-ID 12033369]

Marko Petkovšek:

PETKOVŠEK, Marko. Ambiguous numbers are dense. American mathematical monthly, ISSN 0002-9890, 1990, let. 97, št. 5, str. 408-411. [COBISS-SI-ID 8040537]

PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337] xii + 212 str. (ISBN 1-56881-063-6).

PETKOVŠEK, Marko. Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2002, vol. 244, no. 1-3, str. 375-388. [COBISS-SI-ID 11414873]