La inform¨¢tica cumple 80 a?os

En el optimista contexto cient¨ªfico de finales del siglo XIX, con el mecanicismo y el determinismo reinando sobre las ciencias naturales, no es extra?o que David Hilbert (1862-1943), una de las mentes m¨¢s brillantes del momento, apostara por la completa mecanizaci¨®n de las matem¨¢ticas. Un proyecto que extender¨ªa la potencia de las calculadoras ya existentes en aquel momento hasta l¨ªmites insospechados, superando las sumas, restas y sus derivados y atrevi¨¦ndose con el razonamiento del m¨¢s alto nivel para obtener de forma mec¨¢nica cualquier resultado matem¨¢tico.

Hilbert propon¨ªa utilizar la l¨®gica como formalismo universal para expresar las afirmaciones matem¨¢ticas y estudiar las relaciones de ¨¦stas entre s¨ª mediante reglas de inferencia. Uno de los retos fundamentales planteados por Hilbert es el conocido como Entscheidungsproblem o Problema de Decisi¨®n, que consiste en proporcionar un m¨¦todo efectivo capaz de establecer, en un n¨²mero finito de pasos, si una determinada f¨®rmula de la l¨®gica es cierta o no.

Espoleados por el reto intelectual planteado, o tal vez por la perspectiva de quedarse sin trabajo, muchos matem¨¢ticos acompa?aron a Hilbert en su b¨²squeda. En 1936, hace ahora 80 a?os, Alonzo Church (1903-1995), l¨®gico americano de la Universidad de Princeton, y Alan M. Turing (1912-1954), graduado poco antes en Cambridge, introdujeron sendos modelos de c¨¢lculo simb¨®lico autom¨¢tico (el denominado C¨¢lculo Lambda y lo que hoy conocemos como M¨¢quina de Turing) y avanzaron la tesis, hoy conocida como Tesis de Church-Turing, de que ambos capturaban el escurridizo concepto de m¨¦todo efectivo en el sentido planteado por Hilbert.

Alonzo Church y Alan Turing

La Tesis de Church-Turing es eso, una tesis, que no es posible demostrar formalmente ya que, aunque el C¨¢lculo Lambda y la M¨¢quina de Turing est¨¢n definidos con total precisi¨®n, no existe una definici¨®n de ¡®m¨¦todo efectivo¡¯ con la que compararlos. Sin embargo, en la actualidad dicha tesis es ampliamente aceptada (?aunque debatida!) y constituye la base de la moderna Ciencia de la Computaci¨®n ya que los l¨ªmites descubiertos para su m¨¢quina por el propio Turing afectan a todos los dispositivos que utilizamos hoy en d¨ªa, comenzando por nuestros smartphones y terminando por los superordenadores que permiten predecir el tiempo o guiar las misiones de exploraci¨®n a Marte.

En efecto, Church y Turing demostraron que el Problema de Decisi¨®n no tiene soluci¨®n. En t¨¦rminos m¨¢s actuales, significa que no existe ning¨²n programa de ordenador que sea capaz de establecer si una propiedad expresada en el lenguaje de la l¨®gica es cierta o falsa. Esta afirmaci¨®n puede dejarnos fr¨ªos: ?qu¨¦ tiene que ver la l¨®gica con el uso de las redes sociales desde mi smartphone o con la consulta de mi peri¨®dico favorito en mi navegador favorito? Mucho. Puesto que los programas de ordenador son objetos formales (expresiones de un lenguaje con unas normas de construcci¨®n muy precisas) y su comportamiento en ejecuci¨®n est¨¢ gobernado por reglas igualmente precisas y formales, es posible realizar afirmaciones sobre los resultados esperados con ese programa: ?le ha llegado el mensaje que acabo de enviar a mi amigo? ?la transacci¨®n bancaria que acabo de realizar en mi aplicaci¨®n de banca electr¨®nica se ha reflejado en mi cuenta corriente? ?la impresi¨®n que he lanzado va a completarse? Estas preguntas pueden formularse utilizando un lenguaje l¨®gico y por tanto est¨¢n sometidas al dictado del Problema de Decisi¨®n. En el ¨¢mbito del desarrollo del sofware tienen que ver con el problema de inspeccionar el texto de un programa de ordenador y ser capaz de extraer alguna conclusi¨®n sobre c¨®mo va a funcionar o qu¨¦ resultados puede proporcionar; se trata del problema del an¨¢lisis y verificaci¨®n de software.

La soluci¨®n negativa dada por Church y Turing al Problema de Decisi¨®n implica que nuestras preguntas sobre el comportamiento del software y, en general de los sistemas inform¨¢ticos que utilizamos, no siempre obtendr¨¢n respuesta. Tampoco significa que nunca obtendr¨¢n respuesta: hay espacio para el desarrollo de m¨¦todos que nos permitan estudiar ciertas propiedades, depurar errores y conseguir software m¨¢s fiable. Pero el trabajo de Church y Turing muestra que, adem¨¢s de las categor¨ªas l¨®gicas cierto o falso, debemos admitir un fat¨ªdico ¡®no s¨¦¡¯ entre nuestros compa?eros de viaje. Solo podemos aspirar a esquivar esa indeterminaci¨®n tanto como podamos. Lo cual es apasionante, dicho sea de paso.

Uno de los retos fundamentales planteados por Hilbert es el conocido como 'problema de decisi¨®n', que consiste en proporcionar un m¨¦todo efectivo capaz de establecer, en un n¨²mero finito de pasos, si una determinada f¨®rmula de la l¨®gica es cierta o no

Goldstine y von Neumann

Durante su etapa en Princeton (1936-1938), donde Turing realiz¨® su tesis doctoral con Church, John von Neumann ofreci¨® a Turing un empleo como asistente de investigaci¨®n, aunque ¨¦ste decidi¨® volver a su pa¨ªs, donde ya se present¨ªa la llegada de una guerra. Goldstine y von Neumann tuvieron un papel muy importante en la realizaci¨®n pr¨¢ctica de las ideas de Turing, ya que en 1946 propusieron un esquema general para llevarlas a la pr¨¢ctica mediante el uso de componentes electr¨®nicos sobre la base de codificar todo tipo de informaci¨®n mediante secuencias de ceros y unos (los conocidos bits). Goldstine y Von Neumann tambi¨¦n dise?aron la primera notaci¨®n para escribir los programas que controlan la actividad de los ordenadores (diagramas de flujo).

Pero la Tesis de Church-Turing sigue manteniendo su carga prof¨¦tica: establece un l¨ªmite fundamental a la capacidad de c¨®mputo que cualquier dispositivo del futuro podr¨¢ alcanzar. Y es el origen de toda una ¨¢rea de investigaci¨®n, creaci¨®n y desarrollo tecnol¨®gico en la que todos estamos invitados a participar: la Inform¨¢tica.

Salvador Lucas es catedr¨¢tico de la Universidad Polit¨¦cnica de Valencia, ¨¢rea de Lenguajes y Sistemas Inform¨¢ticos.

Cr¨®nicas del Intangible es un espacio de divulgaci¨®n sobre las ciencias de la computaci¨®n, coordinado por la sociedad acad¨¦mica SISTEDES (Sociedad de Ingenier¨ªa de Software y de Tecnolog¨ªas de Desarrollo de Software). El intangible es la parte no material de los sistemas inform¨¢ticos (es decir, el software), y aqu¨ª se relatan su historia y su devenir. Los autores son profesores de las universidades espa?olas, coordinados por Ricardo Pe?a Mar¨ª (catedr¨¢tico de la Universidad Complutense de Madrid) y Macario Polo Usaola (profesor titular de la Universidad de Castilla-La Mancha).