Basic Theoretical Questions in Computablity Tests

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