lunes, 23 octubre, 2017

La prueba de Turing


me arde la cabeza de querer cantaros con el exceso
de expresión de todas mis sensaciones,
con un exceso contemporáneo de vosotras, ¡oh máquinas! 

Fernando Pessoa, bajo el heterónimo de Álvaro de Campos

Máquina de calcular de Leibniz de 1694

Máquina de calcular de Leibniz de 1694

Leibniz fue un extraordinario pensador racionalista al que se considera el último sabio universal por sus contribuciones punteras en multitud de campos del saber científico, matemático y filosófico. Comparece en este artículo porque creó una calculadora mecánica y fue el primero en preguntarse por lo que hoy se conoce como «el problema de la decisión». Es sencillo explicar en qué consiste: se trata de ver si se puede responder con un sí o un no a una pregunta. Cuando desconocemos si la respuesta es afirmativa o negativa, entonces nos encontramos ante lo que los lógicos denominan «un problema indecidible». Al parecer, Leibniz ya acariciaba la idea de construir una máquina que fuera capaz de procesar símbolos.

Si un lógico dice que un problema es «decidible» está refiriéndose a que existe alguna clase de algoritmo que lo resuelve. Desgraciadamente, no siempre es suficiente con saber que un problema tiene solución. Dentro de los problemas decidibles los lógicos distinguen entre los tratables y los intratables, según el tiempo que haga falta para proporcionar una respuesta.

Pongamos algunos ejemplos. Examinemos en primer lugar un problema decidible: Dado un número cualquiera, podemos responder afirmativamente a la pregunta de que existe un número primo mayor que la cantidad en cuestión, sea ésta cual sea. Cuanto mayor es el número de partida, más tiempo nos llevará encontrar el número primo, pero sabemos con total seguridad que algún día alguien será capaz de proporcionar la respuesta.

El matemático noruego Viggo Brun

El matemático noruego Viggo Brun

Para poner un ejemplo de un problema indecidible, hablemos brevemente primero de los primos gemelos, que son aquellos que se diferencian en dos unidades. Por ejemplo, 5 y 7, o bien 11 y 13, o bien 17 y 19 son primos gemelos. Pues bien, se desconoce a matemática cierta —aunque se sospecha que así es— si hay infinitos primos gemelos, y por tanto la cuestión de si existe una pareja de primos gemelos mayor que un número dado es indecidible por el momento. En relación con esto, en 1919 el matemático noruego Viggo Brun demostró uno de esos resultados que lo llevan a uno a mirar las matemáticas y a los matemáticos con veneración: La suma de los inversos de los primos gemelos converge hacia un número que recibe su nombre —la constante de Brun— y que resulta ser aproximadamente 1,902216.

El cálculo del quíntuplo de un número es un problema decidible y que podemos considerar tratable ya que si se tiene paciencia y se deja de mirar constantemente el móvil, cualquiera es capaz de multiplicar por cinco un número. Exponenciar enseguida se convierte en intratable ya que por ejemplo alcanza los noventa y un dígitos cuando se calcula 2300, y seiscientas veintitrés cifras cuando se calcula 300300. El cálculo del factorial (esto es, el producto de un número por todos los inferiores hasta uno, por ejemplo, factorial de 5 es igual a 5x4x3x2x1=120) para un número como 300 —es decir, 300 x 299 x … x 3 x 2 x 1— tiene la friolera de setecientas cuarenta y cuatro cifras.

El matemático alemán David Hilbert

El matemático alemán David Hilbert

Estos números son monstruosos. Hagamos un pequeño cómputo para que el lector de la mirada infinita se haga una idea: se estima que en el universo hay 100.000 millones de galaxias —es decir 1011 en notación científica—, cada una de las cuales posee aproximadamente otras tantas estrellas, luego el número total de soles es de 1011x1011=1022, o lo que es lo mismo, un uno seguido de veintidós ceros. Si se toma como masa de una estrella la cantidad de 2×1033 gramos, el peso del universo está en torno a los 2×1055 gramos, cada uno de los cuales está constituido por 6×1023 protones y neutrones, cuyo número total es, por tanto, 1,2×1079. Por tanto, el universo contiene una cantidad de protones y neutrones que puede expresarse mediante un número de setenta y nueve cifras, y es por ello muchísimo más pequeño que los que hemos comentado en el párrafo anterior.

El matemático ruso Yuri Matiyasevich en un retrato de 1969

El matemático ruso Yuri Matiyasevich en un retrato de 1969

Cada vez que un matemático resuelve un problema importante convierte un problema indecidible en decidible. El insigne David Hilbert planteó en 1900 a la comunidad matemática mundial veintitrés problemas no resueltos a la sazón. El décimo puede enunciarse como sigue: dada una ecuación con coeficientes enteros, ¿cuándo admite solución entera? Por ejemplo, la ecuación x2+y2=13 admite la solución x=2 e y=3. A los setenta años de su formulación, el gran matemático ruso Yuri Matiyasévich consiguió demostrar que no existe un algoritmo que permita saber si una ecuación de coeficientes enteros —llamada ecuación «diofántica» en honor de Diofanto de Alejandría— admite solución entera, y por tanto, un problema indecidible se convirtió en decidible.

 

ALAN TURING, LA MANZANA Y LA INFORMÁTICA

Sello dedicado a Alan Turing

Sello dedicado a Alan Turing

Alan Turing fue un insigne matemático británico que está considerado como uno de los padres de la informática y un pionero de la inteligencia artificial. Tuvo un papel muy destacado en la Segunda Guerra Mundial porque fue capaz de descifrar «Enigma» —la avanzadísima máquina criptográfica del ejército alemán—, lo que permitió interceptar las comunicaciones de la Wehrmacht. Toda la información relacionada con el modo en que Turing realizó sus investigaciones ha sido secreta hasta época relativamente reciente ya que, según algunas fuentes, los británicos sabían de antemano que Coventry iba a ser aniquilada por la Luftwaffe y no dieron orden de evacuar la ciudad para que la jerarquía nazi no sospechara que sus comunicaciones estaban siendo espiadas por la Inteligencia británica.

Steve Jobs y el logo de Apple

Steve Jobs y el logo de Apple

Su vida concluyó de manera incomparablemente triste: Arnold Murray, su amante, ayudó a un cómplice a cometer un robo en casa del propio Turing, quien denunció el delito ante la policía. En el curso de la investigación, salió a relucir la homosexualidad del matemático, que fue acusado de indecencia y perversión sexual, ya que en esa época la homosexualidad era ilegal en el Reino Unido. Turing consideró conveniente no defenderse en el juicio y fue condenado. Se le dio a elegir entre ir a prisión o someterse a castración química. Optó por esta segunda alternativa, lo que dio lugar a importantes transformaciones en su cuerpo —obesidad, aparición de pecho, pérdida de libido—. A los dos años del juicio, mordió una manzana envenenada con cianuro —lo que, al parecer, inspiró el logo de Apple— y perdió la vida.

Estatua dedicada a Alan Turing

Estatua dedicada a Alan Turing

La influencia de Turing en la lógica y en la informática del siglo XX ha sido colosal. En el congreso matemático de 1900, Hilbert había planteado si las matemáticas eran decidibles, esto es, si cualquier cuestión matemática podía probarse como verdadera o falsa mediante un proceso deductivo. La fascinante y visionaria respuesta de Turing llegó en su genial artículo de 1936 «On computable numbers», donde presentaba la que desde entonces se conoce como «máquina de Turing», un dispositivo mecánico antecesor de los modernos ordenadores programables.

Placa conmemorativa de Alan Turing

Placa conmemorativa de Alan Turing

La máquina hipotética descrita por el pensador británico consistía en un ingenio capaz de procesar una cinta consistente en celdas sucesivas donde se podía escribir y leer símbolos de manera secuencial. Disponía de un cabezal que leía las celdas e iba avanzando o retrocediendo a las celdas adyacentes según las instrucciones escritas en la cinta que el cabezal interpreta. La máquina de Turing realizaba su tarea consistente en interpretar la cinta y en ejecutar las instrucciones hasa que se quedaba sin tareas pendientes y se detenía.

Con ayuda de esta máquina conceptual —que en esencia se comporta como un microprocesador—, Turing consiguió responder de manera negativa al reto de Hilbert empleando un razonamiento por reducción al absurdo que omitiremos: Existen proposiciones acerca de cuya verdad o falsedad es rigurosamente imposible pronunciarse.

 

¿PUEDEN PENSAR LAS MÁQUINAS?

En 1950, Alan Turing encabezó el emocionante artículo «Computing Machinery and Intelligence» —que el lector de la mirada infinita puede encontrar aquí— con la frase «¿Pueden pensar las máquinas?». ¡Por primera vez en la historia alguien intentaba caracterizar el pensamiento no humano! Turing daba una respuesta que sigue siendo aceptada en la actualidad: una máquina piensa si un observador no es capaz de detectar que quien responde es una máquina. El filósofo británico aseguró que harían falta al menos cincuenta años para que una máquina superase con éxito su prueba, lo que llevó al escritor Arthur C. Clarke a darle el título de «2001» a su célebre novela.

El matemático italiano Giuseppe Peano

El matemático italiano Giuseppe Peano

En su artículo, Turing examina nada menos que nueve posibles objeciones a su tesis de que algún día todo lo que somos capaces de hacer los seres humanos, incluido pensar, podrá ser realizado por máquinas. De ellas —para no extender el artículo— sólo vamos a detenernos en dos: la objeción teológica y la objeción matemática. Los que defienden que Dios ha otorgado únicamente al hombre la facultad de pensar olvidan que Dios, en Su omnipotencia, podría otorgar la facultad de pensar a un elefante —«He has the freedom to confer a soul on an elephant if He sees fit», leemos—. Sostiene Turing que al crear una máquina pensante en absoluto estaríamos usurpando la facultad de Dios de crear almas en mayor medida que lo estamos en el transcurso de la procreación de nuevos seres humanos. Tanto en un caso como en otro somos instrumentos de Dios que procuramos una casa a la nueva alma creada por Él.

El filósofo, matemático y lógico austriaco Kurt Gödel

El filósofo, matemático y lógico austriaco Kurt Gödel

La objeción matemática tiene que ver con los sensacionales dos teoremas de incompletitud de Gödel que delimitan lo que puede ser pensado en el contexto de sistemas de cierta complejidad, como por ejemplo la aritmética de Peano —que es la que nos enseñan de pequeñitos en el colegio—. Turing señala que esta objeción imposible de superar atañe tanto a los seres humanos como a las máquinas, de modo que no es una verdadera objeción.

 

EL PROGRAMA EUGENE

Interfase de usuario del programa Eugene

Interfase de usuario del programa Eugene

A los sesenta años del trágico fallecimiento de nuestro ídolo, los profesores de la universidad de San Petersburgo Vladimir Veselov y Eugene Demchenko han creado el programa informático Eugene que se ha hecho pasar ante unos observadores por un muchacho de trece años. Su éxito no es completo, ya que sólo consiguió convencer al jurado en un 33% de las pruebas realizadas. Hay más considerandos: el supuesto muchacho era de nacionalidad ucraniana, con lo que su dominio del idioma inglés en el que se realizaban las pruebas era un tanto precario. Sin embargo, y esto es muy importante, no había limitación en los temas que eran objeto de examen, con lo que una tasa de un tercio de aciertos en una prueba de estas características es un resultado histórico.

Eugene Vladimir Veselov

Eugene Vladimir Veselov

Mi proyecto fin de carrera —acabado hace unos veinticinco años— trató sobre inteligencia artificial, y debo confesar que lo que mi pobre cabeza pudo llegar a comprender de esta rama del conocimiento humano me resultó un tanto decepcionante, aunque quizá esté siendo injusto y en realidad el modo adecuado de expresar mi pensamiento en esta materia sea decir que desde entonces admiro infinitamente la capacidad de la mente humana, dado lo difícil y lo precario que es implantar razonamientos semejantes a los nuestros en programas informáticos. Es de suponer que en años sucesivos los investigadores consigan poner a punto nuevos algoritmos que vayan pareciéndose cada vez más a lo que somos capaces de razonar los hijos de Eva, y eso abra la puerta a posibilidades maravillosas que a día de hoy no pasan de ser meras especulaciones.

Sin embargo, con frecuencia lo que verdaderamente buscan las empresas, los estados, los ejércitos, y buscamos las mujeres, los hombres, los padres, los hijos es justamente lo contrario de lo que pretendía Alan Turing: que los seres humanos sean tan fiables como lo son las máquinas. Queremos a nuestro lado gente que no falle, y quien tiene la reputación de funcionar en toda circunstancia es la máquina.

Caricatura de una máquina de Turing

Caricatura de una máquina de Turing

¡Pero el cuerpo es también una máquina!: Nuestras articulaciones, nuestros músculos y huesos, nuestros sistemas circulatorio, digestivo, renal o respiratorio son un formidable mecanismo que funciona razonablemente bien a lo largo de toda una vida. Nuestro cerebro también es capaz de realizar tareas matemáticas, lingüísticas, lógicas, artísticas y verbales, entre otros muchos prodigios. ¿Entonces por qué nos vemos menos fiables que las máquinas, pese a que las máquinas también fallan y nosotros tenemos mucho de máquinas? Quizá la respuesta a estos sofismas se reduzca a reconocer que la esencia humana es la imperfección y el fallo, y nuestra admiración por lo que no falla casi nunca, aunque sea pequeño, nos lleva a olvidar lo inmensos que somos.

El hombre es lo que podría ser perfecto.

Álvaro Fierro Clavero
www.alvarofierro.com

Comentarios

  1. Pura Sanjuán dice:

    Me gustaría tener tiempo para leer “casi todos” tus artículos
    Respecto a este, por el momento, solo señalar un errorcillo:
    “Cada vez que un matemático resuelve un problema importante convierte un problema indecidible en decidible. El insigne David Hilbert planteó en 1900 a la comunidad matemática mundial veintitrés problemas no resueltos a la sazón. El décimo puede enunciarse como sigue: dada una ecuación con coeficientes enteros, ¿cuándo admite solución entera? Por ejemplo, la ecuación x2+y2=13 admite la solución x=2 e y=3. A los setenta años de su formulación, el gran matemático ruso Yuri Matiyasévich consiguió demostrar que no existe un algoritmo que permita saber si una ecuación de coeficientes enteros —llamada ecuación «diofántica» en honor de Diofanto de Alejandría— admite solución entera, y por tanto, un problema indecidible se convirtió en decidible”.

    indecidible se convirtió en decidible: Debe ser al revés, ¿no?

    Un saludo

    Pura Sanjuán
    sanjuanpm@gmail.com

    • No: se desconocía si el problema tenía o no solución, y Yuri Matiyasevich zanjó la cuestión y demostró que no existe el algoritmo que se buscaba. Un problema indecidible se convirtió en decidible, en sentido negativo. Gracias por el interés.

  2. Excepcional artículo. Uno no para de aprender. Gracias, Álvaro.

  3. Gabriel Alamo dice:

    Me ha gustado mucho tu articulo. Se nota, antes que lo descubras, tu gran interés por el tema.

Deja un comentario