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