## Theory of Computations, Test 2 for the courseCS 5315, Spring 2016

Name: _____________________________________________________

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

• is their union r.e.? is it decidable?
• is their intersection r.e.? decidable?
• is complement to A r.e.? decidable?
• is complement to B 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 A and B are r.e., and number 7 belongs to both sets. Suppose that:
• the algorithm for generating elements of set A produces number 7 at moment 2, and
• the algorithm that generates all the elements of the set B produces number 7 at moment 3.
Two questions:
• at what moment of time will an algorithm for generating all the elements of the intersection A ∩ B generate number 7?
• at what moment of time will an algorithm for generating all the elements of the union A ∪ B generate number 7?

4. Prove that a power-checker is not possible. To be more precise, prove that no algorithm is possible that, given a program p, checks whether this program always computes ab.

5-6. Write down the rules of a Turing machine that transforms a positive binary number into the corresponding negative number (e.g., 3 into −3). Specifically, the negative number should be represented in the 2's complement form. To obtain this form, we need to perform two steps:
• first, we change each 0 to 1 and each 1 to 0 (in the above example, 310 = 0112 is changed to 100);
• after that, we add 1 to the lowest bit (in the above example, 100 is replaced with 100 + 1 = 101).
It is therefore natural to design your Turing machine as follows:
• Write down the rules for two Turing machines that perform each of the two steps (not that in class, we have already designed a Turing machine for the second step).
• Use a general algorithm for composition to design the desired sign-inverting Turing machine.
Trace your newly designed sign-inverting Turing machine on the example of 3 (# 1 1 0 # # ...), you should get −3 (# 1 0 1 # # ...).

On this example, explain why in the definition of computation by Turing machine, we need to always "rewind", i.e., to bring the head back to the leftmost position.

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 a * u6 + b * u3 + c = 0 with an unknown u, we reduce it to a quadratic equation a * v2 + b * v + c = 0. Once we know v, we can compute u as the cubic root of v. Describe, for this reduction:
• what is C(x, 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,
• what is NP-hard, and
• what is NP-complete.