[43] A universal Turing machine U is a standard Turing machine, or standard machine for short, if for every other Turing machine V there is a polynomial time function f such that f(p) ≤ l(p) + O(1)

and V (p) = U(f(p)) (when defined).

(a) For every standard machine U there exists a constant c and a computable function which for every string x produces l(x)2 strings containing a program p for x such that l(p) ≤ C(x) + c.

(b) Show that the constant c must depend on U.

(c) For every standard machine U there exists a polynomial-time computable function which for every string x produces poly(l(x)) strings containing a program for x of length C(x) + O(log l(x)).

(d) Given a string x, for every c > 0, for every optimal Turing machine U, for every computable function f which produces a set of strings containing a program p for x with l(p) ≤ C(x) + c holds d(f(x)) = Ω(l(x)2/c2)

for infinitely many x (the constant hidden in the Ω notation depends on f and U).

Comments. Source: [B. Bauwens, A. Makhlin, N.K. Vereshchagin, and M. Zimand, Comput. Complexity, 27:1(2018), 31–61]. Hint: use graphs that allow online matching, unbalanced bipartite graphs. Item

(c) was improved in [J. Teutsch, Comput. Complexity, 23:4(2014), 565–583] by replacing O(log l(x)) by O(1), and in [M. Zimand, Proc. 10th Conf.

Computability Europe, (2014), 403–408] by reducing poly(l(x)) strings to O(l(x)6+) strings.