Let H(n) be the length of the shortest computer program which solves the halting problem for programs of length <=n. What is known about the growth of H(n)?
The paradox "least number larger than all numbers defined by programs of length <= n" gives the bound H(n) > n. Can we get a better bound? An upper bound?