El Año de Turing

El Año de Turing

La informática a la que recurrimos para tuitear o hacernos una resonancia magnética es en esencia Alan Turing, uno de los científicos más importantes de la Historia. Fue un hombre generoso que afrontó con genialidad lógica horrores como el Nazismo pero al que el mundo devolvió sólo injusticia. Acercamos su obra a los lectores para que comprueben lo importante que fueron sus aportaciones. Creó la Informática tal y como la conocemos.

De Blaise Pascal a Maurice Wilkes

ALBERTO PRIETO ESPINOSA

En la conmemoración del centenario del nacimiento de Alan Turing, muy merecidamente se han destacado las dotes de este extraordinario personaje. Me mueve a escribir estas líneas pensar que muchas personas erróneamente crean que la contribución europea al desarrollo de las primeras máquinas de calcular y computadores se circunscribe al loable trabajo de Turing; cuando ha habido otros pioneros, algunos coetáneos a él, que también destacaron por su inteligencia e imaginación en este campo. Voy a referirme básicamente a aspectos de ingeniería, a máquinas en sí, no a aspectos teóricos.

La historia reconoce que las primeras máquinas de calcular, basadas fundamentalmente en ruedas dentadas y engranajes, fueron desarrolladas en Europa, destacando las siguientes contribuciones:

  • Blaise Pascal (1624) ideó y construyó la primera calculadora mecánica para sumar y restar (Pascalina). La desarrolló para ayudar a su padre que era recaudador de impuestos de la alta Normandia, nombrado por el cardenal Richelieu.
  • Gottfried W. Leibnitz (Leipzig) en 1671 concluyó una máquina
    que, Aritmómetromediante el uso de cilindros escalonados, incluía por primera vez el producto y la división
  • Charles Xavier Thomas de Colmar (Francia) patentó 
    el 18 de noviembre de 1820 el Aritmómetro, que fue la primera calculadora de sobremesa capaz de realizar las cuatro operaciones básicas de forma sencilla y sin errores con resultados de hasta 12 cifras.

Mención aparte merece Charles Babbage que ideó en 1837 su Máquina Analítica, e introdujo conceptos fundamentales como:

  • Máquina AnalíticaLa definición de una estructura funcional para las máquinas de calcular: almacén (lo que hoy denominamos “memoria”), taller (en la actualidad “unidad aritmético-lógica”), y unidades de entrada y salida.
  • La noción de programabilidad de la máquina, por medio del
    encadenamiento automático de secuencias por medios
    mecánicos.

BrunsvigaEn 1982 la empresa alemana GNC (Grimme, Natalis & Co.) diseña la calculadora mecánica de sobremesa “dupla” Brunsviga, siendo de las más utilizadas en el mundo desde 1885 hasta la década de los 1950. En 1955 la empresa ocupaba a más de mil personas y hasta 1957 se fabricaron más de 500.000 de esas máquinas en varios modelos.

 El AjedrecistaDentro de los sistemas mecánicos de cálculo que se concibieron en aquella época conviene hacer referencia a la contribución del español Leonardo Torres Quevedo (1852-1936). En la línea de Babbage trabajó en la construcción de máquinas automáticas de cálculo analógico, siendo celebre su estudio sobre “máquinas algebraicas” que presentó en las academias de ciencias española (1893) y francesa (1900). En la Feria Mundial de Paris de 1914 presentó una máquina (El Ajedrecista) que jugaba automáticamente un final de rey y torre contra el rey de un oponente humano.  Siempre ganaba, pero no en un número mínimo de movimientos. El 6 de noviembre de 1915 en la revista Scientific American se citaba a este trabajo como "Torres and His Remarkable Automatic Device“.

Sin lugar a dudas dos de los europeos que más contribuyeron en el desarrollo de los primeros computadores fueron el alemán Konrad Zuse (1910-1995) y el inglés Maurice Wilkes (1913-2010). Zuse trabajó en la  Ford Motor Company y en la Henschel Aircraft Factory ubicadas en Berlin-Schönefeld. Su trabajo requería realizar muchos operaciones matemáticas a mano, lo que le llevó a proyectar sistemas automáticos de cálculo. Así, en  mayo de 1941 concluyó el Z3 que es considerado como el primer computador controlado por programa en funcionamiento. Este computador estaba proyectado para realizar cálculos aeronáuticos y no era de uso general, y utilizaba en su construcción relés de telefonía. Otro hecho notable es que era entre Konrad Zuse4 y 5 veces más rápido que el computador Mark I, concluido 3 años más tarde por  Howard T. Aiken en la Universidad de Harvard  con la colaboración de IBM. De 1943 a 1945 definió un lenguaje de programación de alto nivel que denominó Plankalkül  (“Plan de Cálculo”). Posteriormente construyó el Z4 que se convirtió en 1950 en el primer computador comercializado del mundo (un año antes que el UNIVAC I en Estados Unidos).

Desde un  punto de vista conceptual, la contribución de Sir Maurice Wilkes (Universidad de Cambridge) a la   arquitectura de computadores fue fundamental. En el verano de 1946  Wilkes asiste a un curso de verano sobre computadores electrónicos  impartido por Mauchly y Eckert en la Moore School (Filadelfia). Estos investigadores acababan de concluir el ENIAC, que puede considerarse como el primer computador electrónico del mundo. Durante esta estancia cae en sus manos el documento First Draft of a Report on the EDVAC donde John von Neuman proponía la idea de introducir los programas en una memoria como si fuesen datos y junto a estos (programa almacenable en memoria). Literalmente en una noche “devora” este documento (no había por entonces fotocopiadoras) que tenía que devolver con premura.

A su vuelta a Cambridge concibe el EDSAC que construye en tres años y, se adelanta al EDVAC, ya que ejecuta su primer programa el 6 de mayo de 1949. El EDSAC es considerado el primer computador operativo de programa almacenado. Algunas aplicaciones del EDSAC fueron:

  • 1950, resolución de ecuaciones diferenciales que modelan la frecuencia de generación de genes (primer uso del computador para resolver un problema en el campo de la biología)
  • EDSAC1951, obtención de un número primo de 79 dígitos.
  • 1952, desarrollo del primer videojuego del mundo: el tres en raya (OXO). La salida gráfica se obtiene en una pantalla de un osciloscopio (CRT).
  • 1960, recopilación de una serie de evidencias numéricas sobre las soluciones de las ecuaciones elípticas.

En 1951 Wilkes publica con David J. Wheeler y Stanley Gill el primer libro del mundo sobre programación de computadores “The preparation of programs for an electronic digital computer”. Personalmente opino que la contribución más notable a la arquitectura de computadores de Wilkes, que tuvo también lugar en 1951, fue el concepto de unidad de control microprogramada. Supuso una alternativa para el diseño de los computadores, y que para poner de manifiesto su ingenio paso a describir a continuación.

Una unidad de control tradicional o “cableada” (“hard-wired”) de un computador está constituida por componentes electrónicos interconectados (mediante cables o conductores) que generan las señales eléctricas de control para monitorizar el funcionamiento de los distintos elementos del sistema. Obviamente, un modelo de computador distinto a otro requiere de una unidad de control distinta con diferentes circuitos e interconexiones. La ejecución de una instrucción lleva consigo la generación por la unidad de control de una serie precisa y ordenada en el tiempo de señales de control binarias. Pues bien, la genial idea de Wilkes consiste en sustituir la unidad de control cableada por una memoria especializada (de control) que tenga almacenados los valores de las señales de control. El conjunto de valores de las señales de control correspondientes a la ejecución de una instrucción se denomina “microprograma”, diciéndose por ello que  estas unidades de control son microprogramadas.

Una unidad de control microprogramada es como si hubiese un computador de control dentro del  computador. Podemos pasar de un computador a otro sin más que cambiar los microprogramas almacenados en su memoria de control. Las ventajas que se obtienen son: facilidad de diseñar e implementar nuevos procesadores, posibilidad de que con una misma estructura hardware  se puedan emular distintas arquitecturas, facilidad de migración dentro de una serie de computadores, y computación reconfigurable. Hablando con rigor, cuando decimos que una persona debe de “cambiar el chip” deberíamos decir “debe de cambiar los microprogramas”, lo cual sería  mucho más sencillo de realizar.

El concepto de unidad de control microprogramada, ha sido ampliamente adoptado por la industria desde sus orígenes hasta la actualidad. Una gran parte de los procesadores de uso general actuales lo utilizan, así como sistemas más especializados como es el caso del co-procesador Reality de la Nintendo 64 o las unidades vectoriales VU0 and VU1 de la Sony PlayStation 2.

Maurice WilkesMe gustaría no concluir estas líneas sin relacionar la vida de Maurice Wilkes con la de Alan Turing. Los dos fueron coetáneos, es más, estudiaron un grado en matemáticas en la misma clase en la Universidad de Cambridge obteniendo exactamente las mismas calificaciones. Como confesó el propio Wilkes, posteriormente sus encuentros fueron ocasionales, eran plenamente cordiales aunque encontraba a Alan reservado en sus maneras, existiendo cierta rivalidad entre ellos. Turing fue un pionero de la computación teórica describiendo un computador sobre el papel, mientras que Wilkes construyó el primer computador operativo de programa almacenado del mundo y desarrolló conceptos de arquitectura y métodos de programación que aún hoy día se siguen utilizando. Otro contraste notable entre ellos: mientras Alan Turing vivió sólo 42 años (1954), Wilkes murió con 97 (2010). Curiosamente Maurice recibió el premio Alan Turing (considerado el Nobel de la Informática), en su segunda edición (1967).

En mi modesta opinión, el desarrollo de los computadores se ha producido, en gran medida, por la conjunción de: 1) la inventiva europea, 2) los medios y recursos de los Estados Unidos y 3) el poder de “asimilación y reproducción” asiático.

La Academia de Ciencias Matemáticas, Físico-Químicas y Naturales de Granada, en el centenario del nacimiento de Alan Turig organiza el ciclo de conferencias De Alan Turing a nuevos retos científicos europeos en procesamiento de la información, en la ciudad de Granada durante el mes de mayo. Más información puede encontrarse aquí.

Alberto Prieto Espinosa es catedrático de la Universidad de Granada.

Para las fotografías relacionadas con M. Wilkes, derechos de autor del Laboratorio de Informática de la Universidad de Cambridge. Reproducidas con permiso.

DAVID DE FRUTOS

RICARDO PEÑA

Toni HoareSir Charles Antony Richard Hoare, conocido inicialmente entre los informáticos como C. A. R. Hoare, y más coloquialmente como Tony Hoare, es uno de los científicos y académicos que más huella han dejado en nuestra disciplina. Recibió el Premio Turing en 1980, fue nombrado miembro de la Royal Society en 1982, y Sir por la Reina Británica en 2000. En su larga vida científica, ha sentado los fundamentos de muchas de las teorías y técnicas que hoy enseñamos en las facultades de Informática de todo el mundo, tanto a nivel de grado como de posgrado. Sus aportaciones han contribuido decisivamente a hacer de la programación de computadores una disciplina científicamente fundada, partiendo de una situación inicial en la que parecía más un arte, o un oficio artesanal, que una ciencia. Tony Hoare será investido Doctor Honoris Causa por la Universidad Complutense de Madrid el próximo 10 de mayo. Con estas líneas, queremos glosar su figura y su obra para que los informáticos más jóvenes y la sociedad en general conozcan más de cerca quién es este gran científico, y aprovechar la ocasión para invitaros a los distintos actos que se organizarán en nuestra Universidad con motivo de su visita.

Seguir leyendo »

JUAN JOSÉ MORENO NAVARRO

Es curioso cómo nos encanta hacer escalafones y listas de los mejores de lo que sea. Parece algo consustancial a la humanidad, pues los helenos ya eligieron las 7 maravillas del mundo antiguo. Las hay más sesudas y científicas usando indicadores supuestamente contrastados, como los ranking de universidades, tenistas, los países más turísticos o las 100 mejores películas. La mayor parte están basados en consultas estadísticas, a veces sólidas a veces informales. No hay periódico que no publique su ranking de hoteles, móviles, vídeojuegos, coches, series de televisión, etc.

Probablemente ya se haya estudiado esto sociológicamente de forma más científica, pero los ranking suponen una forma de simplificar, de dar un mensaje muy sencillo, quizás para evitarnos hacer pensar, quizás para orientarnos hacia qué pensar. Se usan como armas arrojadizas cuando interesa (como en el caso de las universidades) o se ignoran si los resultados no gustan (España es la novena del mundo en resultados de investigación, lo que no parece que sea coherente con el supuesto desastroso resultado de las universidades). Pero también sirven para provocar: dado un ranking, aparecen mil detractores y objeciones a las decisiones tomadas.

Todos, hasta los más serios, no pasan de ser un juego divertido y están cargados de subjetividad. Son por definición injustos: ¿cómo un cinéfilo puede elegir las mejores 10 películas con las cientos de obras maestras que hay? A la vez sirven para llamar la atención, como señuelo de popularidad. De hecho uno de los consejos que se dan para aumentar el impacto de un blog es publicar un ranking de cualquier cosa, da igual si es sensato o no: en el primer caso será visitado para informarse, en el segundo para descalificarlo. En este blog no vamos a ser menos y vamos a referirnos a uno de ellos de reciente publicación, que tiene el pedigrí de haber sido ideado por Stephen Hawking y está avalado por la Real Sociedad Británica (Royal British Society) y la Real Academia de Ingeniería del Reino Unido, así como el gobierno y los museos de ciencia británicos.

Seguir leyendo »

LLORENÇ HUGET ROTGER

Alan M. TuringAlan Mathison Turing (1912-1954), británico, y Claude Elwood Shannon (1916-2001), norteamericano,  figuran entre el elenco de pioneros de la informática, junto al húngaro John von Neumann (1903-1957). Matemáticos, los tres; Turing y von Neumann pusieron las bases para el desarrollo del ordenador y Shannon las de las tecnologías de la información.

Turing y Shannon tienen una trayectoria como matemáticos, en momentos convergentes y otros divergentes. Claude E. ShannonHabían trabajado, desde la lógica formal de Boole, en líneas complementarias sobre la computabilidad, como respuesta al Entscheidungsproblem (problema de decisión) formulado por Hilbert, en 1928 ¿son las matemáticas computables?, en el sentido de determinar si se puede diseñar un procedimiento mecánico mediante el cual, partiendo de una proposición, y con un número finito de pasos, se pueda concluir si esta proposición es verdadera o falsa.

Universidad de PrincetonTuring, en 1936, presenta su trabajo “On the computable numbers, with an Application to Entscheidungsproblem”, demostrando, con todo rigor, la imposibilidad de este proceso. En este artículo, Turing reemplaza el lenguaje formal basado en la aritmética de Gödel por el concepto de máquina de calcular, constituyendo la base de lo que hoy conocemos como “máquina universal de Turing” (su propuesta teórica tiene coincidencias con la teoría de la Massachusetts Institute of Technologyλ‐decibilidad, desarrollada por Alonzo Church en la Universidad de  Princeton). Casi en paralelo, Shannon, en 1937, demuestra en su tesis doctoral, que desarrolla en el Massachusetts Institute of Technology (MIT), que es posible expresar sentencias del álgebra de Boole mediante la combinación de relés y circuitos eléctricos.  Ésta significó una gran contribución  a la teoría de diseño de circuitos digitales.

En 1938, Shannon y Turing, construyeron, mediante circuitos eléctricos, un ordenador de propósito especial (bautizado como ZZ-1) para generar los harmónicos requeridos en la fórmula de Turing para el cálculo de la función zeta de Riemann.

Bletchley Park
Turing
y Shannon, durante la Segunda Guerra Mundial dedican su atención a la criptografía y al criptoanálisis. El primero juega un papel importantísimo en Bletchley Park, donde se consigue descifrar los mensajes cifrados por la máquina Enigma, usada por la marina alemana. Laboratorios Bell en Nueva YorkEl segundo, trabajó en Bell Labs de Nueva York donde, a partir del artículo A Mathematical Theory of Communication (1948), sienta las bases de la teoría de la información, y con el artículo  Communication Theory of Secrecy Systems (1949), pone las bases de la criptología moderna.


Por otro lado, John von Neumannvon Neumann, es el catalizador de los trabajos de Shannon y Turing  que ambos habían realizado, previamente, en el Instituto de Estudios Avanzados de la Universidad de Princeton,  y que ha llevado a consagrar la arquitectura de los ordenadores actuales como la arquitectura von Neumann, basada en programas almacenados en memoria, y desarrollada en los proyectos EDVAC y ENIAC, siendo éste el primer ordenador electrónico de propósito general.

Se podría decir que Turing y Shannon se sintieron poco interesados en el desarrollo de los ordenadores y experimentaron otras vías de investigación, coincidiendo otra vez, en su interés  por las máquinas que juegan al ajedrez.

Turing se adentró en estudiar teoría de grupos de Lie, temas de análisis numérico y aplicaciones de las ecuaciones diferenciales en morfogénesis;  es decir en la repetición de patrones regulares en los sistemas biológicos (investigadores del King’s College de Londres, donde había estudiado Turing, han proporcionado la primera evidencia experimental sobre la formación de algunos patrones biológicos, como las rayas de los tigres, confirmando las ecuaciones de morfogénesis de Turing).

En esta época Shannon publica el artículo  Programming a Computer for Playing Chess (1949), donde  describe como un computador puede jugar razonablemente a ajedrez, poniendo el interés en la resolución automática de problemas por encima de la importancia que las máquinas pudieran “pensar”. Por otro lado, Turing, en su artículo Digital Computers Applied to Games (1951), se formula la misma cuestión, pero para Turing los juegos constituían un modelo ideal para el estudio de la “inteligencia” de los computadores convirtiéndose así en precursor de la inteligencia artificial, siendo uno de sus paradigmas el denominado test de Turing para saber si un usuario de un computador es un ser humano o una máquina (los célebres Test CAPTCHA, Completely Automated Public Turing test to tell Computers and Humans Apart, con los que nos hacen escribir unas letras o signos confusos, Captchason un test de Turing inverso, con los que un ordenador intenta distinguir entre una persona y una máquina para evitar accesos de autómatas).

A parte de las coincidencias hay que resaltar que las líneas de investigación seguidas por Turing y Shannon han sido increíblemente productivas. Las de Turing más pragmáticas al estar preocupado por la calculabilidad y las de Shannon más teóricas reflejadas en su teoría de la información y las comunicaciones.

En 1950, durante un congreso en Londres sobre cibernética, y en particular en la charla sobre 'Información, máquinas y cerebro ", Turing defiende la idea que "una máquina debe poder alterar sus propias instrucciones", distinguiendo este concepto del de bifurcación condicional, al mismo tiempo que recrimina que la teoría de la información de Shannon no tiene en cuenta el coste computacional. En este mismo congreso, Turing se expande en los conceptos de búsqueda aleatoria y lo que ahora se llama algoritmo genético.

Estas líneas de investigación se han desarrollado de forma independiente y de forma complementaria: la de Turing asumiendo que los procesos de almacenamiento y  comunicación de datos eran perfectos para conseguir la computación y la de Shannon utilizando la computación (en los procesos de codificación y decodificación) para conseguir almacenamiento y comunicación de datos de la forma más fiable posible.

Sin sus contribuciones hoy no conoceríamos las potencialidades de los dispositivos digitales que nos rodean: teléfono, tabletas, ordenadores…, ni siquiera Internet y nuestro mundo sería totalmente diferente, tanto que se me hace imposible imaginarlo.

Llorenç Huget Rotger es catedrático de la Universitat de les Illes Balears.

Un acercamiento a la complejidad del mundo con los números

Por: | 07 de marzo de 2013

BENJAMÍN SUÁREZ ARROYO
EUGENIO OÑATE IBÁÑEZ DE NAVARRA

La historia muestra como las ciencias, y la tecnología, avanzan con el mayor conocimiento del hombre de los fenómenos de la naturaleza y del impacto que en ella ocasionan sus actuaciones. La necesidad de cuantificar la solución de un problema, bien sea de diseño y construcción de un edificio, la predicción de la vida de una célula, o la producción más económica de envases para alimentos, ha sido siempre ineludible. El aura de los números, que desde el inicio de los tiempos ha fascinado al hombre, ilumina la ciencia y la ingeniería modernas a través de los ordenadores y los métodos numéricos, que finalmente son uno de los motores que impulsan el desarrollo de las disciplinas científico-técnicas.

Seguir leyendo »

Lo imposible

Por: | 28 de febrero de 2013

FERNANDO OREJAS

Alan TuringEn su famoso artículo de 1936, del que ya se ha hablado en otras entradas de este blog, Turing hacía varias cosas notables. Primero, definía un modelo de máquina (la máquina de Turing) que permitía dar una definición matemática, y  cercana a la intuición, de qué es lo computable. Segundo, demostraba que había una "maquina universal" que podía tomar otras máquinas como datos y comportarse como ellas. Finalmente, demostraba que hay problemas (matématicos) que ninguna máquina podría resolver, que son no computables o indecidibles. Estas aportaciones se consideran muy importantes desde un punto de vista matemático y filosófico. Pero, dejando aparte la relación entre la máquina universal y los computadores actuales, ¿tienen estos resultados algún interés práctico en informática? Si consideramos que, en la última reforma de planes de estudio en Ingeniería Informática, las asignaturas que estudian estas cuestiones han pasado a ser optativas en un buen número de centros españoles, quizá la respuesta sería no. Claro que, si consideramos que estos temas son obligatorios en los estudios de informática de prácticamente todos los centros de prestigio del mundo, tendríamos que dudar de la anterior respuesta y, quizá, preguntarnos por qué algunos de nuestros centros son diferentes.

Seguir leyendo »

Informática y creatividad

Por: | 21 de febrero de 2013

MACARIO POLO USAOLA

PitagorasEn ocasiones, la investigación y la generación de nuevo conocimiento dan lugar al nacimiento de nuevas disciplinas cuyos primeros expertos son, precisamente, aquellos que hicieron evolucionar lo viejo para dar lugar a lo nuevo: el matemático Pitágoras procedía de la Filosofía; Platón, además de filósofo, escribió sobre Política, Ética y Moral; Aristóteles, discípulo de Platón, escribió cerca de doscientas obras sobre temas tan variados como la Lógica, la Estética, la Ética o la Retórica; el médico Paracelso, que buscó en el siglo XVI el elixir de la vida eterna, se dedicó también a la Astrología; Pascal, uno de los físicos más relevantes del siglo XVII, fue también matemático y teólogo, además de filósofo; Newton, aparte de físico, fue teólogo y alquimista y buscó la Piedra Filosofal.

Seguir leyendo »

HECTOR GEFFNER

Correo electrónicoPocos problemas tienen un carácter más teórico que determinar si hay más conjuntos de números naturales que números naturales, si una axiomatización de la lógica de predicados captura todas inferencias que son deductivamente válidas, o  si puede existir un procedimiento que demuestre que una inferencia es válida o no. Estos problemas no parecen tener mucho que ver con temas más profanos como envíar mensajes de texto, comprar entradas para un concierto por internet, o jugar al World of Warcraft (WoW). Sin embargo, estos y otros desarrollos prácticos que influyen de foma profunda en nuestra vida cotidiana están íntimamente vinculados a esos problemas teóricos mencionados inicialmente.

David HilbertEl vínculo se encuentra en los computadores desarrollados a partir de la década de los años 40, siguiendo un diseño que –en sus líneas fundamentales– había sido esbozado años atrás por el lógico matemático Alan Turing. Se trata de la famosa "máquina de Turing", que no fue diseñada para hacer nada práctico, aunque posteriormente Turing viera las posibilidades que tal "máquina" abría para el estudio del comportamiento inteligente. La "máquina de Turing", en papel, fue desarrollada para resolver un problema eminentemente teórico: el problema de encontrar un procedimiento para determinar la validez de una inferencia en lógica de predicados.  El problema había sido planteado por un famoso matemático, David Hilbert, en 1928. The Universal ComputerTanto la formulación del problema por Hilbert, como su resolución por Turing, se apoyan en ideas desarrolladas por Hilbert y otros lógicos y matemáticos, entre los que cabe destacar a Boole, Cantor, Frege, Russell, y Godel; el "dream team" de la lógica moderna. La historia de este desarrollo está magníficamente contada en el libro "The Universal Computer: The Road from Leibniz to Turing", Martin Davis [1].

Turing demuestra rigurosamente que el procedimiento buscado por Hilbert no existe. Turing inventa "su" máquina como formalización de lo que es un procedimiento (un método de cómputo), y demuestra entonces que no puede haber tal máquina para el problema de Hilbert (el Alan Turingllamado "Entscheidungsproblem"[2], para diferenciarlo de otros problemas fundamentales también formulados por Hilbert). Para la prueba utiliza la idea de codificar máquinas con números, siguiendo el ejemplo de Godel quien introduce una idea similar para demostrar la incompletitud de la aritmética formal (otro problema planteado por Hilbert), y la  técnica de diagonalización, introducida antes por Cantor para demostrar que hay más conjuntos de naturales que números naturales, usada tambien por Godel en su prueba.

Turing no se queda en ese resultado sin embargo y construye una "máquina de Turing" (todavía en papel) que es "universal" en el sentido que este "hardware" particular puede ejecutar cualquier procedimiento. Más precisamente, esta máquina universal de Turing es programable: acepta la descripción de una máquina particular que resuelve un problema dado sobre una entrada, y emula el comportamiento de esa máquina sobre esa entrada.  Máquina de TuringLa máquina universal de Turing es la madre del computador programable moderno. Que algo así era incluso posible no era obvio en los años 40 cuando los "computadores" se desarrollaban para resolver un conjunto específico de cáculos. El límite de la  máquina universal de Turing, por otro lado, es el límite de ordenadores actuales, el límite de lo computable.

Sorprende ver como un desarrollo que no estuvo motivado en modo alguno por aplicaciones "prácticas", ha tenido un impacto que quizás algun día se compare al desarrollo de la agricultura. La historia, sin embargo, no es inusual en el desarrollo de la ciencia, donde uno sabe donde empieza pero no donde termina. Esa es la promesa de la ciencia desde el punto de vista social, y la aventura del  científico desde el punto de vista personal.

Hector Geffner es investigador senior ICREA y profesor de la Universitat Pompeu Fabra.


[1] Martin Davis es un matemático estadounidense, bien conocido por el algoritmo de Davis-Putnam para resolver el problema de satisfactibilidad booleana. Su libro “The Universal Computer” fue editado por Norton el el año 2000, y ha sido reeditado por Taylor & Francis en 2011.

Una excelente conferencia de Martin Davis sobre la naturaleza de la computación y los trabajos de Church y Turing se puede ver aquí. .

[2]  El "Entscheidungsproblem" fue resuelto de forma independiente por Alonzo Church y Alan Turing, en sendos artículos publicados en 1936 con pocos meses de diferencia. El artículo de Turing contenía la descripción de su “máquina”, lo que tuvo una inmensa repercusión posterior. Como curiosidad, cuando Turing escribió su artículo había terminado sus estudios de matemáticas en Cambridge (Reino Unido) pero no había comenzado sus estudios de doctorado. Alonzo Church fue el director de su tesis doctoral en Princeton (Estados Unidos).

Algunos vínculos entre los teoremas de Gödel y Turing

Por: | 07 de febrero de 2013

JOSEP PLA I CARRERA

A finales del siglo XIX y en la primera mitad del XX, hubo diversos intentos de formalizar y sistematizar las denominadas ‘ciencias puras’. Con respecto a las matemáticas, en su obra de 1899, Grundlagen der Geometrie, David Hilbert (1862-1943) plantea ya algunas de las ideas de lo que, desde entonces, irá consolidándose como su formalismo o teoría de la demostración. Ciertas partes ‘esenciales’ de la matemática —geometría, aritmética, topología, etc.— deben tratarse en un lenguaje formal a partir de unos axiomas ‘ad hoc’  que son los que configuran los objetos de la teoría y las interrelaciones que coexisten entre ellos. De hecho, los ‘objetos semánticos’ que se amagan detrás de los ‘objetos formales’ carecen de importancia: “No importa si se trata de puntos, rectas, planos o de mesas, sillas o jarras de cerveza”. Aparece aquí, agazapada, la distinción entre ‘teoría formal’ y ‘matemática formalizada’.

David HilbertEste planteamiento lleva ínsito que el sistema axiomático formal responda a algunas características importantes, cuales son: la independencia de los axiomas (que le dan un carácter minimal que, sin ser esencial, es importante en este contexto por lo que tiene de clarificador), su completitud (los axiomas se eligen de manera que recojan toda la potencialidad de la ‘matemática’ que se formaliza: “todo lo que, en dicha matemática es cierto, la axiomática debe permitirnos demostrarlo”), y su consistencia (la ‘característica esencial’ y que dota de ‘existencia’ a los objetos de la teoría)[1].

 En el texto de lógica Wilhelm Ackermann que publicara junto con Wilhelm Ackermann (1896 -1962), Grundzüge der theoretischen Logik (1928), se plantea una nueva cuestión que, en cualquier caso, debe ‘cuestionarse’: el “Entscheidungsproblem” o “problema de la decisión”: ¿Cabe un ‘algoritmo’ que ‘decida’ si una fórmula bien formada del lenguaje formal es un teorema de una teoría formal concreta?; y, en concreto, “¿el cálculo de predicados de primer orden es decidible o indecidible?”. Lo plantean, como ya lo hiciera Hilbert en 1900 en el enunciado del problema 10 o ‘problema diofántico’ en su lección señera del “Congreso Internacional de Matemáticas de París”, antes de que nadie hubiese elaborado una definición matemática precisa del concepto de ‘algoritmo’.

Emil PostEn 1930, Kurt Gödel (1906-1978) demostraría la ‘completitud’ del cálculo de predicados de primer orden: “Todo lo que se puede demostrar es verdadero y todo lo que es verdadero se puede demostrar”.[2] Este teorema hace referencia a la ‘lógica’ pero carece de lo que podríamos llamar ‘contenido matemático’. El resultado, análogo en el cálculo de proposiciones, establecido por Emil Post [1897-1954] en 1921, podía hacer pensar que quizás aquel cálculo, como lo era éste, sería decidible.


Kurt GödelEn 1931, el eminente matemático y lógico alemán cerraría —de una forma inesperada para Hilbert— las cuestiones de la completitud y de la consistencia de ciertas teorías matemáticas. En definitiva —y de forma breve— [primer teorema de incompletitud de Gödel] “cualquier teoría que contenga la aritmética de Peano convenientemente axiomatizada, y sea consistente, es incompleta”. Además [segundo teorema de incompletitud de Gödel] “es imposible dar una demostración de la consistencia de la teoría ‘dentro’ de la teoría”.

Para lograr establecer estos resultados —en particular, el primero—, Gödel recurre a una especie de “piedra de Rosetta”. Es decir, recurre a tres lenguajes distintos —el lenguaje ordinario, el lenguaje formal y el lenguaje matemático de la aritmética— para los que establece como se traduce de uno a otro[3], uno de los cuales es el lenguaje de la aritmética de los números naturales entendidos como objetos matemáticos y no como objetos formales.

Precisa cuales son los ‘diccionarios’. Los conjuntos, relaciones y funciones aritméticas ‘traducibles’ al lenguaje formal son los ‘primitivos recursivos’, un concepto que en ulteriores trabajos el propio Gödel ampliará ‘recursivo’. Resulta que las expresiones ‘metamatemáticas’ relativas al lenguaje formal por ejemplo,j(v1) es una fórmula con la única variable llibre v1”, “la sentencia s admite una demostración en la teoría formal”, etc.— se pueden transformar en conjuntos primitivos recursivos por medio de la gödelización.

Alonzo ChurchSin embargo, quedaba todavía en el tintero la cuestión de la decidibilidad de la teoría, la cual como ya hemos indicado depende de disponer de un concepto ’fino’ de algoritmo. Este problema sería resuelto en 1936, simultáneamente, por Alonzo Church [1903-1995], y Alan M. Turing [1912-1954].

La presentación de Turing es por su simplicidad y naturalidad la más comprensible y la que más proyección ha tenido en la teoría de la computación, y más si cabe porque, en el trabajo de 1936, establece la ‘existencia de la máquina universal’; esto es, una máquina U que, frente a unos datos, se puede comportar como cualquiera de las máquinas de computación M: puede sumarlos, multiplicarlos, etc. Basta con que indiquemos cómo queremos que se comporte en cada caso. Formalmente,

U(mM, n1,...,nk):=M(n1,...,nk),

 en donde mM dice a la máquina U que debe actuar como la máquina M; de hecho, cada máquina M admite un código numérico mM.

Alan TuringAdemás, Turing, en general, usa el mismo lenguaje para dar la  ‘máquina’ —el programa computacional— como para realizar la computación, un avance realmente notable con respecto de quienes, antes que él, habían intentado ofrecer máquinas de cálculo. La suya, claro está, es una máquina teórica o formal antes que una máquina mecánica.

Con este concepto de ‘computabilidad’ Turing puede establecer dos resultados importantes:

  1. El cálculo de predicados de primer orden no es decidible: “ninguna máquina puede decidir si una fórmula es o no un teorema del cálculo de predicados”.
  2. Hay problemas que ‘no’ son computables:; así aparece el ‘problema de la parada’: “‘no’ es posible construir una máquina que, si le damos como entrada, el código mM de una máquina M y unos ciertos datos numéricos n1,...,nk, nos diga si M(n1,...,nk) se parará o continuará procesando indefindamente”.

Hemos relacionado, pues, Turing con Hilbert.

Pero, ¿qué lo vincula con Gödel? La respuesta nos las dan las ‘funciones recursivas [parciales]’. Una máquina de Turing calcula las funciones recursivas y sólo éstas. Este es un vínculo muy estrecho entre algunos de los conceptos introducidos por Gödel y algunos de los conceptos introducidos por Turing que justifican, creo, que en 1963 Gödel añadiera un apéndice al artículo de su teorema de 1931 afirmando que las aportaciones de Turing permitían “una definición precisa e indudablemente adecuada de la noción general de sistema formal de los teoremas vi y xi”.[4]

Josep Pla i Carrera es profesor emérito de la Universitat de Barcelona.

Libro-plaJosep Pla acaba de publicar el libro: “El teorema de Gödel, Un análisis de la verdad matemática”  dentro de la serie de libros de autor de la Real Sociedad Matemática Española y con edición conjunta entre la RSME y SCIE como actividad del Año Turing / Año de la Informática. El libro se puede encontrar aquí.

El libro está dividido en tres partes. En la primera Josep Pla da una aproximación a la epistemología de la matemática, centrándose en el problema de la verdad en las matemáticas. En la segunda parte, más técnica, aborda la demostración de los teoremas de incompletitud de Gödel. Finalmente, en la tercera parte se analizan algunas consecuencias de los teoremas de Gödel. El libro admite dos lecturas: el lector que busque un texto divulgativo sobre la obra de Gödel verá satisfechas sus expectativas; para el especialista que busque una aproximación rigurosa a los teoremas de Gödel, este texto de Pla es una muy buena opción.

También se destaca que el trabajo sobre computabilidad de Alan Turing se inspiró en el de Kurt Gödel sobre lógica, resultando consecuentemente impregnado de verdad matemática. Así sucede con el conocido problema de la parada para la máquina de Turing cuyo propio enunciado constituye a su vez el paradigma de existencia de funciones no computables.


[1] El lector interesado puede ampliar esta presentación en Pla i Carrera, J. (2013), capítulo 7, págs.145-161.

[2] Para disponer, sin embargo, de la ‘definición’ precisa de ‘verdad’ o ‘validez’ habría que esperar al genial artículo de Alfred Tarski [1902-1983] de 1936. Véase Pla i Carrera, J. (2013), págs.185-191.

[3] El lector interesado puede recurrir al capítulo 11 de Pla i Carrera, J. (2013).

[4] El lector interesado puede recurrir a Cutland [1980], capítulo 8, págs. 143-156.

Referencias

Church, Alonzo (1936). “A note on the Entscheidungsproblem”. Journal of Symbolic Logic, págs.  40–41.

Cutland, Nigel (1980). Computability. An introduction to recursive function theory. Cambridge University Press. Cambridge.

Gödel, Kurt (1930).“Die Vollständigkeit der Axiome des logischen Funktionenkalküls”. Monatshefte für Mathematik und Physik, 37, págs. 349-360. Traducción castellana en Gödel, K. (1981), págs. 20- 34.

Gödel, Kurt (1931).“Ûber formal unentscheidbare Sâtze der Principia Mathematica und verwandter System”. Monatshefte für Mathematik und Physik, 38, págs. 173-198. Traducción castellana en Gödel, K. (1981), págs. 45-89.

Hilbert, David (1899). Grundlagen der Geometrie. Teubner: Sttugart.

Hilbert, David (1900). “Mathematische Probleme”, Archiv für Mathematik und    Physik, 1, págs. 44-63; 213-237. Traducción castellana de Javier García, en Gray, Jeremy (2000), El reto de Hilbert. Drakontos. Crítica, Madrid: 2003.

Hilbert, David y Ackermann, Wilhelm (1928). Grundzüge der theorestischen Logik. Springer. Berlin. Traducción castellana de Víctor Sánchez de Zavala, Elementos de Lógica Teórica. Editorial Tecnos: Madrid, 1962.

Pla i Carrera, Josep (2013), El Teorema de Gödel. Un análisis de la verdad matemática. Real Sociedad Matemática Española. Madrid: 2012.

Post, Emile (1921). “Introduction to a general theory of elementary propositions”. 43, págs. 163-185.

Tarski, Alfred (1936). “Der Wahrheitsbegriff in den formalisierten Sprachen”. Studia Philosophica, 1, págs 261-405.

Turing, Alan Mathison (1936). “On computable numbers, with an application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society, 42, págs. 230-265.Véase http://www.abelard.org/turpap2/tp2-ie.asp.


SUSANA MUÑOZ HERNÁNDEZ

Es dificil decidir cuáles de las áreas tradicionales de cooperación han sido, y son, decisivas en el desarrollo humano. Durante décadas, instituciones gubernamentales y civiles han trabajado en asistencia médica y sanitaria, han luchado contra las crisis alimentarias y han trabajado en la educación. Cuando nos presentaban a alguien que se dedicaba a trabajar en paises del tercer mundo (o del sur o en vias de desarrollo, como queramos llamarlos) automáticamente imaginábamos que esa persona debía ser médico, misionero o profesor. Desde la perspectiva ingenieril no es dificil ampliar este abanico y que se nos ocurran otras áreas, también decisivas, como la ingeniería civil (los trabajos en infraestructuras de comunicaciones terrestres o marítimas, de accesibilidad al agua, ...) o la arquitectura (proyectos de habitabilidad básica por ejemplo en campos de refugiados, de reconstrucción en caso de desastres naturales, etc.) Estas son labores que, si bien no son las primeras que se nos vienen a la mente cuando pensamos en trabajos de cooperación al desarrollo, no nos son, tampoco, ajenas puesto que, al fin y al cabo, estamos acostumbrados a ellas por los proyectos de grandes organizaciones de ayuda humanitaria como Cruz Roja, Naciones Unidas y otros.

Pero el desarrollo humano actual no depende exclusivamente de estas disciplinas. Empieza a resultarnos habitual la incorporación de las nuevas tecnologías a todos los ámbitos y el de la cooperación al desarrollo no deja de ser uno de ellos. Comenzamos a asociar el campo de las comunicaciones a los proyectos de paises en vías de desarrollo. Antenas parabólicas para comunicar via satélite comunidades remotas, repetidores para dar acceso universal a la telefónica movil en zonas inaccesibles, conexiones via internet utilizando coverturas wifi para dar teleasistencia a centros médicos de zonas aisladas o deprimidas.

Y ¿donde queda la informática en todo esto? ¿hemos oido alguna vez hablar de cooperantes informáticos? ¿nos parece un proyecto de informática algo prioritario en el ámbito de la cooperación internacional al desarrollo? La mayoría de la gente respondería “no” a las dos últimas preguntas y, sin embargo, la respuesta debería ser “si”.

Seguir leyendo »

Sobre los autores

Este blog es una obra colectiva en la que participarán científicos y expertos españoles y extranjeros cuya obra haya bebido de las aportaciones de Alan Turing. Aunque principalmente recogerá los avances científicos en la Informática, abarcará otras opiniones sobre la importancia de la misma en otros ámbitos: la Medicina, la Física, la Política, la Economía. El blog está coordinado por Pedro Meseguer y Juan José Moreno Navarro.

Archivo

julio 2013

Lun. Mar. Mie. Jue. Vie. Sáb. Dom.
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

El País

EDICIONES EL PAIS, S.L. - Miguel Yuste 40 – 28037 – Madrid [España] | Aviso Legal