2. Prove that the halting problem is not algorithmically
solvable.
3. In the proof that the halting problem is not algorithmically
solvable, we use a diagonal function
f(n) which was defined as
follows:
- f(n) = jn(n) + 1 if n is a valid code
of a Java program and jn halts on n;
- f(n) = 0
otherwise.
Write down the first 4 values f(0), f(1), f(2),
and f(3) of the diagonal function f(n) for the following case:
- j0(n) = 3;
- j1(n) = n;
- 2
is not a valid numerical code of a program; and
-
j3(n) = n2.
4. Not all algorithms are feasible, but, unfortunately, we do not
have a perfect definition is feasibility. Give two examples:
- an example of an algorithm which is feasible according to
the current definition but not practically feasible, and
- an
example of an algorithm which is practically feasible but not
feasible according to the current definition.
5. Briefly describe what is P, what is NP, and what is NP-hard.
Give an example of an NP-hard problem. What do we gain and what do
we lose when we prove that some problem is NP-hard?