Sobre la indecidibilidad del problema del salto de energía

Por Francisco R. Villatoro, el 10 diciembre, 2015. Categoría(s): Ciencia • Física • Informática • Matemáticas • Mathematics • Nature • Noticias • Physics • Science ✎ 16

Dibujo20151210 gapped and gapless spectrum quantum system nature com

Saber si un algoritmo se detiene tras un número finito de pasos, el problema de la parada, es un problema indecidible. Alan Turing demostró en 1936 que no hay ningún algoritmo universal capaz de decidir  si cualquier otro algoritmo parará o no aplicado a una entrada arbitraria. La idea de la demostración es similar a decidir si la frase «esta frase es falsa» es verdadera o es falsa (obviamente indecidible). ¿Existen problemas físicos que sean indecidibles? No sabemos si la Naturaleza es (o tiene que ser) computable (en el sentido de la tesis de Church–Turing). Luego la cuestión es imposible de resolver.

Se puede construir un algoritmo que simule un sistema físico, es decir, existe un sistema físico discreto, que incorpore en su formulación el problema de la parada de Turing. El resultado de dicha simulación física (o sistema físico discreto) será indecidible. Tras un alarde técnico el español David Pérez-García y dos colegas lo han publicado en Nature. En concreto, demuestran que no es decidible si un sistema cuántico discreto con un hamiltoniano con invariancia ante traslaciones en el tiempo tiene un salto de energía (gap). Recuerda que el espectro de energía de un sistema cuántico puede ser continuo (tener un punto de acumulación) en el estado de mínima energía (sistema sin gap), o puede ser discreto con un salto finito entre los dos primeros niveles de energía (sistema con gap).

Este problema está relacionado con el problema del salto de masa en las ecuaciones de Yang-Mills puras (uno de los Problemas del Milenio del Instituto Clay de Matemáticaas, premiable con un millón de dólares [PDF]). Por supuesto, el nuevo artículo no implica que dicho problema no sea decidible (igual que el problema de la parada de Turing no implica que no haya infinitos algoritmos en los que podamos decidir si paran o no paran).

El artículo es Toby Cubitt, David Perez-Garcia, Michael M. Wolf, «Undecidability of the spectral gap,» Nature 528: 207–211 (10 Dec 2015), doi: 10.1038/nature16059, short version [8 pp.], arXiv:1502.04135 [quant-ph], full version [146 pp.], arXiv:1502.04573 [quant-ph]. Más información divulgativa en Davide Castelvecchi, «Paradox at the heart of mathematics makes physics problem unanswerable,» News, Nature, 09 Dec 2015; critica el enfoque de muchos medios Luboš Motl, «Physics problems cannot be undecidable,» The Reference Frame, 10 Dec 2015.

Dibujo20151210 Part 1 Complete Hamiltonian construction From Undecidability of the spectral gap nature com

¿Qué es computable (o calculable)? Según la tesis de Church–Turing, cualquier cosa que se pueda formular mediante un algoritmo. ¿Todos los números reales son calculables? No, pues hay una cantidad infinita numerable de algoritmos y los números reales son un conjunto no numerable («Vídeo de “Los números que no se pueden calcular (Homenaje a Turing)” en Naukas Bilbao 2012,» LCMF, 03 Oct 2012). Por tanto, con probabilidad uno, un número real elegido al azar no será computable. En Física usamos el concepto de número real para describir la Naturaleza, aunque solo podemos realizar operaciones con números computables. No pasa nada, pues la Física describe modelos de la realidad. Más aún, las simulaciones físicas de la Naturaleza mediante ordenadores usan un número finito de números (los que se pueden representar en aritmética flotante en el ordenador) y nadie duda de que sean simulaciones realistas útiles en ingeniería.

¿Qué es un algoritmo? La tesis de Church–Turing afirma que el concepto de algoritmo es equivalente a una máquina de Turing; hay muchos otros modelos matemáticos del concepto de algoritmo, pero todos son matemáticamente equivalentes a una máquina de Turing y entre sí. Si no sabes lo que es una máquina de Turing (la cinta de colores en la figura de arriba), porque no hayas estudiado informática, o porque no hayas leído el famoso libro de Roger Penrose «La nueva mente del emperador» (Oxford Univ. Press, 1989), lo siento, no te lo voy a explicar (consulta la wikipedia). Resumiendo hasta el extremo, una máquina de Turing (universal) es un modelo matemático del funcionamiento de un ordenador (en rigor, todos los ordenadores son máquinas de Turing).

Cubitt, Pérez-García y Wolf usan una máquina de Turing cuántica. La tesis de Church–Turing–Deutsch afirma que el concepto de algoritmo cuántico es equivalente a una máquina de Turing cuántica. Además, David Deutsch en 1985 demostró que toda máquina de Turing cuántica (o máquina de Deutsch) es equivalente a una máquina de Turing (clásica); no hay nada que una máquina cuántica pueda calcular que no pueda calcular una clásica, y viceversa (aunque Stuart Hameroff no lo sepa, porque no entiende a su colega Roger Penrose). El problema de la parada de máquinas de Turing cuánticas es idéntico al problema de máquinas de Turing (clásicas).

Como puedes imaginar, para incorporar un algoritmo no decidible en la formulación matemática de un sistema físico cuántico (el sistema bidimensional de espines cuánticos con interacción entre vecinos que aparece en forma de grafo en la parte de abajo de la figura de arriba) conviene formular dicho algoritmo usando una máquina de Turing cuántica. Pero ello no cambia nada el resultado, solo facilita la descripción matemática. Por cierto, si no sabes lo que es el espín y qué es un sistema de espines con interacción entre vecinos, lo siento, tampoco te lo voy a explicar (consulta la wikipedia).

Dibujo20151210 Part 2 Complete Hamiltonian construction From Undecidability of the spectral gap nature com

El espectro de energía de un sistema cuántico es el conjunto de niveles de energía para sus posibles estados. Este espectro puede ser discreto, cada par de niveles de energía está separado entre sí por un salto (gap), o puede ser continuo, los niveles de energía corresponden a números reales, o puede ser una combinación de ambos (el espectro discreto presenta regiones con espectro continuo). Todo sistema cuántico estable tiene un estado fundamental, un nivel mínimo de energía. El sistema tiene un salto de energía (gap) si el siguiente nivel de energía está separado del fundamental; pero hay sistemas sin salto de energía (gapless) en los que el nivel fundamental es el nivel de energía más bajo de un espectro continuo.

Cubitt, Pérez-García y Wolf estudian si es decidible el problema de determinar si un sistema cuántico concreto tiene gap o no tiene gap. Para ello introducen un sistema cuántico en forma de red plana de espines cuya interacción entre vecinos depende de los resultados de la ejecución de una máquina de Turing cuántica. Para cualquier máquina de Turing se puede construir el sistema correspondiente. Por ejemplo, para la máquina de Turing universal que Turing usó en su demostración de que el problema de la parada no es decidible. Repito, tras un sorprendente alarde técnico, la definición de su sistema cuántico garantiza que el espectro tendrá un salto de energía (gap) si dicha máquina de Turing para y no tendrá salto de energía (gapless) si dicha máquina de Turing no para. Por tanto, ¿se puede decidir si dicho sistema cuántico tiene gap o no lo tiene? No, porque el problema de la parada no es decidible.

En resumen, la conclusión general es que el problema de saber si un sistema cuántico discreto tiene o no tiene salto de energía no es decidible. ¿Significa esto que la Naturaleza no es decidible? No, por supuesto que no. Dicho sistema cuántico se puede construir físicamente, igual que se puede implementar en tu ordenador la máquina de Turing universal que usó Turing en su demostración, pero ello no implica nada sobre la Naturaleza (o la Física) en general. La tesis sobre la Naturaleza es computable o no es computable, o sobre si es decidible o no es decidible, no tiene nada que ver con el artículo que se acaba de publicar en Nature.

Y, repito para los despistados, ¿significa este nuevo teorema matemático que el problema del salto de masa para las ecuaciones de Yang–Mills no es decidible? No, por supuesto que no. Igual que el problema de la parada no implica que no existan algoritmos en los que podemos decidir si paran o no (la mayoría de los estudiados por los alumnos de informática durante su carrera). Si te atreves (y quieres dedicar algunas décadas de tu vida a ello), aún puedes resolver el Problema del Milenio y ganar el correspondiente millón de euros. No es fácil, pero intuyo que no es imposible.



16 Comentarios

  1. Una entrada maestra Francis:

    Primero: Es común que pase esto de atribuir la propiedad de indecibilidad a uno problema abierto famoso, ha pasado con la hipótesis de Riemann, con la conjetura de Hogde, la conjetura de Collatz… incluso en la novela «Tio petros y la conjetura de Golbach» es un hecho importante en la trama la idea de que esta es indecidible.

    «¿Existen problemas físicos que sean indecidibles? No sabemos si la Naturaleza es (o tiene que ser) computable (en el sentido de la tesis de Church–Turing)» Que pregunta tan importante hace Francis.

    Con el advenimiento de la paradoja de la información y la paradoja AMPSS parece cada vez más relevante pensar en la física en términos computacionales (parafraseando a Scott Aaronson), pensar en las repercusiones de la teoría de la complejidad en física (como lo hace ya Susskind), en si la información es es el objeto fundamental (como cuenta en su libros Vedral), en mirar la qft y cuerdas desde la óptica computacional (T`Hoft) y un muy largo y emocionante etc.

    ¿La información es física? (Landauer)

    ¿La fundamental diferencia entre la teoría cuántica y la física clásica es cuestión de computabilidad? y si la respuesta es si ¿Qué pasa si P=NP?, ¿Cuales serían las consecuencias físicas de la igualdad P=NP o de su negación? (esto es algo de lo que se ha hablado en este blog)

    ¿La mecánica cuántica es derivable desde principios de la teoría de la información?

    ¿Todo proceso físico puede ser simulado con un computador cuántico? (Feynman)

    ¿Qué piensan los demás lectores?

    Por cierto Francis: Se que usted está ocupado con cosas importantes pero me sorprende que alguien que es un físico tan dotado, computólogo apasionado y con un blog tan fantástico no hiciese eco de el supuesto algoritmo que resuelve el problema del isomorfismo de grafos en tiempo cuasipolinomial (sé que en twitter hizo voz de ello). De cualquier manera estoy estudiando el primer curso en computación teórica gracias a entradas que aparecieron en este blog y me formé en geometría diferencial por la emoción de los post sobre el problema del salto de masa, así que de ninguna manera es un reclamo 🙂

    En mathoverflow se preguntó por las repercusiones de este resultado y alguien (el más votado) aseguro que básicamente es ninguna… lo realmente escandaloso hubiese sido que se hubiese colocado el problema del isomorfismo en P.

    1. Ramiro, un post sobre el problema del isomorfismo de grafos está entre mis borradores. Lo iba a finalizar y publicar en el último Carnaval de Matemáticas (alojado en Gaussianos) pero al final no tuve tiempo… Ya aparecerá… aunque como no hay aún ningún artículo publicado (sólo un vídeo de una charla y varios posts explicando su contenido), yo estaba esperando a que se publicara algo (no vaya a ser esto como el cuento de la lechera).

    2. Muchas veces, Ramiro, pienso que todo apunta a que posiblemente la naturaleza pudiera finalmente simularse computacionalmente hablando, pero después me doy cuenta, que esa idea , que esa intuición, casa perfectamente con la lógica de alguien en el espacio y tiempo que me ha tocado vivir, y entonces…me desinflo y no sé qué pesar. 🙂

      1. Gracias por el comentario Pedro.

        Entiendo vuestra postura y pienso que sea cual sea esta la pregunta no deja de ser sumamente importante ¿La naturaleza es un modelo de computación?

        No se si sea un buen símil pero hace unos días pensaba en que el descubrimiento de nuevas y más poderosas teorías físicas siempre conlleva un aumento en su capacidad de poder de cómputo… es decir la mecánica clásica y la teoría de campos clásicos es una teoría determinista que bien puede decirse es un modelo de computación determinista. La cuántica llega después y esta es un modelo de un teoría que se comporta como una máquina de Turing probabilista y no determinista (en el sentido de la tesis fuerte de Church-Turing), la teoría cuántica de campos(perturbativa) parece una aproximación a una clase de métodos desconocidos(no pertubativos) para los cuales bien podría no existir una aproximación (uno de los medallistas fields del año pasado ha trabajado en el problema de si un problema genérico Np puede poseer soluciones aproximadas por un algoritmo que se ejecute en tiempo polinomial) y parece (como ya dije) que la paradoja de la información sugiere un nuevo tipo de computabilidad para la naturaleza.

        Susskind está hablando de esto http://arxiv.org/pdf/1509.07876.pdf

        A los lectores del blog de Francis: ¿Hay procesos no computables en la naturaleza?

  2. No está demás poner los enlaces a las entradas de francis sobre el problema del salto de masa:

    Los conceptos de campo, partícula virtual y vacío
    https://francis.naukas.com/2012/08/15/los-conceptos-de-campo-particula-particula-virtual-y-vacio/

    Confusiones típicas de los físicos en el problema del salto de masa en teorías de Yang-Mills puras
    https://francis.naukas.com/2012/08/14/el-problema-del-salto-de-masa-en-las-teorias-de-yang-mills-puras-y-la-masa-de-los-gluones/

    Oscar Prada y el salto de masa en teorías Yang-Mills:
    https://francis.naukas.com/2011/06/02/me-ha-defraudado-oscar-garcia-prada-en-su-charla-sobre-la-existencia-de-yang-mills-y-del-salto-de-masa/

    Conexión, curvatura y la geometría diferencial de las teorías de Yang-Mills
    https://francis.naukas.com/2012/08/16/conexion-curvatura-y-la-geometria-diferencial-de-las-teorias-de-yang-mills/

  3. Creo que en divulgación no deberíamos mentar, como siempre acabamos haciendo, la similitud con las sentencia «esta frase es falsa» para hablar de la demostración de Turing como es el caso aquí, o de la incompletud de Gödel. Esto crea malos entendidos, y los más graves se dan en la comprensión de incompletud de Gödel.
    Los legos en la materia que no profundizan, suelen interpretar que al final Turing o Gödel urgieron alguna especie de entelequia lógica para que se negara a sí mismo aquello que querían refutar; de forma que llegan a la conclusión de que no demostraron nada que tuviera repercusión fuera de su propio contexto.

    Gödel: «Yo no soy demostrable». Turing: «Yo no soy decidible» Muy distinto a «a esta frase es falsa».

      1. Sí, sí la conozco. Parte de un programa capaz de resolver la parada. y crea otro, aprovechando éste, con el que se llega a una paradoja, ergo tal programa universal no es posible. Cierto, ayer se me fue la olla y puse justamente lo que quería decir que se debería de evitar, el que se piense que la demostración solo concluye que un programa así no podría examinarse a sí mismo. La noche me confundió. Suerte que has contestado. Gracias.

  4. Fijaros como Luboš Motl (en el enlace que expone Francis) utiliza a Cantor para retirar del mundo físico el problema de la parada de Turing, pero ¿realmente la demostración de Turing precisa de un infinito en acto? Por un lado la idea básica es perfectamente soportable en un infinito potencial clásico «No importa qué programa de tipo «Termina» hagas, yo siempre podré hacer uno que lo burle», pero es que además, si en nuestro universo hubiera un límite en las palabras que soportara un algoritmo, entonces, el hipotético programa «Termina» tendría que ser ligeramente mayor, luego no existiría.

    Luboš se tira medio artículo hablando de la paradoja del mentiroso; quiere convencernos de que la demostración de Turing (y también la de Gödel) es una especie de autonegación, y no es así.

    1. Pedro:

      Creo que esta discusión es muy relevante, me parece oportuno que cites a Molt, me gustó su entrada. Pienso que tiene razón y que en la naturaleza no deben ocurrir procesos

      Sobre la prueba de Turing del segundo problema de Hilbert me gustaría debatir, pues ciertamente yo estoy seguro de que se necesita un argumento «tipo corte diagonal» a la Cantor para demostrar que no es descidible el problema de la parada y por consiguiente el uso del infinito es obligado.

      Sobre si en el universo hay un límite de computabilidad y compresión de una secuencia de caracteres en un determinado espacio físico… al parecer los hay, la cota de Bousso es de alguna manera un límite a la compresibilidad de la información en una región del espacio, y sobre la computabilidad hay una cota llamada el límite de Bremermann.

      ¿Qué piensas Pedro?

      Algunos comentarios:

      Es posible que algún día el concepto de número tenga una relevancia mucho mayor a la que ha tenido hasta el momento en la física, los números reales «son feos» en el sentido de que precisan del infinito, de la propiedad de ser no numerable, de muchas propiedades no constructivas, de no computabilidad y un incómodo etc.

      De cualquier manera que misterioso es que estas entidades nos regalasen todo lo que tenemos hasta ahora ¿Llegará el día en que necesitemos algún otro tipo de objeto?

  5. Ramiro, yo no creo que necesitemos el infinito en acto por lo siguiente. El problema de la parada de Turing, es un problema físico real, totalmente real, y lo vemos en el día a día, por ejemplo, no podemos hacer un antivirus perfecto (capaz de averiguar a 100% lo que va a hacer otro programa leyendo su código), porque siempre se puede aprovechar nuestro antivirus para hacer un virus que lo esquive, y el fondo de la cuestión es la parada.
    Ahora bien, si es un problema de la realidad, pero para demostrarlo necesitamos el infinito en acto, el cual, hasta donde sabemos hoy en día, no existe en la naturaleza ( y además es un axioma basado en la intuición, no tiene demostración previa), ahí hay algo que no me cuadra…¿es el infinito en acto una buena herramienta para la realidad? Si lo es, entonces no tiene razón Molt, porque estas cosas afectan a la naturaleza, y si no lo es, pues la demostración de Turing no nos sirve…a no ser, que nos olvidemos de querer darle el toque místico Cantoriano que a mi entender no le hace ninguna falta a la demostración de Turing.

    Por otro lado, fíjate, Ramiro, que el problema de la parada tiene también un fondo, y es el de la imprecisión…se ve más claro en el caso de los virus y los antivirus, el problema más grande es preguntarse ¿qué es un virus? ¿en qué momento puedo decir que un programa es malicioso o no? Con la parada pasa lo mismo si lo piensas detenidamente.

    Tienes toda la razón de que los números reales nos han dado atajos muy buenos aunque no llegamos a verlos en el mundo físico ¿habrá números complejos en la naturaleza? ¿existirán otro tipo de objetos que no sean los números, o más radical, habrá algo distinto de las matemáticas que sea más apropiado usar y no somos capaces de ver?

    Te aconsejo que le eches un vistazo a los videos de youtube y escritos del profesor N J Wildberger (pon en google njwildberger y te sale todo lo referente a él). Es un hiper constructivista anti infinito en acto, anti «números reales» y anti «conjuntos», etc…. Cuidado que no es un idiota ni un troll; es un profesor respetado en su universidad de Sydney que enseña número reales y enseña a Cantor y todo correctamente, pero sus investigaciones están centradas en construir todo a base de números racionales. Vale la pena leer y ver estos «extremos» para sacar conclusiones más «centradas»; a mí me ha cambiado muchos puntos de vista.

    1. Pedro:

      Todo lo que suscita la discusión de la computabilidad y la teoría de la información en la física es extremadamente emocionante que bueno que usted lo vea, es muy emocionante lo que está pasando con la paradoja de la información y con esas ideas de pensar en la física como computación, lo sea o no esto está genial.

      Recomiendo este escrito de Wilzeck hablando sobre como imagina la física en cien años
      http://arxiv.org/pdf/1503.07735v1.pdf

      Spoiler: Imagina la mecánica cuántica como una simetría, deducida a partir de la teoría de la información, imagina que los principios variacionales tendrán una conexión con la teoría de la complejidad y ese nexo será enseñado en cursos elementales, ordenadores cuánticos etc. vale la pena

      1.- Sobre el infinito en el mundo físico: me parece que es una discusión filosófica ¿No os parece a usted?, creo que el infinito está presente en nuestras teorías modernas (En el concepto de campo, variedad riemmaniana etc.) aunque por supuesto siempre se puede argumentar que lo que tenemos son teorías efectivas (Molt tiene un post sobre escenarios discretos para el espaciotiempo en gravedad cuántica y los tacha de «aburridos»)

      2.- Voy a leer el enlace que adjunta sobre los virus me parece interesante pero no termino de entenderlo, lo leo y comento.

      3.- Que curioso que mencione a Wildberger. Yo tomé dos de sus cursos (topología algebraica, geometría diferencial), vi alguna vez sus videos de trigonometría racional y son fan.

      Sobre ello quiero decir que al principio me parecía que era evadir lo inevitable pues sobre todo en el curso de geometría me parecía artificial como evadía la aparición de pi y porque de alguna manera muchos teoremas los prueba aproximando «tanto como sea posible» determinada cantidad lo cual me daba a entender que en el fondo podía introducir cortaduras de Deedekind en cualquier momento y no estaba haciendo la gran cosa. Solo evitar lo inevitable…

      Ahora lo veo diferente 🙂 y me encanta recomendarlo pues sus técnicas geométricas y de análisis pueden generalizarse a cualquier campo en cualquier característica, a mi me mola eso de la trigonometría racional y aunque de ninguna manera va a convencer al mundo de dejar de usar reales es refrescante ver como puedes capturar la noción de variedad, (co)homología etc. desde una contraparte racional. En verdad me encanta 🙂

      1. Hola Ramiro,

        Efectivamente estoy de acuerdo en que el tema del infinito no entra dentro del estudio de las ciencias naturales hoy por hoy, pues no tenemos evidencias a donde agarrarnos. Son idealizaciones y tenemos que ser cautos, por eso no me gustan mucho a la hora de tratarlos en los temas físicos.

        Para el tema de los virus mírate el teorema de Rice, del mismo se deriva que no es posible hacer un programa que examinando a cualquier otro (examinando su código, no reproduciéndolo) pueda determinar si realiza alguna acción no trivial. De ahí que los antivirus más cañeros funcionen a base de reproducir los posibles softwares maliciosos en entornos seguros.

        Con el tema de Pi, efectivamente parece artificial cuando intentamos evadirlo, pero date cuenta de algo que no pensamos nunca, y es que se necesita el infinito en acto para poder hablar de PI… Explicado de otra forma, si vemos el problema desde el punto de vista del infinito en potencia, al tener infinitos decimales es como si no importara cuantas divisiones le hiciéramos a la recta real, el punto nunca cae en ninguna…es decir, el número empieza como “3,1”, así que PI está entre “3,1” y “3,2”, por lo tanto dividimos ese tramo en 10 partes iguales, como sabemos, el número PI está entre “3,14” y “3,15” así que volvemos a dividir ese tramillo en 10 partes, ahora vemos que el número cae entre “3,141” y “3,142”…y volvemos a dividir, y volvemos a dividir, y volvemos a dividir…, el número PI, entonces, siempre estará en medio de ninguna parte, parece una especie de entelequia producto de empeñarnos en comparar el perímetro de la circunferencia usando cono unidad el radio o viceversa… Es decir, intentar esquivarlo no es menos decepcionante que acogerlo. Pero lo que está claro es que gracias a PI hemos avanzado mucho en el conocimiento de la naturaleza, de eso no hay duda, es un atajo enorme.

  6. «Esta frase es falsa».

    Desde los tiempos de Socrates, hace mas de 2000 años, se viene hablando de lo mismo. Los problemas y limitaciones del lenguaje, esa herramienta defectuosa, o inadecuada, que usamos para pensar y comunicarnos.
    Socrates examino a fondo la cultura de sus contemporáneos, y comprobó lo huecos y superficiales que eran sus conocimientos. Podría decirse que era un barniz de conocimientos, pero nada que revelara un todo coherente.
    Para los que no conozcan la historia de la discusión entre Socrates el sofista Hipias, les dejo un resumen.

    El sofista Hipias era el prototipo del «erudito»: Un «todologo», como diríamos actualmente. Sabia de todo un poco, pero en la realidad no había profundizado de verdad en ningún tema.
    Por el contrario, Socrates dedico su vida a desenmascarar a estos farsantes de sabiduría aparente y frases sin sentido. Bueno, así termino también, bebiendo la cicuta…
    Volviendo a la historia, la cuestión es que Hipias decía la frase sobre que «el que hace el mal sin intencion, tiene menos culpa que hace el mal sabiendo lo que esta haciendo».
    Socrates, mediante un razonamiento que a primera vista parece lógico, le demostró que esta frase era, aunque ustedes no lo crean: ¡falsa!.
    Hipias no acepto el triunfo de Socrates. Según el, había ganado con preguntas capciosas.
    Socrates le contesto humildemente que el tampoco podía creer que a través del pensamiento y la razón, los hombres comunes como el se consideraba, y los supuestos sabios, como eran Hipias y el resto de los sofistas, pudieran equivocarse tan dramáticamente haciendo uso de lo mas preciado y vanagloriado del ser humano, su mente racional.

  7. Pedro, Ramiro. En la materia Lógica y Computabilidad, dictada en la Facultad de Ciencias Exactas y Naturales de la Universidad de Buenos Aires dábamos (dejé de trabajar allí en el 2014) una demostración muy elegante de la existencia de programas que no pueden terminar en un número finito de pasos. Incluso, la demostración era constructiva. No usaba ni infinitos, ni tercero excluído, ni ningún equivalente al Axioma de Elección. En resumen, era aceptable para la Lógica Intuicionista. La demostración era una variación de la de Gödel (aunque para estar 100% seguro debí haber leído sus originales y no es el caso), pues no usaba el Teorema Chino del Resto. Definíamos como computable a un programa que se pudiera programar en S. El lenguaje S es equivalente a la máquina de Turing. ¿Cuáles eran los pasos permitidos por S? Las entradas en S son números naturales. Hay 4 instrucciones permitidas: i) sumar 1; ii) La resta truncada por 1 (es decir, si n>0 le asigno n-1 y al 0 le asignamos el 0; iii) «go to» (pues cada línea de código está numerada y iv) A n asignar n. Cada programa tiene un único número natural (es decir, se numera) y cada número natural corresponde a un único programa. En S las variables están numeradas. La instrucción iv) puede parecer tonta, pero gracias a ella tenemos una biyección explícita entre el conjunto de los números naturales N y el conjunto de programas en S, con lo cual N pasaría a ser el conjunto de números de programas de S. Si definimos Halt(x;y) «el programa de número y con entrada x» = 1 si termina y 0 sino, se puede probar (nuevamente, de forma explícita, sin usar ni Axioma de Elección ni tercero excluído ni nada prohibido por la Lógica Intuicionista), que el programa Halt(x;y) (recordad que tanto x como y son números naturales) no es computable. La materia estaba a cargo tanto del Departamento de Matemática (que la dictaba los primeros cuatrimestre de cada año) como del Departamento de Computación (que la dictaba los segundos cuatrimestres de cada año). Ya pasaron muchos años, pero los años que dicté la materia, dejaba en su página pdfs y apuntes teóricos. Si aún siguen estando allí, pueden ver esbozos más detallados de lo que acabo de escribirles.
    Saludos

Deja un comentario