La complejidad de Kolmogorov es el más fuerte noncomputable función

Question

Yury I. Manin dice que la complejidad de Kolmogorov (en algún sentido no trivial) es el más fuerte noncomputable función ("Колмогоровская сложность... невычислима... она во многих интересных смыслах заслуживает титул универсальной невычислимой функции... в некотором смысле слова(нетривиальном) это такая самая сильная невычислимость которая может существовать":http://youtu.be/nnZPqnwoD64?t=15m39s).

¿Cuál es el texto exacto de esta declaración?

upd: mi traducción de un diálogo sobre este vídeo:

las designaciones y definiciones:

Deje $u$ - es parcial función recursiva entre el $\mathbb{Z}_+$ e $X$ donde $X$ es contable establecido.

$K_u(x) = min \{ m \in \mathbb{Z}_+ | u(m) = x\}$ o el infinito

Instrucción: $\exists u ($óptimo de Kolmogorov numeración$): \forall v($función como$ u) \exists c(u, v) > 0 \forall x \in X: K_u(x) \le K_v(x)$

Prueba de Kolmogorov orden de$(u) \mathbb{Z}_+ \to X$ - en la orden de pedido Lower_to_higher

Diálogo:

Misha Verbitsky: Es $u$ bijection?

Yuri Manin: No, y es el enfoque y la gran trampa. $u$ no es definir en muchos $n$, muchos

Misha Verbitsky: Y no por cualquier $m$ también?

Yuri Manin: consigue todos los $x$.

Michael Tsfasman: No, porque a veces

Yuri Manin: Óptimo óptimo para obtener todos los $x$. No todos los $m$ son programas sólo algunos. Y su no-computable... Además (en muchas maneras interesantes) merece el título de el Universal noncomputable función.

Alguien: La Complejidad?

Yuri Manin: la Complejidad de Kolmogorov del pedido demasiado.

Alguien: Orden? Es el orden de complejidad creciente?

Yuri Manin: Orden de complejidad creciente. Ellos no son computables. De una manera (no trivial) es la más fuerte noncomputable. Si usted tiene oracle que te dan las cosas en el test de Kolmogorov orden del entonces muy mach cosas se computable (te voy a mostrar es para los códigos). Me escribió en alguna parte que la civilización es de oracle, que nos producen los conocimientos científicos con el fin de aumentar su complejidad de Kolmogorov...

Answer 1

Respuesta de Yury I. Manin:

1) entiendo (semi)funciones computables como (parcialmente) funciones recursivas; así, los argumentos y los valores son desde el inicio de números naturales. Pero pueden ser también los números racionales, finito de palabras en un alfabeto finito y mucho más: cf. Capítulo V de [1], y también las páginas 285-296 allí.

2) La exponencial de la complejidad de Kolmogorov de un número (o de un semicomputable función) es la primera vez que aparece en un óptimo universal programa: vea las páginas 223-234 de [1]. Es "casi", pero no es computable: es el infimum de una secuencia de funciones computables. En este sentido KC se encuentra "al límite" entre computable y uncomputable.

3) Si un oráculo órdenes de todos los números naturales en la orden de creciente complejidad de Kolmogorov, a continuación, todos los semi-funciones computables a ser de no más de crecimiento lineal (por supuesto, si sus valores son también de manera ordenada). Así KC "simplifica" todos semicomputable funciones de manera simultánea. En este sentido, probablemente, debería haber dicho que KC tiene "menos complejo uncomputability", en lugar de "lo más complejo", lo siento.

4) En [2], se pueden encontrar aplicaciones de este concepto que se bastante inesperado para mí, y que yo he entendido hace bastante poco.

Mejor, Yu. Manin

REFERENCIAS

[1] Yu.M. Un Curso de Lógica Matemática para los Matemáticos. Segunda Edición (con la colaboración de B.~Zilber). Springer Verlag, 2010. xvii+384 pp.

[2] Yu. M. Complejidad vs Energía: Teoría de la computación y física teórica. {\it (Hablar en la conferencia satélite de ECM DE 2012, `QQQ el Álgebra, la Geometría, la Información", Tallin, 9 de julio--12, 2012).} Preprint arXiv:1302.6695

Answer 2

No estoy seguro de a qué te refieres por redacción exacta. Supongo que, a entender de idioma ruso. Así que, sólo me escribió todo lo que dijo de 15:40 a 17:20. Si usted necesita una traducción al inglés, acaba de decir, es fácil. Si quieres un matemático riguroso formulario de la mencionada Manin de la frase, yo podría intentar, por supuesto. (Sin embargo, no me gustaría interpretar el famoso Yuri Manin.)

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

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

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

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

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

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

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

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

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

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

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

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

Answer 3

.

• 'Ahora, una de Turing-grado es el conjunto de todos los problemas que son Turing-equivalente a un determinado problema. ¿Cuáles son algunos ejemplos de Turing-grados? Bien, ya hemos visto dos ejemplos: (1) el conjunto de computable problemas, y (2) el conjunto de problemas que son Turing-equivalente a detener problema^[1]. Diciendo que estos Turing-grados no son iguales, es sólo otra manera de decir que la detención problema no es solucionable.

• Hay Turing-grados por encima de estos dos? En otras palabras, ¿hay algún problema aún más difícil que la detención problema? Bien, considere el siguiente "super detener problema": dada una máquina de Turing con una de oracle para detener el problema, decidir si se detiene! Podemos demostrar que esta super detener problema es irresoluble, incluso teniendo en cuenta un oráculo para el ordinario detener problema? Sí, se puede! Simplemente tomamos Turing original de la prueba de que la detención problema es irresoluble, y "cambio de todo por un nivel" da todas las máquinas de oracle para detener el problema. Todo en la prueba pasa a través de, como antes, un hecho que nos expresa diciendo que la prueba "relativiza."'----Conferencia a cargo de Scott Aaronson

^{[1]Encontrar el Kolmgorov complejidad es Turing equivalente a decidir el cese del problema.(Para saber cómo,mira a los comentarios de @usul por debajo de este post aquí).}

Así vemos que hay una jerarquía aritmética de los oráculos ( e incluso los intermedios) y, como tal, no es más fuerte de Oracle o sus equivalentes no computable de la función (por ejemplo, este no computable función puede ser tomado como Chaitin s $\omega$ para los de su clase.)

En mi opinión, todos los problemas que son "naturales" y de hecho han surgido en la práctica ; la más afín a la NP duro, que puede ser resuelto por la detención de oracle.. por lo tanto, tal vez la complejidad de Kolmogorov en el más fuerte noncomputable función que se produce en * práctica*.

^{Vamos a tener para calificar a la anterior, ya que es una declaración subjetiva por ejemplo, la función AreThereInfinitelyManyTwinPrimes() no puede ser calculado por la detención de oracle y, por tanto, más en computables de la complejidad de Kolmogorov K() aquí en la MO}

Answer 4

Una de las posibles interpretaciones: tener un oráculo que dice que los valores exactos de la prueba de Kolmogorov complejidad de cualquier cadena de caracteres, se puede usar para resolver detener problema (computably, con oracle llamadas). Pero, por supuesto, hay algunos que no computable funciones que son "más no computable" (no puede ser computable, con tal de oracle); ninguna función puede ser "el máximo noncomputable" en este sentido...