El malentendido zombi de la informática teórica

• La computabilidad y la NP-hardness en informática teórica se aplican a funciones, lenguajes y secuencias infinitas, no a enteros individuales ni a una sola pregunta de verdadero o falso
• En el ejemplo de Sipser, la “función f que siempre devuelve 1 si Dios existe, y siempre 0 si no existe” es una función constante en ambos casos, por lo que es computable
• P vs NP no es un problema que reciba entradas, sino una sola pregunta de sí o no, así que no puede llamarse en sí misma NP-hard ni no computable
• La función Busy Beaver completa es no computable, pero un valor específico como BB(6) no puede tratarse del mismo modo, porque para cualquier entero k existe un programa print k
• El núcleo de la confusión recurrente está en aplicar conceptos pensados para objetos infinitos a problemas individuales; la costumbre de mezclar la no computabilidad del problema de la parada con la incompletitud de Gödel pertenece a la misma familia

---

El alcance de la computabilidad que enseña el ejemplo de Sipser

• En Introduction to the Theory of Computation de Michael Sipser hay un problema de tarea que deja ver la definición de computabilidad
  • Sea f:{0,1}*→{0,1} la función que siempre devuelve 1 si Dios existe, y siempre devuelve 0 si no existe
  • La pregunta es si f es computable, y la respuesta no depende de creencias religiosas
• f es computable
  • La función constante que siempre devuelve 1 es computable
  • La función constante que siempre devuelve 0 también es computable
  • Si f es una de esas dos, entonces f también es computable
• Una pregunta paralela con la misma estructura da la misma intuición
  • En la pregunta “si Dios existe entonces n=3, y si no existe entonces n=5; ¿n es primo?”, aunque n no esté completamente especificado, con saber que es un elemento de {3,5} basta para decir que es primo
  • Con f pasa lo mismo: solo queda decidir cuál de las dos funciones constantes es, pero está lo suficientemente especificada como para concluir que es computable

La computabilidad no trata de la dificultad de escribir un programa, sino de su existencia

• La computabilidad es un concepto que se aplica a funciones o secuencias infinitas
• No se atribuye computabilidad del mismo modo a preguntas individuales de sí o no ni a enteros individuales
• La pregunta clave es si existe un programa de computadora que haga el mapeo de entrada a salida
• Qué tan difícil sea elegir, encontrar o escribir ese programa no forma parte de la definición de computabilidad
  • Aunque para escribir el programa hubiera que resolver si Dios existe, eso no cambia el juicio de computabilidad en sí

Por qué no se puede llamar NP-hard a P vs NP

• La pregunta “¿la propia cuestión de P versus NP es NP-hard y por eso no se puede resolver?” se ha repetido varias veces durante los últimos 25 años
• NP-hard se aplica a funciones o lenguajes que reciben entradas, como 3SAT, Independent Set o Clique
  • La entrada puede ser una Boolean formula, un graph, etc.
  • La salida es la respuesta para esa entrada
  • Se dice que un problema es NP-hard cuando, si se puede resolver en tiempo polinomial, entonces mediante reducciones también se pueden resolver en tiempo polinomial todos los lenguajes o funciones de NP
• P vs NP no es una función ni un lenguaje, sino una sola pregunta de sí o no
  • No puede descartarse que su respuesta sea independiente de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel
  • Pero no se puede decir que esta pregunta sea en sí no computable o NP-hard
• Formalmente, sí existe un programa rápido que responde exactamente a la pregunta P vs NP
  • Si P=NP, un programa que imprime “P=NP”
  • Si P≠NP, un programa que imprime “P≠NP”

La misma confusión que reaparece con Busy Beaver

• En los comentarios de una publicación sobre la determinación del valor de Busy Beaver 5 también se repitieron preguntas parecidas
  • “¿Cuál es el menor n para el que el valor de BB(n) se vuelve no computable?”
  • “¿Podría BB(6) ya ser no computable?”
• La función Busy Beaver es no computable
• Pero el concepto de computabilidad no se aplica así a un entero individual como BB(6)
  • Sea cual sea el entero k que resulte ser BB(6), existe un programa print k
  • Ese programa imprime ese entero
• En cambio, sí puede preguntarse para qué n el valor de BB(n) es imposible de demostrar dentro de un sistema axiomático como la teoría de conjuntos ZF
  • Aaronson y Adam Yedidia trataron esta cuestión en 2016
  • El récord actual es n=745, una mejora sobre el n=8000 de Aaronson y Adam
• Puede considerarse que todo entero específico es “computable”, y lo no computable es la función BB completa

Por qué el “malentendido zombi” sigue reviviendo

• El centro de la confusión recurrente está en aplicar a enteros individuales y problemas abiertos conceptos diseñados para secuencias infinitas y funciones
• Los casos en que se mezcla la no computabilidad del problema de la parada con la incompletitud de Gödel pertenecen a la misma familia de confusiones
  • Están estrechamente relacionadas
  • Gödel permite hablar de proposiciones individuales
  • La computabilidad de Turing no es un concepto relativo a un sistema axiomático específico, sino un concepto absoluto
• Esta explicación sirve como punto de referencia al que se puede enlazar cuando vuelva a aparecer el mismo malentendido pedagógico
• La pregunta final se centra en cómo podría apagarse de una vez este malentendido “zombi”

[GN⁺]

Opiniones de Hacker News

• Que el concepto de computabilidad incluya inevitablemente el infinito puede resultar bastante contraintuitivo
  Por ejemplo, si uno pregunta si existe un algoritmo que calcule la complejidad de Kolmogórov K(s) para una cadena arbitraria s, la respuesta, como es bien sabido, es “no”. No existe una máquina de Turing que reciba una cadena de longitud arbitraria y calcule K(s), y la demostración se resuelve brevemente usando el problema de la detención
  Pero si uno pregunta si existe un algoritmo que calcule K(s) para cualquier cadena s cuya longitud sea menor que n, la respuesta es “sí”. Para cualquier n existe un algoritmo así
  El método, de forma decepcionante, es construir una máquina de Turing con una enorme tabla de consulta que contenga los valores K(s) para todas las 2^n cadenas posibles. Cómo se obtiene realmente esa tabla es otro asunto; como una implementación concreta tiene una descripción finita y K(s) también es finito para todo s, el algoritmo existe
  Por eso, una pregunta finita sobre un objeto finito puede no ser muy interesante desde el punto de vista de la computabilidad. Porque siempre se puede escribir un programa que imprima todas las respuestas, y solo cuando la pregunta se extiende a un conjunto infinito de objetos se vuelve interesante si algo finito puede responder a infinitas preguntas

  • Una explicación así puede hacer que una gran parte de la informática suene simplemente como un juego ridículo y sin sentido
    En realidad, el infinito está sustituyendo el “comportamiento aproximado, eventual o de estado estable para un N suficientemente grande como para superar cualquier truco puntual”
    En la práctica, esos trucos también importan, y las constantes y los términos de orden bajo que se ignoran en las comparaciones de Big O también son importantes para el rendimiento real. Siempre hay una tensión entre “problemas lo bastante grandes como para que los factores constantes dejen de importar” y “problemas lo bastante pequeños como para entrar en el rango implícito cuando se habla de una constante”. Por ejemplo, cuando los enteros de 32 bits fingen ser enteros
  • Claro que n, por definición, es un número finito, así que ese algoritmo existe
    Desde la perspectiva del infinito, todos los números finitos son en realidad muy pequeños. Si te sientas en una silla al borde del universo, 1 milla no es distinto de 1 milímetro
    Este escenario es básicamente como “el hotel infinito de Hilbert en una computadora”. Si se desplazan los programas existentes una posición, se puede agregar un nuevo programa, y el tamaño de la tabla necesaria para el cálculo queda igual
    Más en general, la mayoría de la gente tiene poca intuición sobre cómo funcionan el infinito, los álefs y la matemática transfinitaria. Tienen poca relevancia cotidiana y están profundamente entrelazados con propiedades emergentes de las matemáticas, la teoría de categorías y la teoría de conjuntos. No solo que el infinito sea mayor que cualquier número finito, sino también que algunos infinitos puedan ser mayores que otros, no resulta evidente para una intuición que se quedó en el concepto escolar de “infinito”
    La pregunta más interesante sería si existe algún n < ∞ que permita calcular el algoritmo, y por supuesto la respuesta es no; adiós premio Turing
  • Es parecido al hecho de que todas las computadoras reales solo tienen estados finitos, así que se parecen más a máquinas de estados finitos que a máquinas de Turing
  • También se puede decir que para una s concreta hay un algoritmo simple que calcula K(s), y por lo tanto también lo hay para cualquier conjunto finito de esas entradas
    La idea sería enumerar todas las máquinas de Turing posibles empezando por las más cortas hasta encontrar una que imprima s. Si ya probaste todas las máquinas más cortas y no imprimieron s, entonces encontraste la máquina más corta que imprime s, de modo que su longitud es K(s). Otras máquinas de la misma longitud o más largas también podrían imprimir s, pero K(s) es el valor de la longitud mínima, así que no cambia
  • Me viene a la mente el poder adicional que P/Poly podría tener sobre P. Creo que había un nombre general para la jerarquía de complejidad de circuitos en la que el circuito en sí debe ser emitido por una máquina de Turing simple, pero no me acuerdo ahora

• Según mi experiencia, aquí la matemática constructivista encaja mejor con la intuición de la gente que la informática clásica
  Por ejemplo, todavía no existe una prueba constructiva de que haya un programa que imprima la respuesta al problema P=NP
  En mi artículo también traté este problema en relación con los conjuntos de Julia computables. Mark Braverman demostró que todos los conjuntos de Julia cuadráticos son computables, pero él mismo explica que esa demostración no es uniformemente computable. En cambio, construye 5 máquinas que reciben los parámetros del conjunto de Julia deseado e intentan dibujar varios conjuntos con la resolución deseada, y para cada conjunto de Julia una de ellas lo dibuja correctamente
  En matemática constructivista, el concepto constructivo de un conjunto compacto corresponde aproximadamente al tipo de conjunto computable que se necesita para los conjuntos de Julia computables. Pero no se puede demostrar constructivamente que todos los conjuntos de Julia cuadráticos sean compactos; hay que dividir el plano complejo de los parámetros posibles en varias regiones y demostrar que, dentro de cada región, los conjuntos de Julia correspondientes son compactos
  En la matemática clásica, la unión de estas regiones es todo el plano complejo, pero en el constructivismo este resultado no se sostiene. Del mismo modo, en la matemática clásica la unión de los reales positivos y los reales no positivos es toda la recta real, pero en el constructivismo eso tampoco se sostiene
  El enfoque constructivista dice con precisión qué información adicional se necesita para realizar el cálculo en la práctica. Es decir, hay que determinar a qué región del plano complejo pertenece el parámetro dado, y así saber cuál de las 5 máquinas ejecutar para obtener la imagen deseada. Esta se siente como una respuesta mucho más satisfactoria

  • En el caso P=?NP que plantea Aaronson, la respuesta tampoco debería ser una respuesta clásica como “P=NP”, sino una función real NP→P
    La gente sabe instintivamente que necesita saber en qué lado de la bifurcación está, y no es que haya sido entrenada en lógica clásica y por eso haya olvidado ese hecho
  • Es interesante eso de que “para cada conjunto de Julia, una de las 5 máquinas lo dibuja correctamente”. Me pregunto si esto equivale esencialmente a una prueba de que la probabilidad de calcular el conjunto correcto es de al menos 1/5
    También me pregunto si, ante la pregunta “cuál de las 5 es la correcta”, se considera que hay una prueba que aún no se ha encontrado, o si se la ve como indecidible, como dentro de ZFC

• Creo que este es uno de los factores que dificulta entender la indecidibilidad del problema de la detención.
  Uno quisiera decir: “hay máquinas tan complejas que ninguna máquina puede determinar si se detienen o no”, pero uno de los programas triviales return true y return false siempre dará la respuesta correcta para cualquier máquina y entrada que se le pase.
  Querrías refutarlo diciendo: “esos programas no saben nada sobre máquinas de Turing, así que hay que excluirlos”, pero la decidibilidad no se trata de eso. También se podría pensar que “lo indecidible es averiguar cuál de los dos programas es el correcto”, pero eso también tiene una respuesta determinada, verdadera o falsa. El problema solo puede volverse indecidible cuando se extiende a un conjunto infinito de combinaciones máquina/entrada.

  • Otros problemas que solo aparecen en familias de objetos también pueden ser igual de difíciles de entender para principiantes.
    Por ejemplo, cualquier espacio vectorial de dimensión finita es isomorfo de varias maneras a su espacio dual y a su bidual, pero para este último se puede elegir un isomorfismo “natural” coherente a lo largo de todos esos espacios, mientras que para el primero no.
    Ahí surge confusión del tipo: “¿Por qué no son naturalmente isomorfos? ¡Las bases tienen la misma longitud! ¿Por qué importa si depende de la base o no? ¿Por qué en otras demostraciones sí está bien elegir una base?”.

• Creo que el problema de la formulación es que requiere lógica modal.
  “Si Dios existe, definamos f:{0,1}*→{0,1} como la función constante 1; si Dios no existe, como la función constante 0. ¿Es f computable? Pista: la respuesta no depende de creencias religiosas”.
  La pregunta precisa es si f sería computable, es decir, si existe una máquina de Turing M tal que para todo x se cumpla f(x)=M(x).
  La respuesta es sí. Porque, en cualquier mundo, existe una máquina de Turing trivial M=1_M o M=0_M. En cambio, la formulación original, “¿es f computable?”, es una pregunta modalmente mal planteada, más cercana a una pregunta gramaticalmente incorrecta como las paradojas de Sleeping Beauty o Red Envelope.
  Desde otro punto de vista, la dependencia de Dios o de algún hecho que podría ser real se parece más a una directiva de compilador o a un pragma que se completa después, pero queda fijado antes de usarse. Si se pregunta correctamente, no es más que un ejercicio de desplegar las definiciones rigurosas de función y computabilidad, y ambas están definidas explícitamente en Sipser.

  • Mi reacción fue parecida, y eso escribí en los comentarios del texto de Aaronson. Esta pregunta no trata de una función f que pueda llamar a la función constante 1 o a la función constante 0 según exista Dios o no.
    Lo que dice es que el referente de la etiqueta f será la función constante 1 si Dios existe, y la función constante 0 si Dios no existe; simplemente no sabemos cuál de las dos es hasta conocer si Dios existe. Como la computabilidad de ambas funciones constantes es evidente, en realidad se parece más a un problema de etiquetas que a uno de computabilidad.
  • Las paradojas de Sleeping Beauty o Red Envelope no parecen tener mucha relación con esto. Esas paradojas solo muestran que aplicar conceptos puramente matemáticos de probabilidad al mundo real a veces no es sencillo.
    No sorprende si se considera que el hecho mismo de que la teoría de la probabilidad funcione al aplicarse a la realidad es bastante misterioso y ha sido objeto de muchas investigaciones científicas y filosóficas.
    La solución propuesta de tipo “would f be” tampoco parece resolver gran cosa. El propósito de la pregunta sobre “Dios” es hacer que el lector salga de un problema P-NP específico y entienda que, para funciones constantes, el concepto de computabilidad no aporta nada útil. Para que esta propuesta ayudara, tendría que poder aplicarse también a la pregunta original sobre P-NP, y todavía no veo cómo entra un enfoque modal en una pregunta matemática bien definida.
  • Creo que si esta oración se escribiera un poco más larga habría menos errores de parseo.
    “Si Dios existe, definimos f:{0,1}→{0,1} como la función constante 1; si Dios no existe, definimos f:{0,1}→{0,1} como la función constante 0”.
  • Sea cual sea el predicado que se ponga en lugar de “Dios”, esa implicación, estrictamente hablando, es verdadera en la lógica clásica de primer orden, y probablemente también en muchos otros sistemas lógicos. La analogía con el pragma es adecuada.
    Que ese predicado corresponda o no al concepto de Dios de cada quien es un problema no matemático aparte.
    Es parecido a la sorpresa que siente la gente al aprender que, en lógica clásica, una proposición falsa implica cualquier cosa. En matemáticas hay reglas formales estrictas, y es importante dejar de lado las ideas preconcebidas sobre el significado cotidiano de palabras como “implica” o “si”.
  • La versión dependiente del tiempo es mucho más interesante.
    Sería algo como definir G:t∈ℝ⁺->{0,1} como 1 si Dios existe en el tiempo t, y 0 si no.
    Por supuesto, analizar G en un sistema de referencia no inercial lo vuelve más interesante.

• Sipser está aprovechando que la mayoría de la gente no distingue bien entre cómputo e investigación empírica.
  “¿Existe Dios?” quizá sea una pregunta imposible de responder, pero ese no es el punto. Encontrar esa respuesta, para empezar, no pertenece al ámbito del cómputo. Un cómputo es solo un procedimiento que mapea entradas a salidas, y en este caso la existencia de Dios es una de las entradas.
  La confusión viene de que no podemos conocer realmente el valor de entrada, pero el programa sigue existiendo y es trivial. Se podría reemplazar por cualquier otra pregunta empírica binaria.
  Por ejemplo, digamos que f:{0,1}* -> {0,1} vale 1 “si hay al menos un baño portátil en París”, y 0 si no. Eso es computable e incluso se puede ejecutar realmente con una entrada verdadera. La función sobre Dios también es computable, solo que únicamente puede ejecutarse con una entrada conjeturada. Aunque no haya garantía de que la salida corresponda de forma significativa con el universo en el que vivimos, sigue siendo una función computable.
  Más simple aún, basta con pensar en f:{0,1}* -> {0,1}. “Dios existe” y “Dios no existe” son, cada una, posibles cadenas de bits. Si la pregunta es si puede existir un programa que, al recibir una de ellas como entrada, imprima 0, y al recibir la otra imprima 1, por supuesto que sí. No importa si la entrada es empíricamente verdadera o no.

  • De hecho, las funciones de la pregunta no usan la entrada para nada. Mejor podrían definirse como funciones del conjunto vacío a {0, 1}.
    La f de la pregunta no es una función, sino una etiqueta. Si Dios existe, el referente de f es f1, que siempre imprime 1; si Dios no existe, es f0, que siempre imprime 0. Así que, en realidad, no es un problema de computabilidad, sino de etiquetas.

• Esto pasa todo el tiempo porque matemáticos y científicos de la computación usan expresiones abreviadas que omiten detalles para facilitar la conversación.
  No es distinto de decir “multiplicamos ambos lados por dx”. La pregunta “¿el problema del viajante es NP-hard?” se refiere a una familia de problemas, no a una instancia específica. Si fijás un grafo concreto, no hay N, así que obviamente no es NP-hard.
  Si sabés esto, es tan obvio que ni vale la pena decirlo, pero para alguien que no conoce el significado de los términos resulta totalmente inaccesible.
  Yo también tuve en el pasado un malentendido similar en otro campo. Veía el ADN como si fuera código, y creía que las cosas que intercambian mensajes mediante sustratos, ya sea directamente o modificando el ADN, ejecutaban ese código. En conjunto no es un modelo completamente inútil, pero había que saber cuándo no dejarse atrapar por él.
  Para un biólogo con formación matemática, ver el ADN tal cual como un modelo de ejecución de una máquina de Turing es claramente incorrecto, pero para mí no lo era. Al final, el problema viene de lo ajenos que resultan los conocimientos básicos.

• Palabras como decidibilidad, computabilidad, existencia e incluso fruta tienen significados distintos en contextos académicos y cotidianos. Si llevás la intuición del significado cotidiano al contexto académico, aparecen estas “preguntas tontas”.
  Algunos números enormes que aparecen en Wikipedia “existen” y son “computables” en el sentido académico, pero sus dígitos no cabrían dentro de nuestro universo.

• Si no se lee con cuidado, la formulación puede confundir.
  En “si Dios existe, definamos f:{0,1}*→{0,1} como la función constante 1; si Dios no existe, como la función constante 0. ¿Es computable f?”, las alternativas no forman parte de la función.
  La función f no ramifica según el valor de “Dios existe”; la ramificación está en el metalenguaje. No sabemos si f=0 o f=1, pero en cualquiera de los dos casos ambas funciones posibles son computables, así que f también es computable.
  Más aún, incluso si f incluyera realmente esa ramificación y el dominio de la función fuera 0 (Dios no existe) y 1 (Dios existe), seguiría siendo una función computable en el sentido de que se puede calcular el resultado para cada valor del dominio.
  El núcleo de la confusión está en meter dentro de f, como condición de ramificación, una variable libre cuyo valor se considera desconocido.

• Estoy dispuesto a objetar el ejemplo “si Dios existe, sea n=3; si Dios no existe, sea n=5. ¿n es primo?”.
  Aquí se está usando el tercero excluido para afirmar que n es 3 o 5, pero no hay justificación de que el tercero excluido valga para la proposición “Dios existe”.

  • En la lógica clásica, el tercero excluido es válido.
    En este caso, si se va a cuestionar si el tercero excluido está justificado, también habría que justificar por qué se cuestiona solo el tercero excluido. ¿Por qué no descartar también el principio de explosión y trabajar en lógica paraconsistente? Kolmogorov también veía serios problemas en este axioma y al principio consideraba que no era compatible con la lógica constructivista.
    Además, según la formalización exacta de esta proposición, puede que ni siquiera sea necesario el tercero excluido.
  • Como referencia, la versión del libro de texto dice que se debe suponer que la pregunta es un problema binario claro (Sipser, 2.ª edición, p. 162). Haber notado eso es bastante agudo.
  • “¿n es primo?” también depende de la voluntad de Dios, si Dios existe.
    Dios no necesariamente tendría que estar atado a las leyes físicas ni a necesidades lógicas básicas. Ese concepto de Dios proviene de cierta línea de razonamiento teológico, no es el caso general.
    Si quisiera, Dios podría hacer que 6 fuera impar. También podría cambiar toda la matemática, la consistencia lógica y el universo entero, o crear un mundo donde solo 77 fuera par y todos los demás números fueran impares, y hacer que todos los matemáticos consideraran esa disposición totalmente consistente y siempre correcta.
    Por eso, puede decirse que la respuesta depende en cierta medida de la creencia religiosa.

• La informática teórica y la teoría de la complejidad parecen ocupar, para estudiantes de grado de CS o personas de industrias cercanas, un lugar similar al que la física de partículas ocupa para el público general.
  Así como la gente común ha oído hablar del entrelazamiento, nosotros hemos oído hablar de NP-hard, y en vez de seguir el desarrollo matemático directamente lo reemplazamos por pésimas analogías populares y fantasías.

  • Dicho eso, no hay razón para pensar que todo el mundo deba usar la palabra “computable” solo con una definición muy estricta. La definición cotidiana, “lo que una computadora puede hacer”, también tiene sentido.
    Puede que el autor, por su largo entrenamiento, haya elegido su propia definición muy estricta de computabilidad, haya escrito todo el texto sobre esa definición particular de la palabra y luego haya acusado de hacer preguntas tontas a la gente del mundo que usa la misma palabra con otra definición.
    Esto pasa muy seguido cuando se habla con académicos en el trabajo o con gente común. Es difícil acordar términos compartidos, y resulta agotador trazar una línea según los propios términos y luego pedirles a los demás que se pongan al día.