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

Name: __________________________________________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place your name on each extra page.
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?