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) = j_{n}(n) + 1 if n is a valid code
of a Java program and j_{n} 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:
 j_{0}(n) = 3;
 j_{1}(n) = n;
 2
is not a valid numerical code of a program; and

j_{3}(n) = n^{2}.
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 NPhard.
Give an example of an NPhard problem. What do we gain and what do
we lose when we prove that some problem is NPhard?