All preliminaries that I think are relevant:
- We focus on domains that are comprised of strings built from {0, 1}.
- A set S of strings is prefix-free if no string in S is a proper prefix of a string in S.
- A prefix-free program, P, is a program whose domain is prefix-free.
- A theorem is given, where we can construct a prefix-free program U such that every prefix-free program C there exists a constant, $c = c_{U,C}$, such that for each input string x, there exists an input z where $|z| \leq |x|+c$ such that $U(z) = C(x)$.
- Say we have a prefix-free program M, we define program-size complexity $H_M(x)$ to be size of the smallest input for M to compute $x$ or $H_M(x) = inf\{|p|\, s.t \, M(p) = x\}$.
The "challenge" question in my lecture presented; "One can effectively construct a prefix-free program U such that for every prefix-free program C there effectively exists a constant $c=c_{U,C}$ such that for each input string x we have $H_U(x)\leq H_C(x)+c$.
Let $C_i$ be the computable enumeration of all prefix-free programs. Construct $U$ by $U(1^i0\alpha) = C_i(\alpha)$.
Then given a C, we have $e_{U,C} = 1^i0$ (intuitively I think of this as the encoding of C as @aschepler made me realise). It holds for $x\in dom(U) \cap dom(C)$ that $H_U(x) \leq |1^i0\pi^*|$ where $\pi^*$ is the smallest $\pi$ such that $C(\pi) = x$. Then $|1^i0\pi^*| = |e| + |\pi^*| = |e| + H_C(x).$ There $H_U(x) \leq H_C(x) + c$ as required ($c$ as $|e|$).