Homework 2
Distributed on Monday, September 8.
Please bring your solutions to the lecture on Wednesday, September 17.
Exercise #2:
 Explain in words the problem 0'''.
 Prove that H^{H} is semidecidable
by BF^{H}
 but not decidable by BF^{H}.
Exercise #3:
A universal BF program U
receives as input an arbitrary BF program P
and some string x; then simulates P on x.
(Such universal programs have actually been written
here,
here,
and here;
but it may be rather cumbersome to backwardengineer their operation.)

Sketch (but do not implement)
an extended universal program which
receives as input a 3tuple (P,T,x),
where T denotes (in binary)
the number of steps of P to simulate on x.
Explain the memory layout during the simulation.
 Analyze the asymptotic running time
of your program in terms of
T and (the length of) P, x.
Can you achieve
O(T·(T+P^{2}+x+log
T)) ?
How about O(T·(P^{2}+x+log
T)) ?