ИСТИНА

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list guaranteed to contain a $O(\log |x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.