185.203 Computability Theory
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2020S, VU, 2.0h, 3.0EC, to be held in blocked form
TUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Learning outcomes

After successful completion of the course, students are able to independently prove various advanced  computability-theoretic statements and facts, and to apply results presented in the lectures to achieve this.

Subject of course

Introduction to computability theory: unsolvable problems, models of computations (Turing machines, register machines, recursive functions, lambda calculus), Church-Turing thesis, numbering of computable functions, numbering programs, the diagonal method, the s-m-n theorem, universal programs, Kleene's theorem, recursive and recursively enumerable sets, Rice's theorem. The LOOP-hierarchy and enumerations of subrecursive classes. Didactic procedure: During the course two sheets of exercises will be distributed which have to be solved by the students on their own.

Teaching methods

Lecture

Mode of examination

Written and oral

Additional information

ECTS breakdown

24 h: 5 lectures

16 h: solving 2 sheets of ex. a 7 ex.

4 h: typing solutions in LaTeX

30 h: preparation for final examination

1 h: final examination

-----------------------------------------

75 h = 3 ECTS

 

 

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue09:15 - 12:0003.03.2020 - 28.04.2020 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Computability Theory - Single appointments
DayDateTimeLocationDescription
Tue03.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue10.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue17.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue24.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue31.03.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue21.04.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Tue28.04.202009:15 - 12:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Computability theory, will be held in blocks
Course is held blocked

Examination modalities

2 sets of exercises and an oral exam

Course registration

Not necessary

Curricula

Literature

P. Odifreddi, Classical Recursion Theory, Studies in Logic, North Holland 1989

Previous knowledge

Some basic knowledge in mathematical logic and theoretical computer science is required; in particular knowledge in first-order predicate logic is of major importance.

Language

English