3350 Automata, Computability, and Formal Languages
2017, Test 3
- you are allowed up to 5 pages of
- if you need extra pages, place your name
on each extra page.
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
3. In the proof that the halting problem is not algorithmically
solvable, we use a diagonal function
f(n) which was defined as
- f(n) = jn(n) + 1 if n is a valid code
of a Java program and jn halts on n;
- f(n) = 0
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;
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
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?