CS 3350 Automata, Computability, and Formal Languages
Spring 2017, Test 3

Name: __________________________________________________________

General comments:

Good luck!

1. Formulate Church-Turing thesis. Is it a mathematical theorem? Is it a statement about the physical world?

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?