## Theory of Computations, Test 2 for the courseCS 5315/6315, Spring 2017

Name: _____________________________________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place your name on each extra page.
Good luck!

1-2. Let A be decidable, B be decidable, and C be r.e.

• is the union of the three sets r.e.? decidable?
• is the intersection of the three sets r.e.? decidable?
• is the complement to the union of the three sets r.e.? decidable?
• is the complement to the intersection of the three sets r.e.? decidable?
For each of these questions, either provide a proof, or provide a counterexample. In your proofs, you can use the results that we proved in class, without the need to reproduce the proofs of these auxiliary results.

3. Suppose that both the set A and its complement −A are r.e. Suppose that number 6 belongs to A, and the algorithm for generating elements of set A produces number 6 at moment 3. At what moment of time will the deciding algorithm (i.e., the algorithm for checking whether a given number belongs to A) inform us that 6 belongs to the set A? Explain your answer.

4. Prove that no algorithm is possible that, given a program p, checks whether this program always computes the value of the Ackermann function A(n), i.e., whether p(n) = A(n) for all n.

5-6. Write down the rules of a Turing machine that checks whether the word written on a tape is a palindrome, i.e., whether:
• the first letter is equal to the last one,
• the second letter is equal to the last-but-one letter, etc.
For simplicity, assume that the words only use letter 'a' and 'b'. Trace your newly designed sign-inverting Turing machine on the example of the word abba.

7. Write down the Church-Turing thesis.
• Is it a mathematical theorem?
• Is it a statement about the physical world?

8. To solve an equation p * u2 − q / u2 = r with an unknown u, we multiply both sides by u2 and introduce a new variable v = u2. This reduces our original problem to the problem of solving an appropriate quadratic equation a * v2 + b * v + c = 0. Once we know v, we can compute u as the square root of v. Describe, for this reduction:
• what is x, what is y, what is C(x, y),
• what is x', what is y', what is C'(x', y'),
• what is U1,
• what is U2, and
• what is U3.

9. Give a formal definition of feasibility. Give two examples:
• an example when an algorithm is feasible in the sense of the formal definition but not practically feasible, and
• an example when an algorithm is practically feasible, but not feasible according to the formal definition.
These examples must be different from the examples that we had in class.

10. Define:
• what is P,
• what is NP, and
• what is NP-hard.