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

## Daten[edit | edit source]

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

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

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

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

## Vortrag[edit | edit source]

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

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

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

noch offen

## Zeitaufwand[edit | edit source]

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

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

## Tipps[edit | edit source]

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

## Verbesserungsvorschläge / Kritik[edit | edit source]

noch offen