185.203 Computability Theory This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_1y",{id:"j_id_1y",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_20",{id:"j_id_20",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});});

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

Properties

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

Aim of course

The aim is to provide a basis for the understanding of some of the most fundamental concepts of theoretical computer science: the concept of an algorithm and models of algorithms, mechanizability, undecidability, and principal limits of mechanization of problems.

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.

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

Course dates

DayTimeDateLocationDescription
Tue14:00 - 18:0005.03.2019 - 02.04.2019 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Computability Theory - Single appointments
DayDateTimeLocationDescription
Tue05.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Tue12.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Tue19.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Tue26.03.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Tue02.04.201914:00 - 18:00 Besprechungsraum des Instituts für Diskrete Mathematik und Geometrie, E104, Freihaus, 5. Stock, grüner Bereich, DA05C22Theorie der Berechenbarkeit; wird geblockt abgehalten
Course is held blocked

Not necessary

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.

English