# Kolmogorov complexity is the strongest noncomputable function

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...

• If you are looking for someone who knows Russian to give greater detail or rigor to Manin's quote, it would probably help if you gave a link to your source, plus whatever context you know. Other than that, perhaps your best English translation of your excerpt. There may be someone who can answer who knows little Russian. – Will Jagy Sep 22 '13 at 19:43
• @Will Jagy, I made ​​a reference (it was lecture about this:arxiv.org/abs/1107.4246) but I don't think that context is important: it was only remark. – Alexey Milovanov Sep 22 '13 at 20:14
• Alexey, it is very nice to have the Manin arxiv reference available in case someone is good with this material but needs to see something in English. Thanks for providing some background. Maybe someone will be able to give you a substantial answer. – Will Jagy Sep 22 '13 at 20:26

## 4 Answers

Answer from Yury I. Manin:

1) I understand (semi)computable functions as (partially) recursive functions; so arguments and values are from the start natural numbers. But they can be also rational numbers, finite words in a finite alphabet and a lot more: cf. Chapter V of , and also pages 285-296 there.

2) The exponential Kolmogorov complexity of a number (or of a semicomputable function) is the first time that it appears in an optimal universal program: see pp. 223-234 of . It is "almost", but not quite computable: it is the infimum of a sequence of computable functions. In this sense KC lies "at the boundary" between computable and uncomputable.

3) If an oracle orders all natural numbers in the order of growing Kolmogorov complexity, then all semi-computable functions become of no more than linear growth (of course, if their values are also so ordered). So KC "simplifies" all semicomputable functions simultaneously. In this sense, probably, I should have said that KC has "the least complex uncomputability", rather than "the most complex", sorry.

4) In , one can find applications of this notion that were quite unexpected for me, and that I have understood pretty recently.

Best, Yu. Manin

REFERENCES

 Yu.M. A Course in Mathematical Logic for Mathematicians. Second Edition (with collaboration by B.~Zilber). Springer Verlag, 2010. xvii+384 pp.

 Yu. M. Complexity vs Energy: Theory of computation and theoretical physics. {\it (Talk at the satellite conference to ECM 2012, QQQ Algebra, Geometry, Information", Tallinn, July 9--12, 2012).} Preprint arXiv:1302.6695

• My guess, you will need to award the bounty to Yu.Manin. – Sasha Anan'in Sep 27 '13 at 20:21

I am not sure what do you mean by exact wording. I guess, you understand Russian language. So, I just wrote down everything said from 15:40 to 17:20. If you need a translation into English, just say, it is easy. If you want a rigorous mathematical form of the mentioned Manin's phrase, I could try, of course. (However, I would not like to interpret the famous Yuri Manin.)

Миша Вербицкий: Простите, $u$ это биекция или нет?

Юрий Манин: Что?

Миша Вербицкий: $u$ это биекция?

Юрий Манин: Нет! Вот в этом и фокус. В этом большая ловушка. Сама $u$, которая оптимальна по Колмогорову, не определена на массе значений $m$, на массе ...

Миша Вербицкий: И не на всех $x$, это тоже?

Юрий Манин: Она производит все $x$'ы. Производит она все $x$'ы.

Кто-то: Нет, не все, потому что иногда ... [неразборчиво]

Юрий Манин: Оптимальная, оптимальная производит все $x$'ы, все $x$'ы. Не все $m$ являются программами, только некоторые ... Вот. И более того, она не вычислима, сама она не является частично рекурсивной, не является вычислимой, не является ничем. Она, во многих интересных смыслах, заслуживает титул ... ааа, значит, ааа ... универсальной ... ааа ... невычислимой функции ...

Кто-то: Сложность, сложность сама? Сама сложность. Сложность?

Юрий Манин: Да, сама сложность. Ну, и Колмогоровские порядки тоже.

Кто-то: Порядки --- это порядки возрастания сложности?

Юрий Манин: Порядки возрастания сложности. И то, и другое не является вычислимым. Но в некоем смысле слова (нетривиальном), это такая самая сильная невычислимость, какая может существовать. Если у Вас есть оракул, который производит Вам вещи в порядке Колмогоровской сложности, то почти все вещи (очень многие вещи) становятся вычислимыми. (Это я покажу для этого самого хозяйства.) И я где-то написал, что вообще цивилизация --- это такой оракул, что мы вообще производим научное знание в порядке возрастания его Колмогоровской сложности, не формализовывая --- это существенно ... Вот.

• Sasha Anan'in, вот я и собираюсь понять в каком "нетривиальном" смысле это "самая сильная невычислимость, какая может существовать")) – Alexey Milovanov Sep 25 '13 at 18:03
• Ну или хотя бы примеры тех многих вещей, которые можно вычислить если есть оракул вычисляющий Колмогоровскую сложность. Кстати первый "Кто-то" - это М. А. Цфасман – Alexey Milovanov Sep 25 '13 at 18:07
• I don't know whether the OP reads Russian fluently, but I don't and I would love to see a translation! – François G. Dorais Sep 25 '13 at 23:10

.

• 'Now, a Turing-degree is the set of all problems that are Turing-equivalent to a given problem. What are some examples of Turing-degrees? Well, we've already seen two examples: (1) the set of computable problems, and (2) the set of problems that are Turing-equivalent to the halting problem. Saying that these Turing-degrees aren't equal is just another way of saying that the halting problem isn't solvable.

• Are there any Turing-degrees above these two? In other words, is there any problem even harder than the halting problem? Well, consider the following "super halting problem": given a Turing machine with an oracle for the halting problem, decide if it halts! Can we prove that this super halting problem is unsolvable, even given an oracle for the ordinary halting problem? Yes, we can! We simply take Turing's original proof that the halting problem is unsolvable, and "shift everything up a level" by giving all the machines an oracle for the halting problem. Everything in the proof goes through as before, a fact we express by saying that the proof "relativizes."'----Lecture by Scott Aaronson

Finding the Kolmgorov complexity is Turing equivalent to deciding the halting problem.(For how,look at the comments by @usul below this post here.)

So we see there is an arithmetical hierarchy of oracles ( and even intermediate ones) and as such there is no strongest Oracle or its equivalent non computable function (as an example this non computable function can be taken as Chaitin's $\omega$ for its class.)

In my opinion ; all problems which are "natural" and have actually arisen in practice ; the hardest akin to NP hard; can be solved by the halting oracle.. hence perhaps Kolmogorov complexity in the strongest noncomputable function which occurs in * practice*.

We will have to qualify the above as it is a subjective statement eg the function AreThereInfinitelyManyTwinPrimes() can not be calculated by the Halting oracle and hence more in-computable than Kolmogorov complexity K() here on MO

One of the possible interpretation: having an oracle that tells the exact values of Kolmogorov complexity of any given string, one can use it to solve halting problem (computably, with oracle calls). But, of course, there are some non-computable functions that are "more non-computable" (cannot be computable with such an oracle); no function can be "maximally noncomputable" in this sense...

• It is interesting to know some examples of noncomputable functions that can be compute if we have oracle that compute Kolmogorov complexity – Alexey Milovanov Sep 25 '13 at 18:14
• @Alexey, I think if we have an oracle to solve the halting problem, we can compute Kolmogorov complexity: On input $s$, let $m$ be the length of $s$ plus the size of the TM that copies input to output (this is an upper bound on $KC(s)$); now iterate over the finitely many pairs (TM, input) with total length less than $m$, first checking if this TM halts on this input, and if so, running it to see if it produces $s$. Output the length of the shortest pair that produces $s$, or output $m$ if none do. – usul Sep 26 '13 at 2:12
• Assuming that is correct, KC seems to be no "harder" than halting, which makes Manin's comment quite mystifying to me (but I don't know Russian, so I don't know the context of the quote). – usul Sep 26 '13 at 2:14
• Yes, the Turing degree of a Kolmogorov complexity function $K$, for an arbitrary universal prefix-free code, is the same Turing degree as the halting problem. Similarly, each Chaitin-type $\Omega$ number is computable from the halting problem $0'$. – Carl Mummert Oct 2 '13 at 10:44