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

## Daten[edit]

Lecturers | Prof. Fokina |
---|---|

ECTS | 3 |

When | summer semester |

Language | English |

Links | tiss:185203 |

Master Logic and Computation | Wahlmodul Logic, Mathematics, and Theoretical Computer Science |

Master Software Engineering & Internet Computing |

## Inhalt[edit]

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[edit]

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.

## Vortrag[edit]

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[edit]

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.

- 2 definitions about reducibility and one related proof from the script
- 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

## Zeitaufwand[edit]

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

## Unterlagen[edit]

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

## Tipps[edit]

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

## Verbesserungsvorschläge / Kritik[edit]

noch offen