TU Wien:Computability Theory VU (Fokina, San Mauro)

From VoWi
Jump to navigation Jump to search


Lecturers Prof. Fokina
When summer semester
Language English
Links tiss:185203
Master Logic and Computation Wahlmodul Logic, Mathematics, and Theoretical Computer Science
Master Software Engineering & Internet Computing


Equivalence of (Turing) machines and functions in terms of computability. Universal functions, S-m-n theorem, recursion theorem. Enumerability (computably enumerable) with creative & simple sets. Many-one and Turing reducibility.


2021S (Fokina): 4 lectures. Two exercise sheets. Oral exam at the end. Basically the course was in the first half of the semester because Advanced Mathematical Logic is in the second half and supposed to be the successor to Computability Theory.

Benötigte/Empfehlenswerte Vorkenntnisse[edit]

I did it without "Logic & Computability" before. Felt not so easy.


2021S: She asked really politely (and often) if there were any questions but hardly anyone asked some. She talked about the most important things and difficult proofs.


2021S: Two exercise sheets with a few weeks time for each. Grading was nice. I tried every exercise, but am certain that a couple of my proofs do not work. Got a 1 for it anyway.

Prüfung, Benotung[edit]

2021S: Oral exam directly with Prof. Fokina.

  1. 2 definitions about reducibility and one related proof from the script
  2. A (new) proof using definitions of c.e. (Not really similar to the exercises IMO)

There was no question about the exercise sheets in the exam. Grading was nice. With somewhat knowing the definitions (and talking about some related topics that came to my mind), not remembering the first proof and babbling my way through the second, I got a 3 for the exam.

Total grade consists of exercise sheets + exam (50% each I think. 1 for exercises + 3 for exam gave 2 in total).

Dauer der Zeugnisausstellung[edit]

noch offen


2021S: The course was not so easy for me. The difficulty felt comparable to the second=harder part of Discrete Mathematics for me.


Wikipedia and other resources contain some additional helpful (easier) explanations. For example, explanations for the T predicate or


You can find a few solutions in the internet easily. Some others were impossible to find for me.

Verbesserungsvorschläge / Kritik[edit]

noch offen


This page has no attachments yet but you can add some.