# 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.