Quizzes for the course

CS 5315, Spring 2011

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 (100 times)

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

3. (March 2)

- Prove that if the sets A and B are r.e., then their intersection is also r.e.
- Prove that an n
^{4}-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 counter-example.