¿Existen resultados de indecidibilidad que no se saben que tengan una demostración por argumento diagonal?

Question

¿Existe algún problema que se sabe que es indecidible (en el sentido algorítmico), pero para el cual las únicas pruebas conocidas de indecidibilidad no utilizan alguna forma del argumento diagonal de Cantor de manera esencial?

Debo admitir libremente que esta es una pregunta algo mal formulada, por varias razones:

1. Uno podría tomar una prueba que no use diagonalización e insertar una invocación gratuita del argumento diagonal para evitar una respuesta positiva a esta pregunta por una cuestión técnica. (Por lo tanto, el calificador "esencial" en la pregunta anterior tiene que hacer mucho trabajo pesado.)
2. Como señaló Timothy Chow en esta respuesta anterior de MO, no hay una noción bien definida de lo que significa "usar diagonalización".
3. Muchos resultados de indecidibilidad no mencionan la diagonalización en el nivel superior de su prueba, sino que se basan en reducciones a otros resultados de indecidibilidad, como la indecidibilidad del problema de detención, que generalmente se demuestran mediante diagonalización.

De todos modos, espero que el espíritu de la pregunta siga siendo claro, a pesar de su falta de precisión.

Dos observaciones:

1. La indecidibilidad del problema de detención en sí misma ciertamente tiene pruebas que posiblemente no invoquen la diagonalización (algunas de ellas se enumeran aquí). Pero esto no sería una respuesta positiva a mi pregunta, porque la indecidibilidad del problema de detención también tiene la prueba de libro de texto que usa la diagonalización.
2. Ciertamente hay resultados de indecidibilidad que no se prueban simplemente mediante reducción al problema de detención; consulte las respuestas a esta pregunta anterior de MO para ver varios ejemplos. Es posible que uno de los resultados mencionados allí sea ya una respuesta candidata a mi pregunta, aunque no pude identificar fácilmente dicho candidato.

Answer 1

Déjame proponer un candidato: la complejidad de Kolmogorov no es computable.

Es decir, no existe un procedimiento computable que, dada una secuencia finita $s$, produzca el tamaño del programa más pequeño (con respecto a alguna noción natural fija de tamaño) que puede escribir $s$ como salida.

Para probar esto, suponemos hacia una contradicción que la complejidad de Kolmogorov fuera computable. El programa que la realiza tendría un tamaño $k$, que podemos suponer que ya es bastante grande. Utilizando este algoritmo de Kolmogorov como subrutina, escribimos un programa simple $p$ que considera las secuencias binarias finitas a su vez, hasta que encuentre una secuencia $s$ cuya complejidad de Kolmogorov exceda $2^{2^k}$. Nos detenemos y producimos la primera $s$ que se encuentre.

Observa que $2^{2^k}$ tiene una complejidad de Kolmogorov mucho menor que $k$, ya que $k$ puede ser descrito explícitamente en un programa de tamaño aproximadamente $\log(k)$ codificando los dígitos, y luego podemos describir cómo calcular exponenciales. Así que el programa $p$ tendrá un tamaño menor que $k$ o aproximadamente $k$. Ciertamente menor que $2^{2^k}$.

Pero si la computación de Kolmogorov funciona correctamente, el programa $p$ produce una secuencia que no puede ser producida por un programa tan pequeño. Contradicción.

¿Es esta una demostración por diagonalización? Bueno, en ningún momento diseñamos un proceso que diagonalizara contra todos los programas, o contra todos los tamaños. No hicimos nada con cada índice posible $i$ para derrotar a ese índice en particular como solución. El programa $p$, después de todo, fue diseñado específicamente para derrotar solo un $k$ específico, el tamaño del programa que decide la complejidad de Kolmogorov, que nos fue dado antes de que diseñáramos $p$.

Por otro lado... Tengo una visión muy amplia de la diagonalización, y en mi opinión casi cada argumento no trivial en la materia de lógica en su totalidad, incluyendo cada resultado de indecidibilidad y cada resultado en teoría de computabilidad, teoría de la complejidad, teoría de conjuntos de cardenales grandes, y demás, participa profundamente de la diagonalización. Así que lo que espero es que para cada respuesta propuesta a la pregunta, será posible ver un destello de diagonalización en su interior. Es parte del ADN de la materia.

Answer 2

Desde un punto de vista, tu pregunta se relaciona con una "conjetura abierta" en la teoría de computabilidad.

Creo que estás preguntando si hay un problema específico $ P $, que se puede mostrar que es indecidible, pero no con un argumento de diagonalización o con una reducción al problema de la Detención que ya tiene un argumento de diagonalización.

Ahora vamos a analizar esto. Un problema de decisión particular corresponde a un grado de Turing particular $ T $, y si su falta de resolución se puede reducir a la falta de resolución del problema de la detención, entonces $ T \geq 0'$.

Hay una conjetura informal (que escuché por primera vez de Steven Simpson, pero no sé quién la observó por primera vez): Los únicos grados de Turing con definiciones bien definidas son $ 0 $ (cosas computables), $ 0' $ (cosas equivalentes al problema de la Detención), $ 0'' $ (cosas equivalentes al problema de la Detención relativo al problema de la Detención), y así sucesivamente. Entonces los únicos grados de Turing no computables que son 'buenos' computan todos el problema de la Detención. Esto incluye resultados conocidos de indecidibilidad como el problema 10 de Hilbert, el teselado de Wang, la complejidad de Kolmogorov, y similares. Resolver todos ellos resolvería el problema de la Detención (lo cual es demostrado por diagonalización).

Ahora bien, podemos definir otros grados de Turing explícitamente, como el grado que proviene de una prueba del teorema de Friedburg-Munich de que hay un grado entre $ 0 $ y $ 0' $, pero las definiciones están increíblemente conectadas a las definiciones exactas que damos de cosas como la máquina de Turing. Incluso una definición ligeramente diferente (pero equivalente) de máquina de Turing llevaría a una enumeración diferente de todos los programas, lo que llevaría a un grado intermedio muy diferente.

La conjetura básicamente es que no hay problemas reales (matemáticos) en el mundo que no estén en $ 0 $, $ 0' $, $ 0'' $, o más altos. Por supuesto, como tu pregunta, esta conjetura no está bien planteada. (Pero he escuchado a personas sugerir que la solución al problema 10 de Hilbert para los racionales es un grado intermedio entre $ 0 $ y $ 0' $ lo cual me parece absurdo, ya que claramente violaría esta conjetura.)

Entonces creo que no, no hay problemas de indecibilidad (naturales) que no se puedan resolver mediante diagonalización, incluso si es solo reduciéndolo al problema de la Detención.

Answer 3

Demasiado largo para ser un comentario: El argumento de complejidad de Kolmogorov de Joel contiene lo que consideraría ser una diagonalización. Aquí hay un argumento esencialmente equivalente que hace que la diagonalización sea más obvia, al eliminar el uso de la contradicción y argumentar directamente:

Teorema: Ningún programa calcula la complejidad de Kolmogorov.

Bosquejo. Sea $P$ un programa que toma cadenas binarias como entrada y produce números; construiremos una cadena binaria $s$ cuya complejidad de Kolmogorov satisface $K(s) \neq P(s)$. Haremos esto construyendo un segundo programa $Q$ como en el argumento de Joel, que utiliza $P$ como subrutina para producir la primera cadena lexicográficamente que cumple $P(s) \ge 2^{2^k}$ donde $k$ es el tamaño de $P$, si existe tal cadena.

Si existe, entonces según argumenta Joel, $Q$ no puede ser mucho más grande que $P$, lo que nos da un límite del tipo $K(s) \le k + \log k + C$ o algo así. Y, limpiando los detalles de los distintos límites (podríamos reemplazar $2^{2^k}$ por una función diferente si es necesario), esto nos da $K(s) < P(s)$ como se deseaba.

De lo contrario, $P$ está limitado por $2^{2^k}$, pero $K$ no lo está, por lo que podemos encontrar una cadena $s$ tal que $K(s) \ge 2^{2^k} > P(s)$. $\Box$

Para mi mente, esto es una diagonalización sobre todos los programas, y creo que al escribir el argumento con más detalle se vería aún más como una diagonalización. Después de todo, en algún momento en la búsqueda sobre cadenas binarias, para que este argumento funcione, ¡$Q$ necesariamente encuentra el código fuente de $P$ en binario, y lo aplica a $P$!

Answer 4

Creo que la prueba similar a Burali-Forti de la incomputabilidad de (una variación menor de) Kleene's $\mathcal{O}$ podría encajar.

Sea $\mathcal{W}$ el conjunto de índices para los well-orderings computables; básicamente, $e\in\mathcal{W}$ si la máquina de Turing $e$-ésima computa una relación binaria $R$ en los naturales tal que $(\mathbb{N};R)$ es un well-ordering (que identificaré con $R$ en sí). Consideremos - antes de establecer cualquier hipótesis contrafactual - el well-ordering $$\lambda:=\left(\sum_{e\in\mathcal{W}}R_e\right)+1.$$ Por definición, todo ordinal computable se incrusta como un segmento inicial adecuado de $\lambda$, así que $\lambda$ no es isomorfo a ningún ordinal computable. Pero evidentemente podemos computar una copia de $\lambda$ a partir de $\mathcal{W}$. Observa que en ningún momento tenemos que mirar el índice presunto para la computación de $\mathcal{W}$ o $\lambda$, así que aquí no veo nada como diagonalización.

---

Aquí hay dos puntos críticos:

• ¿Realmente evita la diagonalización lo anterior? Yo diría que sí, y en particular que la definición y análisis de $\lambda$ no implica auto-referencia ya que un índice presunto para $\mathcal{W}$ ni siquiera ha sido introducido aún, pero consulta los comentarios abajo.

• Aunque el argumento anterior esté libre de diagonalización, aún queda la pregunta de si alguna prueba de la incomputabilidad de $\mathcal{W}$ utiliza diagonalización. Por ejemplo, es ciertamente posible demostrar la incomputabilidad de $\mathcal{W}$ al reducir primero ${\bf 0'}$ a $\mathcal{W}$ y luego aplicar un argumento diagonal para analizar ${\bf 0'}$. Sin embargo, creo que esto es mucho más complicado que el argumento puramente estructural anterior, por lo que se podría decir que esto no se beneficia de la diagonalización.

En última instancia creo que esto se sostiene en ambos puntos, pero la opinión de cada uno puede variar.

Answer 5

[Editado ligeramente para (¡espero!) mayor claridad.]

Esto es más un comentario que una respuesta, pero creo que es relevante. En el contexto de la teoría de la complejidad computacional (en lugar de la teoría de la computabilidad), uno podría esperar que sea más fácil dar ejemplos de teoremas cuyas demostraciones no solo no usan diagonalización, sino que no pueden usar diagonalización. La razón es que la sabiduría convencional es que "los argumentos diagonales relativizan", y por lo tanto un argumento diagonal no puede demostrar algo como $\mathsf{P} \ne \mathsf{NP}$, que tiene relativizaciones contradictorias.

Desafortunadamente, incluso el caso de $\mathsf{P} \ne \mathsf{NP}$ no es claro, porque no está del todo claro exactamente qué es un "argumento diagonal". En un artículo muy interesante, Indexación de clases subrecursivas, Dexter Kozen argumentó que si $\mathsf{P} \ne \mathsf{NP}$ es demostrable en absoluto, entonces es demostrable por diagonalización. Por supuesto, uno podría objetar que la definición de Kozen de un "argumento diagonal" es artificial, y que aún debería haber algún sentido en el que la sabiduría convencional sea correcta. Pero precisar ese sentido es sorprendentemente sutil, especialmente si un argumento de diagonalización se combina con otros argumentos. En el capítulo de Scott Aaronson del libro Problemas abiertos en Matemáticas, esboza la prueba de un famoso límite inferior debido a Ryan Williams, y concluye:

El resultado de Williams hace posible imaginar que, en un futuro lejano, $\mathsf{P} \ne \mathsf{NP}$ podría ser demostrado asumiendo lo contrario, luego derivando consecuencias cada vez más extrañas usando miles de páginas de matemáticas apenas comprensibles para cualquiera vivo hoy en día, y sin embargo, el coup de grâce será un argumento de diagonalización, apenas diferente de lo que Turing hizo en 1936.

De todos modos, incluso si dejamos de lado los problemas matemáticos inversos que mencioné en esa otra respuesta de MO, la conclusión es que puede ser muy difícil argumentar de manera convincente que una prueba de incalculabilidad particular "no usa el argumento diagonal de ninguna manera esencial".