Homework 2

Distributed on Monday, September 8.
Please bring your solutions to the lecture on Wednesday, September 17.

Exercise #2:

  1. Explain in words the problem 0'''.
  2. Prove that HH is semi-decidable by BFH
  3. but not decidable by BFH.

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 backward-engineer their operation.)
  1. 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.
  2. 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)) ?