Distributed on Monday, September 8.
Please bring your solutions to the lecture on Wednesday, September 17.
- Explain in words the problem 0'''.
- Prove that HH is semi-decidable
- but not decidable by BFH.
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
but it may be rather cumbersome to backward-engineer their operation.)
Sketch (but do not implement)
an extended universal program which
receives as input a 3-tuple (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
How about O(T·(|P|2+|x|+log