- 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.
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.
- is the union of the three sets
- is the intersection of the three sets r.e.? decidable?
- is the complement to the union of the three sets
- is the complement to the intersection of the
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,
second letter is equal to the last-but-one letter, etc.
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
- Is it a statement about the physical
8. To solve an equation p * u2
− q /
= r with an unknown u, we multiply both sides by
and introduce a new variable v = u2
reduces our original problem to the problem of solving an
appropriate quadratic equation a
* 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',
- 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
example when an algorithm is practically feasible, but not
feasible according to the formal definition.
must be different from the examples that we had in class.
- what is P,
- what is NP, and
- what is