Test 2 for the course

CS 5315/6315, Spring 2017

Name: _____________________________________________________

*General comments:*

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

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?

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.

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 * u^{2} − q /
u^{2} = r with an unknown u, we multiply both sides by
u^{2} and introduce a new variable v = u^{2}. This
reduces our original problem to the problem of solving an
appropriate quadratic equation a
* v^{2} + 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 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, and
- what is NP-hard.