El Gato de Turing

Esta entrada fue publicada originalmente en Naukas.


Entre los gatos más famosos de la historia, el primer puesto es indiscutiblemente para un gato que todos los de mi generación reconocerán: “¡Es cierto, es cierto, vi un lindo gatito!”


Me pareció ver un lindo gatito…

Igual me estoy dejando llevar por mis preferencias subjetivas. Lo cierto es que hay otros muchos gatos bien famosos: el Gato con Botas, el Gato de Cheshire, Tom (y Jerry), Garfield… Pero, entre los científicos, el que se lleva la palma es el Gato de Schrödinger, un gato hipotético que puede estar simultáneamente vivo y muerto como resultado de la superposición de estados cuánticos.

Pero hoy no quiero hablar de ninguno de estos, sino de uno que, según mis noticias, se presenta por primera vez aquí en sociedad: el Gato de Turing. Sea un gato encerrado en una caja…


Lo cierto es que no me consta que Turing tuviera un gato,
aunque dicen que el Gato de Cheshire aparece cuando quiere en las casas inglesas

Algoritmos y computabilidad

El siglo XX comenzó para las matemáticas con el intento de fundamentarlas en la lógica formal. El monumental esfuerzo realizado por Bertrand Russell y Alfred N. Whitehead en sus Principia Mathematica, no obstante, quedó ensombrecido en 1931 por el teorema de Kurt Gödel sobre la incompletitud de las matemáticas: existen proposiciones verdaderas en la aritmética que no se pueden demostrar mediante la aplicación formal de reglas deductivas. La cuestión estaba estrechamente relacionada con el Entscheidungsproblem (problema de la decisión) enunciado por David Hilbert en 1928: ¿existe algún método definido mediante el cual sea posible decidir si una proposición matemática cualquiera es demostrable?

Alan Turing respondió negativamente a esta pregunta en su famosísimo artículo de 1936, que puede considerarse la piedra fundamental de la informática moderna: Sobre los números computables, con una aplicación al Entscheidungsproblem [1]. En este artículo Turing define en qué consiste ese “método definido”, que él denomina “computación efectiva”, y que corresponde a la noción moderna de algoritmo:

(i) un procedimiento basado en reglas
(ii) que obtiene el resultado deseado
(iii) en un número finito de pasos.

El énfasis estaba en ser un proceso metódico y automático, basado en reglas extremadamente simples, ejecutadas “mecánicamente” en su máquina calculadora universal (posteriormente conocida como Máquina de Turing), con lo que se establecía un puente entre los conceptos teóricos y su implementación en máquinas que funcionasen conforme a las leyes físicas. De modo completamente determinista, por cierto. Su Máquina Universal, siendo ficticia, era a la vez una ilustración de su noción de computabilidad y un prototipo conceptual de una máquina física que, en principio, podía ser construida.

Frente a la aproximación de Alonzo Church para resolver este mismo problema (que publicó de modo independiente unos meses antes que Turing), y la variante cercana de Emil Post (también de 1936), el enfoque de Turing tiene la ventaja de ser más intuitivo, más “ingenieril”. La contribución esencial de ellos tres (estrechamente conectada con el teorema de Gödel) es que hay funciones perfectamente definibles en términos matemáticos cuyo resultado, sin embargo, no se puede obtener metódicamente, en un número finito de pasos, mediante la aplicación mecánica de reglas o instrucciones. Por decirlo brevemente, hay computaciones no computables, y, de modo general, no podemos saber a priori cuáles son computables y cuáles no (técnicamente se dice que es una cuestión indecidible). Ésta es la esencia de la que hoy se conoce como Tesis de Church-Turing [2].

Determinismo y predecibilidad

Pues bien, la tesis tiene implicaciones para la cosmovisión determinista del universo. El determinismo clásico afirma que el estado actual del universo es el efecto del pasado y la causa del futuro. Tal como fue enunciado por Pierre Simon de Laplace en 1814 en su Ensayo filosófico sobre las probabilidades [3], el determinismo incluía la “predecibilidad” como elemento esencial: un intelecto que conociera perfectamente el estado presente podría predecir el futuro hasta en sus más mínimos detalles:

Podemos considerar el estado actual del universo como el efecto del pasado y la causa del futuro. Un intelecto que en un momento dado conociera todas las fuerzas que animan la naturaleza y las posiciones de todos los seres que la componen, si fuera tan vasto como para analizar estos datos, podría condensar en una sola fórmula el movimiento de los mayores cuerpos del universo y el del átomo más ligero; para tal intelecto nada podría ser incierto y el futuro tal como el pasado estaría ante sus ojos.

El determinismo laplaciano había sufrido un duro revés con la Mecánica Cuántica, que niega la posibilidad de conocer con absoluta certeza la posición y velocidad de un cuerpo (principio de incertidumbre), y cuestiona además la causalidad perfectamente determinada de las interacciones físicas fundamentales (principio de indeterminación).

No obstante, sin necesidad de introducir el indeterminismo ni la incertidumbre en los niveles fundamentales de la naturaleza física, la Teoría de Sistemas Complejos de Henri Poincaré (que es el origen de la Teoría del Caos) ya había abierto una brecha irreparable en la predecibilidad, vista desde la física clásica determinista de finales del siglo XIX: en efecto, tal como demuestra Poincaré, alteraciones arbitrariamente pequeñas en el estado actual pueden conducir a diferencias arbitrariamente grandes en los estados futuros; es decir, el futuro determinista no es predecible. Derek Muller (Veritasium), uno de mis divulgadores favoritos, ofrece una magnífica explicación de la impredecibilidad del futuro en un universo estrictamente determinista en La ciencia del efecto mariposa.

Con una nueva vuelta de tuerca, la tesis de Church-Turing reforzará esta conclusión desde el punto de vista estrictamente formal de la Teoría de la Computabilidad: el futuro, incluso si está perfectamente determinado por leyes matemáticas, no es predecible (computable). Una inteligencia computacional no puede predecir un futuro determinista [4].

Por cierto, esto hace inviable la Ley Cero de la Robótica (añadida posteriormente a las tres primeras): “Un robot no hará daño a la Humanidad ni, por inacción, permitirá que la Humanidad sufra daño”. La ley es inviable precisamente porque el futuro es computacionalmente impredecible: el robot no puede saber si sus acciones tendrán buenas o malas consecuencias a muy largo plazo. Manuel Alfonseca y su equipo han desarrollado esta idea desde otro punto de vista [5]: una superinteligencia no puede ser ética, porque la necesidad de prever las consecuencias y actuar conforme a esa previsión para evitar determinados males viola la Tesis de Church-Turing: el problema del daño es indecidible.

Yet another Gedankenexperiment

Sí, otro experimento mental, uno más en una larga tradición. Sea un gato encerrado en una caja, y sea un frasco con veneno conectado a la caja mediante un tubito. Hay un martillo que romperá el frasco, liberando el veneno que matará al gato. Y el martillo es accionado por un dispositivo que se activa cuando una Máquina de Turing que ejecuta un programa arbitrario se detiene…

Voilà. ¿Se detendrá la Máquina de Turing? De modo general, no lo podemos saber a priori. Es decir, habrá programas que podemos saber que tarde o temprano se detendrán (por ejemplo, un sencillo programa que cuenta de 1 a 10). Y habrá programas que sabemos que no se detendrán nunca; es decir, como decimos coloquialmente, se “cuelgan”, entran en un bucle infinito (como un programa que cuenta de 1 a 10 y de 10 a 1 sucesivamente, sin parar, “rebotando” en los dos extremos). Pero, y en esto consiste la demostración magistral de Turing, de modo general no podemos saber a priori si un programa pertenece a la primera clase (los que se detienen) o a la segunda clase (los que no se detienen). Más específicamente, no podemos construir un programa que analice otro programa y prediga si se parará o no. No podemos saber, computacionalmente, si una computación terminará o no. Esto es, ni más ni menos, el Problema de la Parada.

Y como aquí estamos los humanos para hacer trastadas con el Universo, podemos llenarlo de Máquinas de Turing ejecutando programas arbitrarios, y logrando que la evolución futura del universo sea computacionalmente indecidible, es decir, impredecible. En otras palabras: aunque no tuviéramos ni sistemas caóticos ni mecánica cuántica, y el Universo fuera determinista, el futuro seguiría siendo impredecible (computacionalmente).

No sabemos qué pasará con el gato. Esperemos que no le haya molestado el experimento. Era solo mental.

Referencias

[1] Alan M. Turing (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2(42): 230–265.

[2] Jack Copeland (2017). The Church-Turing Thesis. Stanford Encyclopedia of Philosophy.

[3] Pierre Simon de Laplace (1814). Essai philosophique sur les probabilités. «Nous devons donc envisager l’état présent de l’Univers comme l’effet de son état antérieur et comme la cause de celui qui va suivre. Une intelligence qui, pour un instant donné, connaîtrait toutes les forces dont la nature est animée, et la situation respective des êtres qui la composent, si d’ailleurs elle était assez vaste pour soumettre ces données à l’Analyse, embrasserait dans la même formule les mouvements des plus grands corps de l’univers et ceux du plus léger atome: rien ne serait incertain pour elle et l’avenir, comme le passé serait présent à ses yeux.»

[4] Gonzalo Génova (2020). Alan Turing: el genio no computable. En Juan Arana (ed.), La cosmovisión de los grandes científicos del siglo XX. Madrid: Tecnos, pp. 97-108.

[5] Alfonseca, M., Cebrián, M., Fernández Anta, A., Coviello, L., Abeliuk, A., Rahwan, I. (2021). Superintelligence Cannot be Contained: Lessons from Computability Theory. Journal of Artificial Intelligence Research, 70:65-76.

Créditos de las imágenes

http://profesorbigotini.blogspot.com/2019/07/me-parecio-ver-un-lindo-gatito-es.html
https://blogs.elpais.com/turing/2013/06/el-problema-de-la-parada-de-los-programas-y-de-las-personas.html
https://es.wikipedia.org/wiki/Gato_de_Cheshire
https://pixabay.com/es/photos/gato-mascota-animal-gato-doméstico-6080824/

Agradezco a Javier G. su lectura previa y observaciones.

2 comentarios en “El Gato de Turing

Deja una respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Salir /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Salir /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Salir /  Cambiar )

Conectando a %s