1. (February 14)
- What is a primitive recursive function?
- What is Kolmogorov complexity?
- Prove that addition is primitive recursive
- Estimate the Kolmogorov complexity of a string 0 ... 0
2. (February 16)
- What is a decidable set?
- What is a recursively enumerable set?
- Prove that the set of all the people born in 2012 is
3. (March 2)
3. (March 23)
- Prove that if the sets A and B are r.e., then their
intersection is also r.e.
- Prove that an n4-checker is not possible.
- Is every r.e. set decidable?
- Prove, from scratch, that the function a > b is
primitive-recursive and mu-recursive.
- If A is r.e. and B is decidable, is their union r.e.?
decidable? If yes, prove it, if no, give a