This page lists some typical theoretical questions. The ones shown below are the most crucial ones: failing to answer even one of these can severely impact the student's chances to pass the exam. The exhaustive list of theoretical questions can be found browsing my notes: all the exam-relevant topics are marked as such with red margin notes.

- Construct a non-computable function, and prove it is such.
- Define the set of recursive functions.
- Define the set of recursive sets.
- Prove that the Kleene's set K is not recursive.
- Define the set of recursively enumerable sets.
- Prove that the Kleene's set K is recursively enumerable.
- Prove that the complement of Kleene's set K is not recursively enumerable.

Other less crucial questions which are still important are shown below:

- State theorem/lemma X (anything carrying a red mark in my notes) and apply it to one example.
- Define X (anything carrying a red mark in my notes) and provide an example of ... such that definition X holds / does not hold.
- Prove Rice's theorem (for the lambda calculus / in the general case).
- Prove Rice-Shapiro theorem.
- Prove the second recursion theorem (for the lambda calculus / in the general case).
- Prove the s-m-n theorem.
- Prove the padding lemma.
- Prove that recursive sets are closed under union, intersection, complement.
- Prove that r.e. sets are closed under union and intersection, but not complement.
- Prove that recursive sets are also r.e. .
- Prove that a set is recursive iff it and its complement are r.e. .
- Prove that being r.e. is equivalent to ... (four different characterizations are given in the notes).

Repetita iuvant: the above list is not exhaustive. Refer to my notes: red margins mark all the theoretical questions.

Home - Teaching - Computability

Roberto Zunino, 2011