Una moraleja con raíz matemática: la Tesis de Church-Turing sobre la equivalencia de modelos

Rafael Morales Bueno
Academia Malagueña de Ciencias

En los alrededores de los años 30 del pasado siglo, ciertos descubrimientos en Matemáticas relacionados con la computación llevaron a varios científicos a pensar que cada uno de ellos tenía razón en sus postulados y que los demás, sencillamente, estaban equivocados. En realidad, todos estaban equivocados y, con el paso del tiempo, comprendieron que era mucho más eficaz para la Ciencia tener un poco más de humildad y procurar colaborar en sus investigaciones. De esta forma, mediante la colaboración de científicos y universidades, se produjeron los más importantes avances científicos en esta disciplina.

Vamos a realizar un breve recorrido por esta curiosa historia que, desde mi punto de vista, nos deja una interesante moraleja. David Hilbert, un destacado matemático alemán de finales del siglo XIX y principios del XX, de formación prusiana, fue profesor de la Universidad de Königsberg y posteriormente Catedrático en la de Göttingen. Analizó la importancia de saber discernir entre lo que es computable y lo que no lo es. Demostró que ciertas actividades son computables (las reglas están claras, se hacen en un tiempo finito y no dependen de quién las haga): sumar, restar, hacer una división de polinomios. Existen muchas otras acciones humanas que, evidentemente, no son computables, como por ejemplo hacer un buen gazpachuelo. ¿Dónde está la frontera entre lo computable y lo no computable? Para abordar esta cuestión diversos científicos definieron algunos modelos matemáticos. Vamos a citar a cuatro destacados científicos matemáticos, todos ellos expertos en lógica, quizás los más significativos para documentar nuestra moraleja.

(Izquierda) Retrato de Alan M. Turing. (Derecha) Cartel anunciador de la famosa película «El Código ENIGMA» que popularizó la imagen del matemático que logró descifrar las claves de las comunicaciones germanas durante la Segunda Guerra Mundial.

El primero de ellos al que nos referimos es el británico Alan M. Turing, profesor de la Universidad de Cambridge, precursor de la informática moderna y famoso por haber logrado evitar miles de muertes durante la Segunda Guerra Mundial gracias a haber podido descifrar el código de comunicaciones de los submarinos alemanes (Código ENIGMA). Turing definió la conocida hoy como máquina de Turing (que él llamó “A machine”, automática, y para la que tomó como modelo lo que hacían los “computers” del siglo XIX, que no eran más que personas que se ganaban su salario haciendo cálculos para las tablas de logaritmos, tablas trigonométricas, de navegación, etc.).

El segundo científico que vamos a citar es Sthepen Cole J. Kleene, eminente estudiante en el Universidad de Princeton quién realizó su tesis doctoral bajo la dirección de Alonzo Church -de quién hablaremos posteriormente-, pasando a ser un renombrado profesor en la  Universidad de Wisconsin-Madison. Sus trabajos de investigación derivan del Teorema de Incompletitud de Gödel (Premio Albert Einstein, 1951). Conviene que asimilemos de forma intuitiva este teorema tomando como ejemplo la situación que estamos viviendo por causa de la pandemia de COVID19. Contemplar entonces las opciones que tenemos: confinados o no confinados, infectados o no infectados. Kurt Gödel demostró que un sistema no puede ser a la vez COMPLETO (todos los infectados por COVID19 están confinados) y CONSISTENTE (ningún no infectado por COVID19 está confinado). Es decir, si definimos una norma que sea COMPLETA, seguro que confinamos a alguien que no está infectado (INCONSISTENTE) y si, por el contrario, definimos una norma CONSISTENTE, seguro que algún infectado no está confinado (INCOMPLETO), y esto no es evitable de ninguna manera. En la demostración de ese teorema se usan unas funciones que desarrolló Stephen C. Kleene y que las denominó “funciones recursivas”.

Por su parte, el tercer investigador en liza es el norteamericano Alonzo Church, que fue profesor en la Universidad de Princeton y dirigió la Tesis Doctoral de Turing, y fue quién definió el lambda-cálculo, que es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión.

En cuarto lugar, el lógico matemático de origen polaco Emil Leon Post -en 1904, con tan solo siete años, emigró a Nueva York con sus padres-, tras una excelente trayectoria como estudiante con una brillante tesis doctoral, dedicó su vida a la enseñanza secundaria en su ciudad de acogida, aunque siempre permaneció en contacto con destacados investigadores de diversas universidades. Definió un modelo de computación denominado la máquina de Post (al definirla en fechas cercanas a la máquina de Turing y tener la misma finalidad de formalizar lo computable, algunos colegas sospecharon que podría tratarse de algún tipo de plagio, pero pronto se demostró que fue un descubrimiento independiente y original; esto es frecuente en la ciencia: cuando se llega a cierta madurez en un aspecto, el mismo resultado o similar surge en distintos grupos de investigación; lo mismo ocurrió con el cálculo diferencial e integral descubiertos a la vez por Newton y Leibnitz).

Como vemos se trata de cuatro modelos que se deben a la creatividad y al genio de otros tantos investigadores, dándose la circunstancia curiosa de que Church fue profesor de los otros tres investigadores. Pues bien, durante los siguientes años cada uno de ellos se esforzó en demostrar que su propio modelo era el mejor y que los demás estaban equivocados. ¿Cómo? Buscando alguna función o proceso que fuera intuitivamente calculable, que se pudiera hacer con su modelo y en el que los otros modelos fallaran. Lo que sucedió fue que cada problema que un investigador suponía que fallaría en otro modelo, resultaba que no fallaba. Ninguno daba con el perfecto contraejemplo que funcionara a favor de un modelo concreto.

Church y Turing, a quienes se debe la conocida tesis sobre la equivalencia de modelos.

Hacia finales de los años 30 del siglo XX, comenzaron a preguntarse ¿y si mi modelo es equivalente a ese otro del que intento demostrar que es diferente? Las respuestas que cada uno de ellos fue encontrando les permitieron comprobar que este nuevo punto de vista era el correcto: la equivalencia de los modelos. De ésta manera, y mediante la cooperación, comenzaron a demostrar la equivalencia de modelos dos a dos, hasta llegar a la conclusión de que todos ellos eran equivalentes. En décadas posteriores se han desarrollado más modelos numéricos que, a lo largo del siglo XX (la máquina RAM, el lenguaje WHILE,…) también se han demostrado equivalentes. El principio que afirma que todos los futuros modelos también serán equivalentes se conoce como la Tesis de Church-Turing.

La moraleja de esta historia es que resulta conveniente ser humilde y es mejor pensar que estamos cerca los unos de los otros, antes que intentar demostrar que lo de uno es mejor que lo del otro. Tomemos pues lo mejor de cada opción.

 

*Imagen de cabecera (de izquierda a derecha): Hilbert, Turing, Kleen, Post.