¿Cuál es el programa más corto para el que se desconoce la parada?

Question

En resumen, mi pregunta es:

¿Cuál es el programa de ordenador más corto para el que no se sabe si el programa se detiene o no?

Por supuesto, esto depende del lenguaje de descripción; también tengo la siguiente pregunta vaga:

¿En qué medida depende esto del lenguaje de descripción?

Esta es mi motivación, que estoy seguro de que es conocida, pero creo que es una posibilidad especialmente llamativa para una aplicación a las matemáticas:

Dejemos que $P(n)$ sea una afirmación sobre los números naturales tal que exista una máquina de Turing $T$ que puede decidir si $P(n)$ es verdadero o falso. (Es decir, esta máquina de Turing se detiene en cada número natural $n$ imprimiendo "True" si $P(n)$ es verdadero y "Falso" en caso contrario). Entonces el menor $n$ tal que $P(n)$ es falsa tiene baja Complejidad de Kolmogorov ya que será impreso por un programa que comprueba $P(1)$ entonces $P(2)$ y así sucesivamente hasta llegar a $n$ con $P(n)$ falso, e imprime esto $n$ . Así, la complejidad de Kolmogorov del menor contraejemplo de $P$ está limitada por encima por $|T|+c$ para alguna constante (efectiva) $c$ .

Dejemos que $L$ sea la longitud del programa de ordenador más corto para el que no se conoce el problema de detención. Entonces, si $|T|+c < L$ podemos demostrar la afirmación $\forall n, P(n)$ simplemente ejecutando todos los programas de parada de longitud inferior o igual a $|T|+c$ y corriendo $T$ en su salida. Si $T$ da como resultado "True" para estos números finitos, entonces $P$ es cierto.

Por supuesto, el problema de Halting pone límites a la potencia de este método.

En esencia, esta pregunta se reduce a: ¿Cuál es la conjetura abierta más sucintamente enunciable?

EDIT: Por cierto, una implicación asombrosa del argumento que doy es que para demostrar cualquier teorema sobre los números naturales, basta con demostrarlo para un número finito de valores (aquellos con baja complejidad de Kolmogorov). Sin embargo, debido al problema de Halting, ¡es imposible saber qué valores! Si alguien conoce una referencia para este tipo de cosas también lo agradecería.

Answer 1

Existe una máquina de Turing de 5 estados y 2 símbolos para la que no se sabe si se detiene. Véase http://en.wikipedia.org/wiki/Busy_beaver .

Answer 2

Puede encontrar la entrada de mi blog "¿Son decidibles las pequeñas sentencias de la aritmética de Peano?" relevante. En resumen, John Langford y he investigado frases cortas de aritmética de Peano. Las enumeramos todas (en realidad, lo hicieron nuestros ordenadores portátiles) y eliminamos las que se podían reconocer como decidibles. Rápidamente resultó que las ecuaciones diofantinas eran difíciles de reconocer como decidibles. Entre ellas encontramos dos que daban a un teórico profesional de los números algo que masticar (todos los cuantificadores tienen un rango de $\mathbb{N}$ ): $$\exists a, b, c . \; a^2 - 2 = (a + b) b c$$ et $$\exists a, b, c . \; a^2 + a - 1 = (a + b) b c.$$

La frase más corta sin resolver que conozco es ( $S$ es la función sucesora) $$\forall a \exists b \forall c, d . \; (a+b)(a+b) \neq S(S( (S(S c)) \cdot (S(S d)))).$$ Dice (más o menos) que hay infinitos primos de la forma $x^2 - 2$ .

Lo que más me sorprendió fue que los cuantificadores mixtos eran más fáciles que las afirmaciones universales o existenciales directas. Parece que con muy pocos símbolos de sobra para la matriz, no se puede producir una frase interesante de cuantificadores mixtos.

Answer 3

En cuanto a para demostrar cualquier teorema sobre los números naturales, basta con demostrarlo para un número finito de valores ... imposible saber qué valores (donde el contexto explica que el teorema es una afirmación universalmente cuantificada $\forall n\,P(n)$ ): esto es trivial, y un valor es suficiente. A saber, definir $n_0$ de la siguiente manera: si la afirmación es falsa, que $n_0$ sea el contraejemplo más pequeño, de lo contrario dejemos que $n_0:=0$ . Entonces la afirmación es válida si y sólo si $P(n_0)$ .

Answer 4

Es muy posible que el Conjetura de Collatz proporciona una respuesta. Aplique esta función repetidamente. La conjetura es que este proceso llegará finalmente al número 1, independientemente del número entero positivo que se elija inicialmente.

No estoy seguro de cuántas líneas de código serían. Probablemente 2 en Haskell.

Answer 5

A los lectores les interesará saber que iteraciones congruentes similares al problema de Collatz 3n+1 fueron descubiertas "en la naturaleza" mientras se intentaba comprender el comportamiento de varias máquinas candidatas a castor ocupado. Dado que John Conway ha demostrado que decidir la terminación de ciertas clases de tales iteraciones congruentes es indecidible, puede ser que el límite de la indecidibilidad ya se encuentre en uno de estos problemas abiertos de iteración congruente del castor ocupado. Para mucha más discusión y referencias, véase mi antiguo post en sci.math, 13 Feb 1996, ¿la detención es débil? http://groups.google.com/group/comp.lang.scheme/msg/b8c43aee2bc12241
http://google.com/groups?selm=WGD.96Feb13081831%40berne.ai.mit.edu