Theory of Computations,
Test 2 for the course
CS 5315/6315, Spring 2017

Name: _____________________________________________________

General comments:

Good luck!

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

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.