Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах заслуживает титул универсальной невычислимой функции... в некотором смысле слова(нетривиальном) это такая самая сильная невычислимость которая может существовать":http://youtu.be/nnZPqnwoD64?t=15m39s).
What is the exact wording of this statement?
upd: my translate of dialog on this video:
designations and definitions:
Let $u$ - is partial recursive function between $\mathbb{Z}_+$ and $X$, where $X$ is countable set.
$K_u(x) = min \{ m \in \mathbb{Z}_+ | u(m) = x\}$ or infinity
Statement: $\exists u ($optimal Kolmogorov numeration$): \forall v($function as$ u) \exists c(u, v) > 0 \forall x \in X: K_u(x) \le K_v(x)$
Kolmogorov's order$(u) \mathbb{Z}_+ \to X$ - in order of order Lower_to_higher
Dialog:
Misha Verbitsky: Is $u$ bijection?
Yury Manin: No, and it is focus and big trap. $u$ is not define on many $n$, many
Misha Verbitsky: And no for any $m$ too?
Yury Manin: It get all $x$.
Michael Tsfasman: No, because sometimes
Yury Manin: Optimal, optimal get all $x$. Not all $m$ are programs only some. And its non-computable... Furthermore it (in many interesting ways) deserves the title of the Universal noncomputable function.
Somebody: Complexity?
Yury Manin: Complexity and Kolmogorov's order too.
Somebody: Order? It is order of increasing complexity?
Yury Manin: Order of increasing complexity. They are non-computable. In a manner (nontrivial) it is the strongest noncomputable. If you have oracle that give you things in Kolmogorov's order then very mach things became computable (I'll show it for codes). I wrote somewhere that civilization is such oracle, that we do produce scientific knowledge in order of increasing its Kolmogorov complexity...