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

Daten

Diese LVA wird nicht mehr von dieser Person angeboten, ist ausgelaufen, oder läuft aus und befindet sich daher nur noch zu historischen Zwecken im VoWi.

Vortragende	Prof. Fokina
ECTS	3
Sprache	English
Links	tiss:185203

Zuordnungen

Masterstudium Logic and Computation
Masterstudium Software Engineering & Internet Computing

Inhalt

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.

Ablauf

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

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

Vortrag

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.

Übungen

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

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

noch offen

Zeitaufwand

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

Unterlagen

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

Tipps

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

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Neues Material hinzufügen

2

• 2021 CT Ex1.pdf (details)
• 2021 CT Ex2.pdf (details)