Basic Questions in Computablity Oral Tests

This page lists some questions whose answers should be well known by students taking the oral exam. Failing to answer even one of these severely impacts the student's chances to pass the exam. Further, knowing all the answers to these, and nothing else, does not guarantee 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 and are frequently asked.

• 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