1-2. Let A be decidable and B 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 their union
r.e.? is it decidable?
- is their intersection r.e.? decidable?
- is complement to A r.e.? decidable?
- is complement to B
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
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?
Explain your answers.
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
It is therefore natural to design your Turing machine
- 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
- Is it a statement about the physical
8. To solve an equation a * u6
+ b * u3
= 0 with an unknown u, we reduce it to a quadratic equation a *
* 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
- 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,
- what is
- what is NP-complete.