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

Aus VoWi
Zur Navigation springen Zur Suche springen

Daten[Bearbeiten | Quelltext bearbeiten]

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
Sprache English
Links tiss:185203
Masterstudium Logic and Computation Wahlmodul Logic, Mathematics, and Theoretical Computer Science
Masterstudium Software Engineering & Internet Computing

Inhalt[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

Vortrag[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

noch offen

Zeitaufwand[Bearbeiten | Quelltext bearbeiten]

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

Unterlagen[Bearbeiten | Quelltext bearbeiten]

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

Tipps[Bearbeiten | Quelltext bearbeiten]

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

Verbesserungsvorschläge / Kritik[Bearbeiten | Quelltext bearbeiten]

noch offen