Vídeo de “Los números que no se pueden calcular (Homenaje a Turing)” en Naukas Bilbao 2012

“Los números que no se pueden calcular (Homenaje a Turing)”
Francis Villatoro (Emulenews). Click en la imagen para ir a EITB.

Alan (Mathison) Turing nació el 23 de junio de 1912 en Londres (hace 100 años) y murió el 7 de junio de 1954, como Blancanieves, tras comer una manzana envenenada. No se suicidó, le asesinó la madrastra, la sociedad puritana británica que le persiguió por ser homosexual, un delito penal en 1954. El 10 de septiembre de 2009 el primer ministro del Reino Unido, Gordon Brown, emitió un comunicado declarando sus disculpas en nombre del gobierno por el trato que recibió Alan Turing durante sus últimos años de vida.

Celebramos este año el centenario del nacimiento de Alan Turing y en esta charla hablaré de su trabajo matemático más famoso, el que le convirtió en uno de los padres de la informática. La demostración de que hay números que no se pueden calcular. Trabajo en el que introdujo las famosas máquinas de Turing como modelo matemático del concepto de algoritmo.

Turing estudió en el King’s College, Cambridge, 1931-1934, y obtuvo una beca de investigación en 1935. Asistió a un curso de doctorado impartido por el Prof. Max Newman, sobre los teoremas de Gödel y el Entscheidungsproblem de Hilbert-Ackermann (1928), el problema de la decisión. En el verano de 1934, Turing tuvo una idea en los prados de Grantchester, Cambridge, utilizar una máquina para modelar el trabajo de un matemático demostrando teoremas o calculando números. Nació la máquina de Turing. Le llevó dos años escribir el programa de la máquina universal de Turing, necesaria para resolver el problema de la decisión.

En 1936, cuatro matemáticos, trabajando de forma independiente, resolvieron el problema de la decisión. El primero, Alonzo Church, que utilizó el cálculo lambda, el segundo, Alan Turing, que usó las máquinas de Turing, el tercero, Stephen Kleene, gracias a las funciones mu-recursivas, y el cuarto, Emil Post, que usó la máquina de Post. Hoy en día se suele hablar de la solución de Church-Turing. El trabajo de Turing introdujo un algoritmo para calcular números y estudió los números reales que se pueden calcular.

La máquina de Turing que calcula un número es un algoritmo que se puede escribir mediante símbolos. Todas las máquinas de Turing posibles corresponden a todas las secuencias finitas de símbolos y por tanto son enumerables. Su cardinal es el mismo que el de los números naturales, el mismo que el de los enteros, el mismo que el de los racionales (cocientes de enteros), el mismo que el de los números algebraicos reales (soluciones de polinomios con coeficientes enteros). Los números reales computables, entre ellos muchos números transcendentes, como pi o e, tienen como cardinal el mismo que el de los números naturales. Por tanto, hay números reales que no son calculables. Más aún, con probabilidad uno, todo número real es no calculable. Sin embargo, todo lo que sabemos sobre la realidad se basa en operar con los números reales que son calculables.

La demostración más elemental de que hay más números reales que enteros se basa en el argumento de diagonalización de Cantor (1891).

Si no has visto aún mi charla, te animo a disfrutarla en la web de EITB a la carta. La noche anterior dormí un par de horas, pero espero que no se me note mucho.

 

2 pensamientos en “Vídeo de “Los números que no se pueden calcular (Homenaje a Turing)” en Naukas Bilbao 2012

  1. Francis, lo comentado en la charla de la demostración de Cantor mediante su ejemplo de la diagonal, no lo comparto. Aquí lo desarrollo chapuceramente (como todo lo que yo hago)

    http://angelalonso.wordpress.com/2010/09/21/revision-del-ejp-de-la-diagonal-de-georg-cantor/

    Donde concluyo:
    “El ejp. de la diagonal de Cantor solo incluye en dicha diagonal una parte infinitésimal del total de la columna a formar por la TOTALIDAD DE Nº DECIMALES ASOCIADOS UNO A UNO A LOS Nº NATURALES (por ejp.), con lo que, el poder formar un número decimal que no se encuentre entre los utilizados para la DIAGONAL mediante este método, no demuestra que NO esté entre el TOTAL de los números asociados a los naturales que componen DICHA COLUMNA. Esto lo invalida para poder demostrar que esta relación biyectiva es cierta, ni para reducir el ejp. al absurdo por autoinvalidarse dicha relación biyectiva.”

    Que conste que con esto no estoy diciendo que exista esa biyección; más bien al contrario, también creo que no la tienen y que tienen distinto cardinal.

    Saludos de Angel.

Los comentarios están cerrados.