Test 2 for the course

CS 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?

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.

- 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 a^{b}.

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, 3
_{10}= 011_{2}is changed to 100); - after that, we add 1 to the lowest bit (in the above example, 100 is replaced with 100 + 1 = 101).

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

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 * u^{6} + b * u^{3} + c
= 0 with an unknown u, we reduce it to a quadratic equation a *
v^{2} + 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 U
_{1}, - what is
U
_{2}, and - what is U
_{3}.

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.

10. Define:

- what is P,
- what is NP,
- what is NP-hard, and
- what is NP-complete.