Esta semana estaré a cargo de la charla del ciclo Cafés Científicos, organizada por el Centro Atómico Bariloche e Instituto Balseiro. Voy a presentar mi charla sobre el genial Alan Turing, de quien se celebra este año su centenario. Si estás en Bariloche, date una vuelta.
¿Dónde? En el Quincho del Personal del CAB, kilómetro 8 de Av. Bustillo, en Playa Bonita.
¿Cuándo? El jueves 11 de octubre a las 18:30 horas.
¿Cuánto? Nada. La entrada es libre y gratuita.
¿Qué me pongo? Lo que quieras. Son charlas informales.
El fantasma en la máquina
¿Puede programarse una máquina para que piense o para que simule que piensa? ¿Está la inteligencia necesariamente encarnada en un organismo biológico? ¿El cerebro funciona como una máquina? En este encuentro se repasará la breve, fructífera y trágica vida de Alan Turing, genial matemático inglés, pionero de las computadoras y la inteligencia artificial, quien se planteó y trató de resolver estos interrogantes.
Mostrando entradas con la etiqueta Turing. Mostrar todas las entradas
Mostrando entradas con la etiqueta Turing. Mostrar todas las entradas
09/10/2012
22/09/2012
El enigma de Turing (parte 4)
Esta es la cuarta parte de la serie El enigma de Turing. Link a la primera parte. Link a la segunda parte. Link a la tercera parte.
¿En qué estábamos? Terminada la guerra, Turing regresó a la vida académica y a su nueva pasión: construir un cerebro, usando la novísima tecnología electrónica. Su experiencia con máquinas de desencriptar durante la guerra (de las cuales no podía decir ni una palabra, naturalmente), lo ponía en una posición excelente para esta tarea. Fue designado director científico en un área del Laboratorio Nacional de Física creada específicamente para este propósito.
LA INTELIGENCIA ARTIFICIAL
Alan se desentendió un poco de los problemas de hardware y durante un par de años se dedicó a diseñar los rudimentos del software, fundamentalmente a lo que hoy llamaríamos un lenguaje de programación. Lamentablemente su trabajo en el Laboratorio no prosperó, por dificultades personales. Turing era un poco excéntrico, así que el trabajo primordialmente administrativo que tenía en el Laboratorio no le atraía mucho. En eso, su amigo y antiguo profesor Max Newman le ofreció un cargo en la Universidad de Manchester, un importante puesto en el flamante Laboratorio de Computación, así que Alan renunció al Laboratorio Nacional. En Manchester finalmente se construyó una computadora a fines de los '40, si bien no de acuerdo a los lineamientos de Turing, quien creía que el poder de las computadoras vendría de su flexibilidad en términos de software, no de hardware.
Durante estos años Alan alcanzó su mejor momento deportivo, y en 1948 estuvo a punto de participar en el equipo olímpico en los Juegos de Londres, corriendo el maratón. Una lesión le impidió participar. Su mejor tiempo era 2h46m. La medalla de oro fue para el argentino Delfo Cabrera, con un tiempo de 2h35m, uno de los momentos históricos del deporte argentino. Alan seguramente vio el final de la carrera en el estadio de Wembley.
Su trabajo técnico se diversificó, abarcando un montón de áreas. Retomó temas que tenía colgados de antes de la guerra, y empezó cosas nuevas tales como programar una computadora para que jugara al ajedrez. Su fascinación con la relación entre la mente y la materia seguía presente en su obra, y se ocupó también de cuestiones filosóficas relacionadas con la computación. A los 38 años puso sus ideas en un artículo clásico sobre su pregunta favorita: ¿Puede pensar una máquina? La clave de la respuesta, por supuesto, es lo que entendamos por “pensar”.
Turing creía que para el fin del siglo la gente se habría acostumbrado a usar el verbo “pensar” aplicado a una máquina. El fin del siglo ha pasado, y sabemos que lo que las máquinas hacen, al menos por ahora, dista mucho de “pensar”. Nos hemos acostumbrado más bien a que hagan tareas determinísticas con extraordinaria exactitud y celeridad. En la realidad alternativa de la ciencia ficción, por el contrario, a las computadoras le fue mucho mejor. A Turing, que habría cumplido 56 años en 1968 cuando se estrenó 2001: Una Odisea espacial, le habría encantado la idea de una computadora tan inteligente que pudiera tener un colapso nervioso...
Bueno, éste es “el otro” paper famoso de Turing, publicado en la revista Mind en 1950. Aquí desarrolló lo que se llamó el Test de Turing, y que no ha dejado de ser un tema controversial desde entonces. Pero cualquiera que tenga una objeción debería leer el artículo, que es extraordinariamente riguroso. La idea central era tan simple como revolucionaria: lo que importa es el output. No interesa lo que ocurre “adentro”. Si una máquina puede convencerte de que está actuando inteligentemente, ¿quién pude decir que no lo está haciendo?
Muy en el estilo de Computable Numbers, Turing analiza minuciosamente el problema para plantearlo en términos que lo alejen de la especulación filosófica y que permitan un análisis científico. Para lograr esto cambia la pregunta: abandona la cuestión de si la máquina “piensa”, y en cambio se pregunta si puede actuar de manera indistinguible de la de un sujeto pensante. Esta nueva pregunta evita el problema filosófico de la definición de “pensar”, enfocándose en lo que “pensar” permite hacer, y cómo generarlo.
Habiendo aclarado este asunto el propio Turing analiza nueve objeciones, que incluyen todos los principales argumentos que se han esgrimido desde entonces en su contra. Los argumentos van desde la teología hasta la neurología, pasando por la matemática y la percepción extrasensorial (!).
Podemos describir el Test de Turing brevemente, sin entrar en demasiados detalles. Está formulado como un juego con tres participantes: A, B y C en la figura. El participante C puede comunicarse con A y con B sin verlos (usando una especie de "chat", por ejemplo). Pueden conversar sobre cualquier cosa, y C tiene que tratar de decidir si sus interlocutores son personas o máquinas. La cuestión es: ¿puede una computadora asumir el rol de A y hacerse pasar por una persona, sin que C lo descubra? Si puede hacerlo, dice Turing, entonces la máquina es indistinguible de una persona (en ese contexto, por supuesto, pero esa es justamente la idea). Si puede hacerlo la máquina piensa, y quién es quién para decir que no lo hace. El Test de Turing no a dejado de desarrollarse y ramificarse. De hecho todos los días nos encontramos con encarnaciones de un Test de Turing inverso: el CAPTCHA, en el cual una máquina tiene que descubrir si está interactuando con un humano o con otra máquina... La T de CAPTCHA es la inicial de Turing. Pueden chatear con programas que tratan de hacerse pasar por humanos acá.
Este trabajo, a diferencia del primero que era súper técnico y académico, capturó la imaginación de la gente. Turing empezó a salir en la radio y en los diarios. En todo caso, lo que logró este argumento (cuya discusión no ha terminado), fue darles a los diseñadores de hardware una ambición. En poquísimo tiempo las máquinas alcanzaron poderes inimaginables, como sabemos. Su legado quedó plasmado en la visión de un mundo computarizado, que Alan no viviría para ver.
LAS FORMAS DE LA VIDA
Había decodificado el cómputo. Había decodificado mensajes secretos. Había explorado la decodificación de la inteligencia. Era natural que su pensamiento abarcara la posibilidad de decodificar las formas de la vida.
En 1952 publicó otro artículo muy original, el tercero y último de los que constituyen el núcleo de su obra. Su propósito era discutir un mecanismo que proveyera una fundamentación del origen de las formas en los seres vivos, la morfogénesis, un problema tan duro entonces como ahora. Mucho más, en realidad, ya que nada se sabía de ADN’s, ni de códigos genéticos, ni de activación genética, ni de transcripciones de genes en proteínas... Impulsado por la simple fuerza de la lógica Turing proponía que esas formas se originaban espontáneamente, mediante leyes matemáticas sencillas.
Y es importante destacar que no era cuestión de “pongo naranja acá, pongo negro allá”. No es un juego de “pintar por números”. Su modelo representa un sistema que funciona naturalmente y mediante el cual surgen, con la belleza a veces paradójica de la matemática, las alas de las mariposas.
Este mecanismo, que hoy se llama “patrones de Turing” o “bifurcación de Turing”, ha sido usado exitosamente en el modelado de numerosos procesos de morfogénesis. Inclusive se ha puesto en experimentación en la pigmentación de las cebritas (peces comunes de acuarios domésticos) mediante la manipulación de la “condición inicial” en los alevinos y la observación del resultado en el animal adulto.
El mecanismo involucra dos fenómenos físico-químicos separados: por un lado un conjunto de reacciones químicas complejas (con ciclos de realimentación y control, por ejemplo), y un mecanismo de transporte difusivo de las sustancias químicas. Notemos que la difusión, en general, es responsable de la desaparición de cualquier estructura espacial, borroneando las diferencias de concentración (como cuando se pone una gota de tinta en agua). Pero el juego mutuo de los dos fenómenos logra un resultado inesperado. La interacción de la difusión con la reacción química permite un pequeño milagro matemático: la formación espontánea de estructuras espaciales bien definidas y estables.
Con el tiempo las bifurcaciones de Turing se han convertido en una importante herramienta en diversas áreas de la ciencia, no sólo en la embriología, sino en la formación y propagación de estructuras en general, abarcando mucho de nuestro propio trabajo en el Grupo de Física Estadística e Interdisciplinaria en el Centro Atómico Bariloche.
Demos también un ejemplo, sin entrar en detalles. Imaginemos un sistema químico como el que se representa esquemáticamente en la figura. Hay dos substancias, A y B, llamadas "activador" e "inhibidor". El activador cataliza tanto su propia producción como la producción del inhibidor (todo mediante reacciones químicas adecuadas). El inhibidor, en cambio, suprime o reduce la producción del activador. ¡Por eso los llamamos así!
Ahora imaginemos que en una región del espacio hay un exceso de A, de manera que la autocatálisis hace que se dispare la producción de A. Éste, a su vez produce a su propio inhibidor, B, que tendería a mitigar el aumento de A. Debido a la difusión de A, la región con exceso de A tiende a crecer. Pero ojito: si B difunde más rápido que A, el inhibidor llega más lejos y puede llegar a contener espacialmente al activador. Si las condiciones son adecuadas se forma una estructura estacionaria de activación e inhibición. Un mecanismo de este tipo funciona en la retina, donde los fotorreceptores tienen activación local pero inhibición lateral. Este hecho hace posible la ilusión óptica que se muestra en la figura, debido a que las neuronas que reciben luz de las intersecciones blancas reciben también más inhibición lateral que las iluminadas por las calles. Por esta razón las intersecciones parecen más oscuras que las calles.
En 1951 Turing fue elegido miembro de la Royal Society, y todo parecía encaminarse hacia una normal carrera científica destacada. Pero también en 1951 se desencadenaron una serie de eventos que acabarían mal para Alan.
EL TRISTE FINAL
Como consecuencia de una denuncia por robo de su departamento, la policía averiguó que Turing era homosexual, algo que era un delito en Gran Bretaña. Una ley de fines del siglo XIX penaba con hasta dos años de trabajo forzados a los hombres culpables de “gross indecency” en público o en privado. El más famoso de las víctimas de esta ley es Oscar Wilde, que cumplió los 2 años de trabajos forzados en 1895, que probablemente precipitaron su muerte. Alan Turing cayó víctima de este Apartheid sexual.
Ocurrió lo siguiente: Turing conoció un muchacho y empezó una relación con él. Algunas semanas después esta persona dejó entrar a un cómplice en el departamento de Alan y le robó algo de dinero y un reloj de su padre. Turing era tremendamente honesto, y paradójicamente el autor de Computable Numbers era exactamente lo opuesto de lo que se llama “calculador”. Le habían robado, así que acudió a la policía, sin “calcular” las consecuencias. Y les contó todo, y hasta les dio una declaración por escrito y en estilo impecable con todos los detalles. Fue un desastre. El robo fue resuelto sin mayor complicación y el ladrón fue capturado. Pero de golpe había otro “delito”, la homosexualidad de Turing. Quien, además, gozaba de cierta celebridad por la repercusión de sus ideas sobre la inteligencia artificial, así que se convirtió en una desgracia pública.
Le ofrecieron un año en libertad condicional si se sometía a un tratamiento hormonal, una castración química, con el propósito de “curarlo”. Era un tratamiento con estrógeno, tremendamente humillante y plagado de efectos secundarios. Lo volvió impotente y le crecieron tetas. Es posible que la humillación superara la capacidad de expresarlo, porque por lo demás Turing siguió con su actividad normal. Su trabajo en el modelado de los sistemas biológicos continuó, incluyendo una fuerte componente experimental y otra de computación. También su trabajo en lógica, y en la teoría y el diseño de computadoras, que estaban pasando por un momento de expansión gracias a los primeros transistores. Gracias al apoyo de Max Newman y de sus otros colegas la Universidad no lo expulsó (aunque estuvieron a punto de hacerlo). Pero fue excluído de su trabajo en Bletchley Park, que continuaba siendo ultra-secreto. Eran tiempos de Macartismo y Guerra Fría. Los homosexuales eran sospechosos de debilidad de carácter, y en Estados Unidos estaban siendo expulsados de todos los puestos de seguridad, y los británicos adoptaron la misma práctica. Tal vez pensaban que los muchísimos secretos que Alan conocía serían la tentación de la KGB. Por otra parte, se tomó algunas vacaciones en Noruega y otros lugares donde había una mayor tolerancia con la homosexualidad, lo cual le ponía los pelos de punta al Servicio Secreto, quien lo seguía de cerca y produjo más de una crisis.
En 1953 su tratamiento terminó. ¿Se percató Turing de que las hormonas que le habían dado no sólo habían alterado su libido? ¿Que –de manera similar a la de las sustancias químicas de su modelo de morfogénesis– lo habían modificado a él? Nunca se recuperó, ni física ni intelectualmente. No conocemos detalles de cómo experimentó ese último año. Lo único que sabemos a ciencia cierta es que en el 8 de junio de 1954 fue encontrado muerto en su habitación, a los 41 años de edad. Había una manzana mordida en su mesa de luz. La autopsia determinó un envenenamiento por cianuro (su cerebro olía a cianuro). Según testimonios de sus amigos, Alan siempre había tenido una fascinación por la historia de Blancanieves (la película de Disney es del '37, y había sido una sensación mundial). Dicen que a menudo citaba unos versos del guión: "Dip the apple in the brew, Let the sleeping death seep through". Uno de sus amigos recuerda que después de ver la película comentó un posible suicidio involucrando una manzana y un cierto cableado. Alan, que como matemático era medio raro y dado a la experimentación, por esos días tenía en su casa un laboratorio de electroquímica (su afición infantil), para probar sus modelos de morfogénesis. Y tenía un tarro de cianuro de potasio y uno de solución de cianuro.
Su muerte fue inesperada para sus conocidos. No tuvieron ningún indicio de que podía ocurrir algo así. Todos sabían de su infelicidad y de sus problemas, pero el juicio había pasado, el tratamiento había terminado, la Universidad había confirmado su puesto. Su madre no creyó en el veredicto de suicidio, y siempre sostuvo que había sido un accidente. Según ella, Alan era descuidado en sus experimentos y además todas las noches se comía una manzana. Tal vez el propio Alan lo planeó así, "que parezca un accidente". Había en su escritorio correspondencia escrita y sin mandar. Había entradas para el teatro. Había reservado el uso de la computadora para esa semana. En sus recientes visitas a sus amigos cercanos todo parecía normal. Tenía un montón de trabajos empezados, en lógica, en biología, en física. La única cosa rara era un testamento fechado en febrero de ese año. Si bien no hay evidencia de que la paranoia macartista de esa época haya podido llevar a algún servicio secreto a eliminarlo, es cierto que lo tenían cada vez más acorralado, seguramente exacerbando su sensación de aislamiento y depresión.
EL AÑO DE TURING
Al acercarse el año de su centenario se desclasificaron muchos documentos secretos y creció el interés público en la figura trágica de Turing y en su injusto final. En el año 2009 el Primer Ministro británico Gordon Brown publicó una disculpa oficial por el maltrato que Alan había sufrido. "En nombre del gobierno británico, y de todos aquellos que viven libres gracias al trabajo de Alan, estoy orgulloso de decir: lo lamentamos, pedimos perdón. Te merecías algo mejor."
Por esa época se presentó también una solicitud masiva de indulto, con la idea de limpiar su memoria en preparación para el centenario. La resolución judicial se conoció a principios de este año. Increíblemente, la petición de indulto fue rechazada. Uno podría decir: “ah, claro, no cometió ningún delito, no hay nada que indultar.” Pero el argumento del juez fue, en cambio, que sí había cometido un delito, y había sido bien condenado. Sin palabras.
Se dijo muchas veces que el logo de Apple, la manzana mordida, era un homenaje a Turing. Inclusive originalmente (como ésta de 1976) mostraba los colores del arco iris, que son un emblema del movimiento gay. Apple nunca lo admitió. De hecho, el primer logo de Apple muestra que la manzana es la de Newton. Pero bueno, a lo mejor en algún momento a alguien se le ocurrió el homenaje. De todos modos, se non è vero, è ben trovato.
Post scriptum: El 24 de diciembre de 2013 la Reina Elizabeth II, por iniciativa del Gobierno Británico, decretó un indulto a favor de Alan Turing. El procedimiento terminó en agosto de 2014, y hoy Alan Turing está oficialmente indultado de su "crimen".
Leí varias biografías de Turing este año. La mejor, definitivamente, es Alan Turing: The enigma, de Andrew Hodges. Hodges mantiene un enorme sitio dedicado a Alan Turing. También imprescindible es The annotated Turing, de Charles Petzold. En febrero de 2012 la revista Nature dedicó su edición al centenario de Alan Turing, con un montón de notas interesantes.
Algunas de las fotos e imágenes que ilustran estas notas están tomadas de distintas fuentes on line, apelando a un estricto fair use. El copyright de las imágenes registradas pertenece a sus respectivos propietarios. El resto de las imágenes es de mi autoría.
¿En qué estábamos? Terminada la guerra, Turing regresó a la vida académica y a su nueva pasión: construir un cerebro, usando la novísima tecnología electrónica. Su experiencia con máquinas de desencriptar durante la guerra (de las cuales no podía decir ni una palabra, naturalmente), lo ponía en una posición excelente para esta tarea. Fue designado director científico en un área del Laboratorio Nacional de Física creada específicamente para este propósito.
LA INTELIGENCIA ARTIFICIAL
Alan se desentendió un poco de los problemas de hardware y durante un par de años se dedicó a diseñar los rudimentos del software, fundamentalmente a lo que hoy llamaríamos un lenguaje de programación. Lamentablemente su trabajo en el Laboratorio no prosperó, por dificultades personales. Turing era un poco excéntrico, así que el trabajo primordialmente administrativo que tenía en el Laboratorio no le atraía mucho. En eso, su amigo y antiguo profesor Max Newman le ofreció un cargo en la Universidad de Manchester, un importante puesto en el flamante Laboratorio de Computación, así que Alan renunció al Laboratorio Nacional. En Manchester finalmente se construyó una computadora a fines de los '40, si bien no de acuerdo a los lineamientos de Turing, quien creía que el poder de las computadoras vendría de su flexibilidad en términos de software, no de hardware.
Durante estos años Alan alcanzó su mejor momento deportivo, y en 1948 estuvo a punto de participar en el equipo olímpico en los Juegos de Londres, corriendo el maratón. Una lesión le impidió participar. Su mejor tiempo era 2h46m. La medalla de oro fue para el argentino Delfo Cabrera, con un tiempo de 2h35m, uno de los momentos históricos del deporte argentino. Alan seguramente vio el final de la carrera en el estadio de Wembley.
Su trabajo técnico se diversificó, abarcando un montón de áreas. Retomó temas que tenía colgados de antes de la guerra, y empezó cosas nuevas tales como programar una computadora para que jugara al ajedrez. Su fascinación con la relación entre la mente y la materia seguía presente en su obra, y se ocupó también de cuestiones filosóficas relacionadas con la computación. A los 38 años puso sus ideas en un artículo clásico sobre su pregunta favorita: ¿Puede pensar una máquina? La clave de la respuesta, por supuesto, es lo que entendamos por “pensar”.
Muy en el estilo de Computable Numbers, Turing analiza minuciosamente el problema para plantearlo en términos que lo alejen de la especulación filosófica y que permitan un análisis científico. Para lograr esto cambia la pregunta: abandona la cuestión de si la máquina “piensa”, y en cambio se pregunta si puede actuar de manera indistinguible de la de un sujeto pensante. Esta nueva pregunta evita el problema filosófico de la definición de “pensar”, enfocándose en lo que “pensar” permite hacer, y cómo generarlo.
Habiendo aclarado este asunto el propio Turing analiza nueve objeciones, que incluyen todos los principales argumentos que se han esgrimido desde entonces en su contra. Los argumentos van desde la teología hasta la neurología, pasando por la matemática y la percepción extrasensorial (!).
Había decodificado el cómputo. Había decodificado mensajes secretos. Había explorado la decodificación de la inteligencia. Era natural que su pensamiento abarcara la posibilidad de decodificar las formas de la vida.
En 1952 publicó otro artículo muy original, el tercero y último de los que constituyen el núcleo de su obra. Su propósito era discutir un mecanismo que proveyera una fundamentación del origen de las formas en los seres vivos, la morfogénesis, un problema tan duro entonces como ahora. Mucho más, en realidad, ya que nada se sabía de ADN’s, ni de códigos genéticos, ni de activación genética, ni de transcripciones de genes en proteínas... Impulsado por la simple fuerza de la lógica Turing proponía que esas formas se originaban espontáneamente, mediante leyes matemáticas sencillas.
Este mecanismo, que hoy se llama “patrones de Turing” o “bifurcación de Turing”, ha sido usado exitosamente en el modelado de numerosos procesos de morfogénesis. Inclusive se ha puesto en experimentación en la pigmentación de las cebritas (peces comunes de acuarios domésticos) mediante la manipulación de la “condición inicial” en los alevinos y la observación del resultado en el animal adulto.
El mecanismo involucra dos fenómenos físico-químicos separados: por un lado un conjunto de reacciones químicas complejas (con ciclos de realimentación y control, por ejemplo), y un mecanismo de transporte difusivo de las sustancias químicas. Notemos que la difusión, en general, es responsable de la desaparición de cualquier estructura espacial, borroneando las diferencias de concentración (como cuando se pone una gota de tinta en agua). Pero el juego mutuo de los dos fenómenos logra un resultado inesperado. La interacción de la difusión con la reacción química permite un pequeño milagro matemático: la formación espontánea de estructuras espaciales bien definidas y estables.
Con el tiempo las bifurcaciones de Turing se han convertido en una importante herramienta en diversas áreas de la ciencia, no sólo en la embriología, sino en la formación y propagación de estructuras en general, abarcando mucho de nuestro propio trabajo en el Grupo de Física Estadística e Interdisciplinaria en el Centro Atómico Bariloche.
En 1951 Turing fue elegido miembro de la Royal Society, y todo parecía encaminarse hacia una normal carrera científica destacada. Pero también en 1951 se desencadenaron una serie de eventos que acabarían mal para Alan.
EL TRISTE FINAL
Como consecuencia de una denuncia por robo de su departamento, la policía averiguó que Turing era homosexual, algo que era un delito en Gran Bretaña. Una ley de fines del siglo XIX penaba con hasta dos años de trabajo forzados a los hombres culpables de “gross indecency” en público o en privado. El más famoso de las víctimas de esta ley es Oscar Wilde, que cumplió los 2 años de trabajos forzados en 1895, que probablemente precipitaron su muerte. Alan Turing cayó víctima de este Apartheid sexual.
Ocurrió lo siguiente: Turing conoció un muchacho y empezó una relación con él. Algunas semanas después esta persona dejó entrar a un cómplice en el departamento de Alan y le robó algo de dinero y un reloj de su padre. Turing era tremendamente honesto, y paradójicamente el autor de Computable Numbers era exactamente lo opuesto de lo que se llama “calculador”. Le habían robado, así que acudió a la policía, sin “calcular” las consecuencias. Y les contó todo, y hasta les dio una declaración por escrito y en estilo impecable con todos los detalles. Fue un desastre. El robo fue resuelto sin mayor complicación y el ladrón fue capturado. Pero de golpe había otro “delito”, la homosexualidad de Turing. Quien, además, gozaba de cierta celebridad por la repercusión de sus ideas sobre la inteligencia artificial, así que se convirtió en una desgracia pública.
Su muerte fue inesperada para sus conocidos. No tuvieron ningún indicio de que podía ocurrir algo así. Todos sabían de su infelicidad y de sus problemas, pero el juicio había pasado, el tratamiento había terminado, la Universidad había confirmado su puesto. Su madre no creyó en el veredicto de suicidio, y siempre sostuvo que había sido un accidente. Según ella, Alan era descuidado en sus experimentos y además todas las noches se comía una manzana. Tal vez el propio Alan lo planeó así, "que parezca un accidente". Había en su escritorio correspondencia escrita y sin mandar. Había entradas para el teatro. Había reservado el uso de la computadora para esa semana. En sus recientes visitas a sus amigos cercanos todo parecía normal. Tenía un montón de trabajos empezados, en lógica, en biología, en física. La única cosa rara era un testamento fechado en febrero de ese año. Si bien no hay evidencia de que la paranoia macartista de esa época haya podido llevar a algún servicio secreto a eliminarlo, es cierto que lo tenían cada vez más acorralado, seguramente exacerbando su sensación de aislamiento y depresión.
EL AÑO DE TURING
Por esa época se presentó también una solicitud masiva de indulto, con la idea de limpiar su memoria en preparación para el centenario. La resolución judicial se conoció a principios de este año. Increíblemente, la petición de indulto fue rechazada. Uno podría decir: “ah, claro, no cometió ningún delito, no hay nada que indultar.” Pero el argumento del juez fue, en cambio, que sí había cometido un delito, y había sido bien condenado. Sin palabras.
Post scriptum: El 24 de diciembre de 2013 la Reina Elizabeth II, por iniciativa del Gobierno Británico, decretó un indulto a favor de Alan Turing. El procedimiento terminó en agosto de 2014, y hoy Alan Turing está oficialmente indultado de su "crimen".
Leí varias biografías de Turing este año. La mejor, definitivamente, es Alan Turing: The enigma, de Andrew Hodges. Hodges mantiene un enorme sitio dedicado a Alan Turing. También imprescindible es The annotated Turing, de Charles Petzold. En febrero de 2012 la revista Nature dedicó su edición al centenario de Alan Turing, con un montón de notas interesantes.
Algunas de las fotos e imágenes que ilustran estas notas están tomadas de distintas fuentes on line, apelando a un estricto fair use. El copyright de las imágenes registradas pertenece a sus respectivos propietarios. El resto de las imágenes es de mi autoría.
08/09/2012
El enigma de Turing (parte 3)
Esta es la tercera parte de la serie El enigma de Turing. Link a la primera parte. Link a la segunda parte.
Habíamos dejado a Turing regresando de Princeton. Mientras trabajaba en sus temas de Lógica y la situación política en Europa se complicaba cada vez más, Turing se había interesado por la criptografía: la ciencia de crear y romper códigos para mandar mensajes cifrados. Se le ocurrió de que un buen método criptográfico sería convertir un texto en un número (como había hecho Gödel con las proposiciones matematicas, y él mismo con las tablas de las máquinas de computar) y multiplicarlo por otro número muy grande. Así el desencriptado se convertía en un problema de factorización, que podía ser muy difícil. Fue una idea premonitoria, porque así funciona la mayoría de los códigos de encriptación hoy en día (cada vez que usamos la tarjeta de crédito o nos conectamos a Gmail, por ejemplo). Turing, que tenía un gusto por armar cosas con sus propias manos (a diferencia de muchos matemáticos) inclusive fabricó una máquina electromecánica, con relés y electroimanes, que hacían esta codificación. ¡Él mismo enrolló los solenoides para fabricar relés caseros!
EL ENIGMA
Finalmente estalló la guerra. Por ser una nación insular, la subsistencia de Gran Bretaña dependía fuertemente del transporte marítimo de mercadería. Enormes convoys de suministros, fuertemente escoltados, cruzaban permanentemente el Atlántico. Sin embargo, las pérdidas eran enormes, y ponían en peligro la supervivencia de Inglaterra. El principal peligro venía de los U-boats, los submarinos alemanes, rápidos e indetectables, que recibían instrucciones codificadas del Alto Mando.
Las transmisiones eran codificadas mediante una máquina llamada Enigma. Tenía un teclado sencillo, sobre el cual había unas lamparitas que reproducían el mismo arreglo de letras. Adentro había un circuito eléctrico de configuración variable. Cuando se presionaba una letra en el teclado, el circuito la codificaba en otra letra y se encendía la lamparita correspondiente. Al mismo tiempo, el mecanismo variable (unas ruedas, que se ven en la foto atrás de las lamparitas) avanzaba un paso, de manera que la siguiente letra que se presionaba era codificada por un circuito distinto. El mensaje codificado se enviaba por correo o telégrafo. La persona que recibía el mensaje encriptado configuraba su máquina de la misma manera que la codificadora (con una clave preestablecida, que no se enviaba), tipeaba el galimatías, y las lamparitas daban el mensaje decodificado. No era más que un código de substitución, mucho más sencillo que la multiplicación de números grandes que había ideado Alan. Pero el mecanismo de los rotores móviles hacía que una misma letra se substituyera por letras distintas a lo largo del mensaje, dificultando enormemente su descifrado.
En 1932 tres matemáticos polacos habían desarrollado un método para decodificar los mensajes de la Enigma. De una manera que encajaba perfectamente con el pensamiento de Turing habían concluido que, si se usaba una máquina para codificar el mensaje, había que usar una máquina para romper el código. Y diseñaron una máquina, a la que llamaron Bomb, que hacía el trabajo. No se sabe si eligieron el nombre por el tic-tac que hacía la máquina, o por un postre helado que les encantaba.
BLETCHLEY PARK
Los británicos ya habían empezado a colaborar con los polacos, y lograron obtener toda la información sobre la Bomb antes de la ocupación de Polonia. Pero el Servicio de Criptografía británico era más bien anticuado: un puñado de clasicistas y traductores, algo completamente inútil para el conflicto que se venía. En particular, eran incapaces de descifrar la Enigma. Alguien tuvo el buen tino de reclutar un pequeño grupo de especialistas “de tipo profesoral”, matemáticos, físicos, ingenieros y campeones de ajedrez (!). Uno de ellos fue Alan Turing, recién regresado de Princeton. Luchando a brazo partido contra la burocracia de la administración pública y la rigidez de la institución militar lograron transformar por completo el Servicio. Su mejor argumento, por supuesto, es que ellos sí podían decodificar los mensajes cifrados. Finalmente reunieron un equipo enorme, multidisciplinario y súper secreto en una mansión campestre llamada Bletchley Park. Llegaron a trabajar allí más de 10000 personas, así que no cabían todos en el caserón. Se construyeron unos “huts”, unas barracas. Turing estuvo a cargo del Hut 8, dedicado al desencriptado de los mensajes de la Marina alemana.
En Bletchley Park rediseñaron y mejoraron la máquina polaca y la llamaron Bombe. Turing demostró que era posible reducir enormemente el espacio de búsqueda de códigos aplicando la lógica matemática: había recorridos en el espacio de configuraciones del circuito que llevaban a contradicciones, y que podían ser abandonados. Para implementar esta mecanización de las deducciones lógicas no se necesitaba matemática muy avanzada, eran más bien aplicaciones de conceptos sencillos. ¡Nada como el problema de Hilbert! De hecho, las Bombe no eran máquinas de Turing. Además, la decodificación no era en absoluto automática. Dependía en buena parte de "adivinar" partes de los mensajes, algo que era posible sólo gracias a la rígida estructura de los mensajes militares. Para ensamblar esta adivinación con la búsqueda sistemática, la teoría requería la formalización de los procedimientos de toma de decisión basada en información parcial. El formalismo que desarrolló Turing es esencialmente idéntico al de Claude Shannon, a quien Alan conoció pocos años después en Bell Labs, y que hoy llamamos Teoría de la Información.
BOMBE VS. ENIGMA
La primera Turing Bombe entró en funcionamiento en 1940. Pesaba una tonelada y simulaba el funcionamiento en paralelo de 30 Enigmas (la de la foto es una reconstrucción reciente). Finalmente lograron descifrar los mensajes codificados con la Enigma. Al principio cada mensaje les llevaba semanas de trabajo. Pero rápidamente lograron reducir el tiempo a minutos. Los mensajes de la Luftwaffe empezaron a desencriptarse a fines de 1940, pero recién a mediados del '41 pudieron hacerlo con los de los U-boat, que usaban una Enigma más sofisticada. Alcanzaron tal maestría que las pérdida navales cayeron significativamente. Sorprendentemente, los alemanes estaban tan convencidos de la infalibilidad de la Enigma, que en lugar de sospechar que les estaban descifrando los mensajes, sospecharon que los estaban espiando. Así que dedicaron esfuerzos inútiles a cazar espías mientras en Bletchley Park leían sus mensajes como quien lee el Argentinisches Tageblatt.
En febrero de 1942 los alemanes agregaron un nuevo rotor a la Enigma naval y los ingleses perdieron la ventaja. Las pérdidas aumentaron enorme y peligrosamente. Los aliados empezaron a perder más tonelaje que el que podían construir en los astilleros. ¡Si la situación no se revertía, perderían la batalla del Atlántico! En Bletchley Park empezaron a usar la novísima tecnología electrónica (en lugar de electromecánica) que estaba empezando a usarse en las compañías de teléfonos, para alcanzar mayores velocidades de cálculo. Pero fue una tecnología que terminó usándose en otro sistema, no en la Enigma.
En noviembre 1942 Turing fue enviado a Estados Unidos para coordinar al más alto nivel las actividades de desencriptado en conjunto, intentando resolver la crisis de la Enigma naval. Se pasó dos meses en Bell Labs, donde conoció a Harry Nyquist y a Shannon, dos matemáticos que en la década siguiente harían trabajos fundamentales del inicio de la era digital. En Bell querían encriptar las transmisiones telefónicas transatlánticas entre Roosevelt y Churchill. Los métodos que idearon son la base de todas las técnicas de codificación digital de señales analógicas que usamos ahora todo el tiempo, tales como el JPG y el MP3.
A principios de marzo del 43 descubrieron una debilidad de la nueva Enigma y pudieron volver a desencriptarla. Inglaterra y Estados Unidos recobraron el control del Atlántico, situación que se mantendría hasta el final de la guerra. Uno a uno, todos los modelos de Enigma cayeron ante el poder de cómputo de Bletchley Park.
UN CEREBRO ELECTRÓNICO
Alan volvió a Inglaterra, pero su trabajo ya no era esencial en Bletchley Park, así que pudo liberarse un poco de sus responsabilidades. Se convirtió en una especie de consultor todo-propósito del Servicio, y se dedicó a aprender electrónica y a un proyecto propio de codificación electrónica del lenguaje hablado. Su posición administrativa era muy influyente a pesar de su juventud (tenía 30 años), y fue fundamental para lograr el apoyo gubernamental para empezar a desarrollar máquinas más veloces que las Bombes, basadas en la electrónica. Las primeras de este tipo se llamaron Colossus. Tenían miles de válvulas, y nadie les tenía mucha fe al principio, pero funcionaron. Fueron las primeras computadoras electrónicas, pero a diferencia de las computadoras modernas, estaban también dedicadas a un propósito específico, como las Bombes. Alan, al ver funcionar estas máquinas desencriptadoras, se entusiasmó vislumbrando el poder que una verdadera máquina de Turing podría lograr con la ayuda de la tecnología electrónica. Empezó a diseñar la construcción de su propia Máquina Universal. Se refería a su proyecto como “construir un cerebro”.
¡Y de nuevo le ganaron de mano del otro lado del Atlántico! Se publicó un proyecto, llamado EDVAC, proponiendo construir precisamente lo que quería hacer Alan: una computadora electrónica, digital binaria y programable. John von Neumann, uno de sus principales promotores, le enchufaba el Computable Numbers a cada persona que se involucraba en el proyecto. La reacción en Inglaterra fue, con todo, razonablemente buena: crearon un laboratorio para llevar adelante un proyecto similar, y Alan Turing fue nombrado director científico. La guerra, además, había terminado. ¿Qué más se podía pedir?
Finaliza en la Cuarta Parte de El enigma de Turing...
La EDVAC finalmente se construyó, y fue la primera computadora en el sentido moderno. Usaba una memoria externa de cable magnético, su memoria interna era acústica (aproximadamente 1 kilobyte, más tres registos de una palabra cada uno), operaba a una velocidad de procesamiento de menos de 1 kilohertz, tenía una unidad de control con osciloscopio y un timer. Sus 6000 válvulas de vacío y 12 mil diodos consumían 56 kilowatts. Ocupaba 45 metros cuadrados, pesaba 8 toneladas y la operaban 30 personas en cada turno de 8 horas. Costó 500 mil dólares, empezó a funcionar en 1951 y se la usó durante 10 exitosos años.
Habíamos dejado a Turing regresando de Princeton. Mientras trabajaba en sus temas de Lógica y la situación política en Europa se complicaba cada vez más, Turing se había interesado por la criptografía: la ciencia de crear y romper códigos para mandar mensajes cifrados. Se le ocurrió de que un buen método criptográfico sería convertir un texto en un número (como había hecho Gödel con las proposiciones matematicas, y él mismo con las tablas de las máquinas de computar) y multiplicarlo por otro número muy grande. Así el desencriptado se convertía en un problema de factorización, que podía ser muy difícil. Fue una idea premonitoria, porque así funciona la mayoría de los códigos de encriptación hoy en día (cada vez que usamos la tarjeta de crédito o nos conectamos a Gmail, por ejemplo). Turing, que tenía un gusto por armar cosas con sus propias manos (a diferencia de muchos matemáticos) inclusive fabricó una máquina electromecánica, con relés y electroimanes, que hacían esta codificación. ¡Él mismo enrolló los solenoides para fabricar relés caseros!
EL ENIGMA
En 1932 tres matemáticos polacos habían desarrollado un método para decodificar los mensajes de la Enigma. De una manera que encajaba perfectamente con el pensamiento de Turing habían concluido que, si se usaba una máquina para codificar el mensaje, había que usar una máquina para romper el código. Y diseñaron una máquina, a la que llamaron Bomb, que hacía el trabajo. No se sabe si eligieron el nombre por el tic-tac que hacía la máquina, o por un postre helado que les encantaba.
BLETCHLEY PARK
BOMBE VS. ENIGMA
En febrero de 1942 los alemanes agregaron un nuevo rotor a la Enigma naval y los ingleses perdieron la ventaja. Las pérdidas aumentaron enorme y peligrosamente. Los aliados empezaron a perder más tonelaje que el que podían construir en los astilleros. ¡Si la situación no se revertía, perderían la batalla del Atlántico! En Bletchley Park empezaron a usar la novísima tecnología electrónica (en lugar de electromecánica) que estaba empezando a usarse en las compañías de teléfonos, para alcanzar mayores velocidades de cálculo. Pero fue una tecnología que terminó usándose en otro sistema, no en la Enigma.
En noviembre 1942 Turing fue enviado a Estados Unidos para coordinar al más alto nivel las actividades de desencriptado en conjunto, intentando resolver la crisis de la Enigma naval. Se pasó dos meses en Bell Labs, donde conoció a Harry Nyquist y a Shannon, dos matemáticos que en la década siguiente harían trabajos fundamentales del inicio de la era digital. En Bell querían encriptar las transmisiones telefónicas transatlánticas entre Roosevelt y Churchill. Los métodos que idearon son la base de todas las técnicas de codificación digital de señales analógicas que usamos ahora todo el tiempo, tales como el JPG y el MP3.
A principios de marzo del 43 descubrieron una debilidad de la nueva Enigma y pudieron volver a desencriptarla. Inglaterra y Estados Unidos recobraron el control del Atlántico, situación que se mantendría hasta el final de la guerra. Uno a uno, todos los modelos de Enigma cayeron ante el poder de cómputo de Bletchley Park.
UN CEREBRO ELECTRÓNICO
¡Y de nuevo le ganaron de mano del otro lado del Atlántico! Se publicó un proyecto, llamado EDVAC, proponiendo construir precisamente lo que quería hacer Alan: una computadora electrónica, digital binaria y programable. John von Neumann, uno de sus principales promotores, le enchufaba el Computable Numbers a cada persona que se involucraba en el proyecto. La reacción en Inglaterra fue, con todo, razonablemente buena: crearon un laboratorio para llevar adelante un proyecto similar, y Alan Turing fue nombrado director científico. La guerra, además, había terminado. ¿Qué más se podía pedir?
Finaliza en la Cuarta Parte de El enigma de Turing...
La EDVAC finalmente se construyó, y fue la primera computadora en el sentido moderno. Usaba una memoria externa de cable magnético, su memoria interna era acústica (aproximadamente 1 kilobyte, más tres registos de una palabra cada uno), operaba a una velocidad de procesamiento de menos de 1 kilohertz, tenía una unidad de control con osciloscopio y un timer. Sus 6000 válvulas de vacío y 12 mil diodos consumían 56 kilowatts. Ocupaba 45 metros cuadrados, pesaba 8 toneladas y la operaban 30 personas en cada turno de 8 horas. Costó 500 mil dólares, empezó a funcionar en 1951 y se la usó durante 10 exitosos años.
25/08/2012
El enigma de Turing (parte 2)
Segunda parte de la serie sobre Alan Turing en el centenario de su nacimiento. La primera parte está acá.
Dónde estábamos: Alan tomó el curso de Lógica Matemática de Max Newman en King's College. Terminaba con los teoremas de Gödel, que daban por tierra con el ambicioso Programa de Hilbert. Turing se interesó en un resquicio que Gödel no había resuelto, el Entscheidungsproblem, el problema de la decidibilidad: ¿Existe un método para decidir si una dada afirmación matemática es demostrable? Turing resolvió este problema, trabajando en completa soledad a los 23 años de edad, y de paso en el camino inventó la ciencia de la computación.
COMPUTABLE NUMBERS
Su contribución está en este trabajo, publicado en 1936 en los Proceedings de la London Mathematical Society. Tiene un título intimidante, con una palabra inventada, “computable”, y la famosa palabra de Hilbert tan difícil de pronunciar sin que alguien diga ¡salud!. Es notable que Turing ponga el énfasis del título en los números computables y no en la demostración del problema de Hilbert. A pesar de la relevancia académica de resolver un problema de Hilbert, parece que Turing se diera cuenta de que lo que había inventado estaba bueno, y que el problema de la decisión resultaba apenas una aplicación. Pero en realidad nadie (ni siquiera Turing) se dio remotamente cuenta de su profundo significado hasta mucho tiempo después. Todas las computadoras modernas, desde las laptops a los videojuegos, desde los teléfonos hasta los robots que aterrizan en Marte, son exactamente lo que Turing mostró en este paper.
En la segunda página del artículo, promediando el larguísimo resumen, nos encontramos con la conclusión de Turing (segundo recuadro en la imagen): el Entscheidungsproblem no tiene solución. En las siguientes 28 páginas Turing no vuelve a hablar del Entscheidungsproblem.
Alan le mostró el manuscrito a su profesor de Lógica. Newman había recibido justo en esos días un preprint de Alonzo Church, un matemático norteamericano de la prestigiosa escuela de Lógica de Princeton. Al mismo tiempo que Turing y de manera independiente Church había llegado a la misma conclusión sobre el problema de la decidibilidad. Así que parte de la originalidad del trabajo de Turing se desvaneció. El approach de Church era de todos modos muy diferente, eso quedó claro desde el principio. Y además estaba el valor teórico de lo que llegaría a ser el fundamento de la ciencia de la computación. Así que Newman apoyó la publicación del trabajo. Pero Alan tuvo que agregar a último momento ese párrafo que vemos asomar en la imagen, al final del largo resumen. Y agregó también un apéndice demostrando la equivalencia entre su “computabilidad” y la “calculabilidad efectiva” de Church.
Si uno sobrevive al título, es posible que la tipografía gótica de la notación termine de intimidarlo. Afortunadamente existe un libro, The Annotated Turing, de Charles Petzold, donde se explica todo párrafo por párrafo.
MÁQUINAS DE TURING
Como decíamos, la cuestión de la decidibilidad era la inspiración del trabajo, pero la mayor parte del mismo se trata de lo que Turing llama “números computables”, cuyo estudio ocupa el primer 60% del artículo, y que se pueden entender sin saber nada de Lógica ni del Programa de Hilbert.
¿Y qué es un número computable? Bueno, un número computable es un número cuyos decimales pueden ser escritos por una máquina. Era algo muy raro de decir en 1936. “Computadora”, en esa época, no significaba una
máquina, como significa ahora. Significaba una persona, en general una
chica. Una persona que calcula. Lo que propone Turing es automatizar todo el proceso para que en lugar de una persona lo haga una máquina. Habían existido máquinas de calcular en siglos anteriores, y en ese mismo momento se estaban diseñando máquinas de calcular, de sumar, de resolver ecuaciones diferenciales. Pero lo cierto es que en 1936 no existía ninguna máquina capaz de hacer lo que Turing pedía de manera tan general. Las computadoras (en el sentido moderno) no existían. Turing sacó el
concepto de su galera matemática. Sólo años más tarde la tecnología
electrónica permitiría convertir estas ideas en verdadera ingeniería.
Turing empieza a explicar lo que quiere decir por “calculable por una máquina”. La justificación viene de la asociación entre lo humano y la máquina, que se convertiría en un tema central a lo largo de toda su obra. Se plantea la cuestión de qué podría lograr una persona llevando a cabo una tarea metódica, repetitiva y mecánica. Y esto lo lleva a formular su análisis en términos de una “máquina” teórica, capaz de realizar operaciones elementales, predefinidas, sobre una secuencia de símbolos impresos en una cinta de papel. Argumenta que cualquier cosa que a uno se le pueda ocurrir que significa “metódico”, esta máquina lo podría hacer tan bien como una persona.
La máquina es increíblemente sencilla. En la figura muestro un ejemplo. Tiene un "scanner" que se desplaza sobre la cinta, leyendo los números uno por uno. La máquina tiene un conjunto de estados posibles. El scanner es el trapecio negro, que además muestra el estado de la máquina en cada paso de tiempo. La nubecita muestra el número leído por el scanner. La "tarea repetitiva y metódica" está especificada mediante una tabla que, de acuerdo al estado y al número leído, dice qué tiene que hacer. Y lo que puede hacer es muy limitado: puede borrar o escribir un número, puede cambiar de estado, y puede moverse a la izquierda o a la derecha. La tabla de este ejemplo define una máquina que suma dos números. En la cinta están inicialmente escritos los números 3 y 4 (en representación "unaria"), y la máquina los suma, así como muestra la animación. Fijensé, no hay trampa. La máquina suma. En terminología moderna, el “método” que lleva a cabo la máquina es un algoritmo. La tabla que define las operaciones que hace la máquina con los símbolos impresos, es el software. Turing inventó el software.
Turing muestra cómo estas máquinas, así de sencillas, no sólo pueden escribir sus "números computables", sino que también pueden llevar adelante cualquier cálculo matemático imaginable, tan sólo moviendo unos y ceros de atrás para adelante y de adelante para atrás. Más aún, cualquier tipo de información podía codificarse numéricamente y procesarse de la manera que uno quisiese. Como ven, son todos conceptos súper familiares para nosotros. No así en 1936. Fue el momento en que nació la Era Digital.
Un número computable, entonces, es un número que una de estas máquinas escribe en una cinta de papel. Claramente, los números enteros son computables. También los números racionales, las fracciones. Aun las que tienen un desarrollo decimal con infinitas cifras, como 1/3. ¿Y los números más raros? Pi, por ejemplo, es computable. Obvio, ya que sabemos cómo calcularlo con cuantos decimales queramos, con lápiz y papel. Lo mismo con la raíz cuadrada de 2, etc. Esto de los números computables es bastante loco. Parecen no tener una relación obvia con los números irracionales, o con los números trascendentes, o cualquiera de las otras categorías que conocemos. ¿Entonces? ¿Todos los números reales serán computables?
No. Turing demuestra que estas máquinas, que tienen un número finito de estados posibles, son enumerables, es decir son tantas como los números naturales. Y hay muchos más números reales que números naturales. Muchos, muchos más. Así que la mayor parte de los números son no computables. No importa cuánto nos esforcemos, nunca aparecerán como resultado de nuestros cálculos. ¿No es loquísimo? Cabe preguntarse qué tan reales son los números reales que no son computables. Así que hoy en día hay toda una rama del análisis de los números computables en lugar de los reales.
Bueno. Ya que las máquinas son numerables, Turing las numera. Es decir, muestra cómo se pueden codificar las tablas (que definen a las máquinas) de manera numérica. Es un lío, pero se puede hacer metódicamente. Uno termina con una máquina descripta, en lugar de por símbolos que representan las operaciones, por una “definición estándard” que es un número entero. Es claramente un approach inspirado en el Teorema de Gödel y su codificación numérica de las expresiones matemáticas. De yapa, tenemos una manera de generar máquinas de Turing: los números enteros. Muchas de ellas no funcionarán, muchas calcularán trivialidades, otras calcularán las mismas cosas de maneras diferentes, algunas más rápido, algunas más lento, algunas con pequeñas diferencias... Algunas ni siquiera se detendrán. ¡Es como la Biblioteca de Babel de Borges!
Con un método diagonal inventado por Georg Cantor en el siglo XIX, y que también es central en el razonamiento de Gödel, es fácil construir un número no computable. La idea está ilustrada en la figura. Supongamos que tenemos todas las máquinas ya numeradas y prolijamente ordenadas. La primera máquina, por ejemplo, computa el número 1. La segunda, digamos, computa pi. La tercera un pi aproximado, etc, etc. Ahora escribimos un número de la siguiente manera, que nos asegura que el número no está en la tabla (es el número de colores de la fila amarilla en la figura): miramos el primer dígito del número computado por T1, y lo cambiamos (por ejemplo, sumando 1). Después revisamos el segundo número, encontramos su segundo dígito, y hacemos lo mismo. Así vamos recorriendo la diagonal de la tabla, y escribiendo un número cuyo i-ésimo dígito es distinto del i-ésimo dígito del i-ésimo número. Este número no está en la lista, así que no es un número computable. ¿Por qué? ¿No podría haber una máquina Tj, con j por ahí abajo, que compute este número? No, porque el j-ésimo dígito del número computado por Tj es distinto del j-ésimo dígito del número colorido. ¡Así lo construímos! Y como en la tabla están todas las máquinas que computan números, no hay ninguna máquina que pueda computar el número de colores. Chan.
LA MÁQUINA UNIVERSAL
Pero ¿no hay aquí una contradicción? El método de Cantor es tan fácil de explicar que parece completamente mecanizable, ¿cómo puede ser que ese número sea no computable? ¿No debería haber una “máquina de Cantor” capaz de calcularlo? Esta máquina debería producir la tabla de la máquina T1, ejecutarla hasta el primer dígito, sumar 1 y escribir, después producir la segunda máquina, ejecutarla hasta el segundo dígito, sumar 1 y escribir, y así siguiendo. Es decir, debe ser una máquina capaz de emular lo que hacen las otras máquinas. Una máquina universal.
En algún sentido, la Máquina Universal de Turing es la única que necesitamos: no se necesita una máquina para cada tarea computable. La máquina universal ha llegado para acabar con todas las máquinas. La máquina universal es, decimos hoy, programable.
La máquina universal es tan importante para el argumento de Turing que éste la construye con todo detalle, dando explícitamente su tabla de estados y operaciones, a un nivel que es muy difícil de asimilar con facilidad. Si uno ha de creerle al Annotated Turing, además, la descripción no está libre de bugs. Pero, dejando de lado esto, Turing acababa de hacer algo extraordinario: había demostrado la generalidad de la computación, había mostrando cómo una máquina programable puede llevar a cabo la operación de cualquier máquina de computar. Es sin duda uno de los grandes logros intelectuales del siglo XX.
Ciertamente, Turing no “inventó” la computadora. Pero hasta ese momento la suposición habitual en la gente que trabajaba en el tema era que cada computadora debería ser diseñada para un propósito específico. Aún en la década del 50, más de 15 años después de Computable Numbers, los ingenieros que diseñaban las primeras computadoras digitales no habían acabado de visualizar a la computadora como una herramienta lógica, más que de cálculo. Así que no es de sorprender que el rol de Turing en la historia de la computación se cuente de manera desigual en distintos libros. Una cosa es contar la historia de la computadora desde un punto de vista de la ingeniería o del mercado. Y otro es el punto de vista que considera a las computadoras como materializaciones de conceptos matemáticos. En este último caso, el papel de Turing es destacadísimo.
¿Y el Entscheidungsproblem?
El método diagonal es la clave. La cosa se vuelve sumamente técnica y, depués de todo, no es más que "una aplicación" de las Máquinas. Turing muestra primero que puede construir una máquina que codifica todo el cálculo funcional de Hilbert. Muestra que el Entscheidungsproblem es equivalente a demostrar si la máquina que calcula el número construido con el método diagonal se detiene, y demuestra que este problema no tiene solución. Piece of cake.
PRINCETON
Como no podía ser de otra manera, Turing se fue a Princeton, donde se quedó dos años. Church dirigió su tesis, que completó en 1938. Princeton se había convertido en una meca para la física y la matemática, particularmente con la creación del Instituto de Estudios Avanzados. Gödel lo visitaba todos los años y John von Neumann, Courant, Hardy, Weyl, Einstein y tantos otros se habían establecido allí, muchos de ellos escapando del régimen nazi.
Sus ideas alcanzaron cierta notoriedad, atrayendo incluso la atención de von Neumann, a quien le había encantado Computable Numbers (otro día tal vez hablemos de él). Pero no saltó a la fama ni mucho menos. Su trabajo en Princeton, incluyendo la demostración de que sus conclusiones sobre la decidibilidad coincidían con las de Church, fue el material de su tesis. Esta línea de trabajo, tal vez la más profunda de su carrera, no prosiguió más allá de su doctorado.
Durante su segundo año en Princeton, mientras terminaba la tesis, la situación política en Europa se complicaba cada vez más. Estaba claro que Inglaterra y Alemania pronto entrarían en guerra. A pesar de que von Neumann le ofreció un tentador puesto en el Instituto de Estudios Avanzados, Turing se volvió a Inglaterra, donde no tenía trabajo. Apenas consiguió una beca de King’s College.
Pero rápidamente consiguió un trabajo mejor. Un trabajo secreto, que salvó miles de vidas, permitió la supervivencia de Inglaterra, y ayudó a los Aliados a ganar la guerra.
Continúa en la Parte 3 de El enigma de Turing...
Dónde estábamos: Alan tomó el curso de Lógica Matemática de Max Newman en King's College. Terminaba con los teoremas de Gödel, que daban por tierra con el ambicioso Programa de Hilbert. Turing se interesó en un resquicio que Gödel no había resuelto, el Entscheidungsproblem, el problema de la decidibilidad: ¿Existe un método para decidir si una dada afirmación matemática es demostrable? Turing resolvió este problema, trabajando en completa soledad a los 23 años de edad, y de paso en el camino inventó la ciencia de la computación.
COMPUTABLE NUMBERSSu contribución está en este trabajo, publicado en 1936 en los Proceedings de la London Mathematical Society. Tiene un título intimidante, con una palabra inventada, “computable”, y la famosa palabra de Hilbert tan difícil de pronunciar sin que alguien diga ¡salud!. Es notable que Turing ponga el énfasis del título en los números computables y no en la demostración del problema de Hilbert. A pesar de la relevancia académica de resolver un problema de Hilbert, parece que Turing se diera cuenta de que lo que había inventado estaba bueno, y que el problema de la decisión resultaba apenas una aplicación. Pero en realidad nadie (ni siquiera Turing) se dio remotamente cuenta de su profundo significado hasta mucho tiempo después. Todas las computadoras modernas, desde las laptops a los videojuegos, desde los teléfonos hasta los robots que aterrizan en Marte, son exactamente lo que Turing mostró en este paper.
En la segunda página del artículo, promediando el larguísimo resumen, nos encontramos con la conclusión de Turing (segundo recuadro en la imagen): el Entscheidungsproblem no tiene solución. En las siguientes 28 páginas Turing no vuelve a hablar del Entscheidungsproblem.
Alan le mostró el manuscrito a su profesor de Lógica. Newman había recibido justo en esos días un preprint de Alonzo Church, un matemático norteamericano de la prestigiosa escuela de Lógica de Princeton. Al mismo tiempo que Turing y de manera independiente Church había llegado a la misma conclusión sobre el problema de la decidibilidad. Así que parte de la originalidad del trabajo de Turing se desvaneció. El approach de Church era de todos modos muy diferente, eso quedó claro desde el principio. Y además estaba el valor teórico de lo que llegaría a ser el fundamento de la ciencia de la computación. Así que Newman apoyó la publicación del trabajo. Pero Alan tuvo que agregar a último momento ese párrafo que vemos asomar en la imagen, al final del largo resumen. Y agregó también un apéndice demostrando la equivalencia entre su “computabilidad” y la “calculabilidad efectiva” de Church.
Si uno sobrevive al título, es posible que la tipografía gótica de la notación termine de intimidarlo. Afortunadamente existe un libro, The Annotated Turing, de Charles Petzold, donde se explica todo párrafo por párrafo.
MÁQUINAS DE TURING
Como decíamos, la cuestión de la decidibilidad era la inspiración del trabajo, pero la mayor parte del mismo se trata de lo que Turing llama “números computables”, cuyo estudio ocupa el primer 60% del artículo, y que se pueden entender sin saber nada de Lógica ni del Programa de Hilbert.
Turing empieza a explicar lo que quiere decir por “calculable por una máquina”. La justificación viene de la asociación entre lo humano y la máquina, que se convertiría en un tema central a lo largo de toda su obra. Se plantea la cuestión de qué podría lograr una persona llevando a cabo una tarea metódica, repetitiva y mecánica. Y esto lo lleva a formular su análisis en términos de una “máquina” teórica, capaz de realizar operaciones elementales, predefinidas, sobre una secuencia de símbolos impresos en una cinta de papel. Argumenta que cualquier cosa que a uno se le pueda ocurrir que significa “metódico”, esta máquina lo podría hacer tan bien como una persona.
Turing muestra cómo estas máquinas, así de sencillas, no sólo pueden escribir sus "números computables", sino que también pueden llevar adelante cualquier cálculo matemático imaginable, tan sólo moviendo unos y ceros de atrás para adelante y de adelante para atrás. Más aún, cualquier tipo de información podía codificarse numéricamente y procesarse de la manera que uno quisiese. Como ven, son todos conceptos súper familiares para nosotros. No así en 1936. Fue el momento en que nació la Era Digital.
Un número computable, entonces, es un número que una de estas máquinas escribe en una cinta de papel. Claramente, los números enteros son computables. También los números racionales, las fracciones. Aun las que tienen un desarrollo decimal con infinitas cifras, como 1/3. ¿Y los números más raros? Pi, por ejemplo, es computable. Obvio, ya que sabemos cómo calcularlo con cuantos decimales queramos, con lápiz y papel. Lo mismo con la raíz cuadrada de 2, etc. Esto de los números computables es bastante loco. Parecen no tener una relación obvia con los números irracionales, o con los números trascendentes, o cualquiera de las otras categorías que conocemos. ¿Entonces? ¿Todos los números reales serán computables?
No. Turing demuestra que estas máquinas, que tienen un número finito de estados posibles, son enumerables, es decir son tantas como los números naturales. Y hay muchos más números reales que números naturales. Muchos, muchos más. Así que la mayor parte de los números son no computables. No importa cuánto nos esforcemos, nunca aparecerán como resultado de nuestros cálculos. ¿No es loquísimo? Cabe preguntarse qué tan reales son los números reales que no son computables. Así que hoy en día hay toda una rama del análisis de los números computables en lugar de los reales.
Bueno. Ya que las máquinas son numerables, Turing las numera. Es decir, muestra cómo se pueden codificar las tablas (que definen a las máquinas) de manera numérica. Es un lío, pero se puede hacer metódicamente. Uno termina con una máquina descripta, en lugar de por símbolos que representan las operaciones, por una “definición estándard” que es un número entero. Es claramente un approach inspirado en el Teorema de Gödel y su codificación numérica de las expresiones matemáticas. De yapa, tenemos una manera de generar máquinas de Turing: los números enteros. Muchas de ellas no funcionarán, muchas calcularán trivialidades, otras calcularán las mismas cosas de maneras diferentes, algunas más rápido, algunas más lento, algunas con pequeñas diferencias... Algunas ni siquiera se detendrán. ¡Es como la Biblioteca de Babel de Borges!
LA MÁQUINA UNIVERSAL
Pero ¿no hay aquí una contradicción? El método de Cantor es tan fácil de explicar que parece completamente mecanizable, ¿cómo puede ser que ese número sea no computable? ¿No debería haber una “máquina de Cantor” capaz de calcularlo? Esta máquina debería producir la tabla de la máquina T1, ejecutarla hasta el primer dígito, sumar 1 y escribir, después producir la segunda máquina, ejecutarla hasta el segundo dígito, sumar 1 y escribir, y así siguiendo. Es decir, debe ser una máquina capaz de emular lo que hacen las otras máquinas. Una máquina universal.
En algún sentido, la Máquina Universal de Turing es la única que necesitamos: no se necesita una máquina para cada tarea computable. La máquina universal ha llegado para acabar con todas las máquinas. La máquina universal es, decimos hoy, programable.
La máquina universal es tan importante para el argumento de Turing que éste la construye con todo detalle, dando explícitamente su tabla de estados y operaciones, a un nivel que es muy difícil de asimilar con facilidad. Si uno ha de creerle al Annotated Turing, además, la descripción no está libre de bugs. Pero, dejando de lado esto, Turing acababa de hacer algo extraordinario: había demostrado la generalidad de la computación, había mostrando cómo una máquina programable puede llevar a cabo la operación de cualquier máquina de computar. Es sin duda uno de los grandes logros intelectuales del siglo XX.
Ciertamente, Turing no “inventó” la computadora. Pero hasta ese momento la suposición habitual en la gente que trabajaba en el tema era que cada computadora debería ser diseñada para un propósito específico. Aún en la década del 50, más de 15 años después de Computable Numbers, los ingenieros que diseñaban las primeras computadoras digitales no habían acabado de visualizar a la computadora como una herramienta lógica, más que de cálculo. Así que no es de sorprender que el rol de Turing en la historia de la computación se cuente de manera desigual en distintos libros. Una cosa es contar la historia de la computadora desde un punto de vista de la ingeniería o del mercado. Y otro es el punto de vista que considera a las computadoras como materializaciones de conceptos matemáticos. En este último caso, el papel de Turing es destacadísimo.
¿Y el Entscheidungsproblem?
El método diagonal es la clave. La cosa se vuelve sumamente técnica y, depués de todo, no es más que "una aplicación" de las Máquinas. Turing muestra primero que puede construir una máquina que codifica todo el cálculo funcional de Hilbert. Muestra que el Entscheidungsproblem es equivalente a demostrar si la máquina que calcula el número construido con el método diagonal se detiene, y demuestra que este problema no tiene solución. Piece of cake.
PRINCETON
Como no podía ser de otra manera, Turing se fue a Princeton, donde se quedó dos años. Church dirigió su tesis, que completó en 1938. Princeton se había convertido en una meca para la física y la matemática, particularmente con la creación del Instituto de Estudios Avanzados. Gödel lo visitaba todos los años y John von Neumann, Courant, Hardy, Weyl, Einstein y tantos otros se habían establecido allí, muchos de ellos escapando del régimen nazi.
Sus ideas alcanzaron cierta notoriedad, atrayendo incluso la atención de von Neumann, a quien le había encantado Computable Numbers (otro día tal vez hablemos de él). Pero no saltó a la fama ni mucho menos. Su trabajo en Princeton, incluyendo la demostración de que sus conclusiones sobre la decidibilidad coincidían con las de Church, fue el material de su tesis. Esta línea de trabajo, tal vez la más profunda de su carrera, no prosiguió más allá de su doctorado.
Durante su segundo año en Princeton, mientras terminaba la tesis, la situación política en Europa se complicaba cada vez más. Estaba claro que Inglaterra y Alemania pronto entrarían en guerra. A pesar de que von Neumann le ofreció un tentador puesto en el Instituto de Estudios Avanzados, Turing se volvió a Inglaterra, donde no tenía trabajo. Apenas consiguió una beca de King’s College.
Pero rápidamente consiguió un trabajo mejor. Un trabajo secreto, que salvó miles de vidas, permitió la supervivencia de Inglaterra, y ayudó a los Aliados a ganar la guerra.
Continúa en la Parte 3 de El enigma de Turing...
11/08/2012
El enigma de Turing (parte 1)
Voy a publicar aquí buena parte del material que preparé para mi charla sobre Alan Turing. Inevitablemente algunas cosas quedan siempre fuera de las charlas, por tiempo o porque me olvido. Así que aquí está todo bien organizado. Es largo, así que serán varias notas, no consecutivas para no aburrir. Pero estoy seguro de que vale la pena.
ALAN TURING, FUNDADOR DE LA CIENCIA DE LA COMPUTACIÓN
Hoy en día se suele definir a Turing de esta manera super simplificadora, tratándose de uno de los pensadores más originales del siglo XX. Pero es estrictamente cierto: en un época sin computadoras, sin computadoras de NINGÚN tipo, Alan Turing plantó la semilla de la cual surgió todo lo que hoy en día está relacionado con las computadoras: el procesador, la memoria, el procesamiento digital, el software…
Alan nació en Londres, en 1912, hace 100 años. Sus padres trabajaban en el servicio imperial en la India, y durante la mayor parte de su infancia Alan y su hermano fueron criados en Inglaterra por una pareja de abuelos substitutos (una práctica habitual en la época). De niño sus entretenimientos favoritos eran los mapas, el ajedrez y la química (como para tantos de nosotros), y era un chico tímido y solitario (también, como tantos). La ciencia le fascinó desde chico, según su propio relato, pero fue una actividad extra-curricular durante su infancia.
Finalmente lo mandaron a una escuela secundaria, internada por supuesto, una de las top del sistema de public schools de Inglaterra (que no son públicas sino privadas, ojo). Allí, en 1928, conoció a otro chico con intereses similares, Christopher Morcom, y se hicieron grandes amigos, aunque pertenecían a houses distintas. Compartían el gusto de la astronomía y de la física y la matemática en general. Chris era brillante y Alan lo admiraba, con una mezcla de admiración y enamoramiento adolescente. Su relación con Chris parece haber dejado una marca de por vida.
En 1929 quedaron fascinados con un libro publicado por el famoso astrónomo Arthur Eddington, La Naturaleza del Mundo Físico, una exposición de las nuevas ciencias de la mecánica cuántica y la relatividad que causó gran impacto en su momento. Chris y Alan terminaron la escuela y decidieron irse a estudiar física y matemática a Cambridge. Christopher ganó la beca y Alan no. Pero Christopher murió inesperadamente en 1930, a partir de complicaciones de una tuberculosis, un hecho que marcó profundamente la vida de Alan. El convencimiento de que tenía que lograr lo que su amigo ya no podría le dio el empujón necesario para avanzar definitivamente en el ambiente académico, donde venía fracasando. En 1931 ingresó finalmente en Cambridge, con una beca del King’s College. Por primera vez empezó a sentirse “en casa” y empezó a disfrutar de la vida universitaria. Se acercó a los movimientos pacifistas, se aficionó a remar, a correr y a navegar, y terminó sus estudios de manera distinguida, con varios premios y becas. Parecía encaminado a convertirse en un profesor de matemática pura de Cambridge, ligeramente excéntrico, nada fuera de lo habitual por otro lado. Su mente singular, de todos modos, lo llevaría por rumbos inesperados.
LA MECANIZACIÓN DEL PENSAMIENTO MATEMÁTICO
A comienzos de los años ‘30, Turing había pasado de las cuestiones matemáticas de la fundamentación de la mecánica cuántica a las cuestiones lógicas de la fundamentación de la matemática. Empezó a interesarse en la Lógica a partir de la influyente obra de Russell y Whitehead, y obras filosóficas de Russell, en las que se trataba el problema de cómo capturar “la verdad” dentro de un sistema formal.
Este interés encontraba su nicho en el llamado “programa de Hilbert”. El famoso matemático alemán David Hilbert había planteado el problema en términos de encontrar un sistema en el cual todas las verdades matemáticas surgieran mediante reglas bien definidas, a partir de un conjunto de axiomas, como automóviles en una línea de montaje: un concepto que a principios del siglo XX había ya revolucionado la industria, ¿estaría llamado a revolucionar la matemática?
Esta idea de una máquina pasando de un estado a otro obedeciendo un conjunto de reglas se convirtió en un núcleo que dominaría el pensamiento de Turing durante toda su carrera. Entreveía que era un concepto muy poderoso, e imaginaba máquinas que jugaban al ajedrez, otras que producían teoremas, otras que escribían poesía, etc.
El Programa de Hilbert estaba basado en tres conceptos que tenían que ser satisfechos por el sistema formal: consistencia, completitud y decidibilidad. En 1930 (año en que Hilbert se jubiló) Kurt Gödel demostró que el Programa era en gran medida imposible: en todo sistema formal, con axiomas y reglas, y que no sea inconsistente (que no contenga contradicciones) había proposiciones indecidibles, esto es proposiciones que son ciertas pero que no se pueden demostrar. Estas proposiciones están basadas en paradojas de la lógica conocidas desde la Antigüedad, como la famosa de Epiménides de Creta: “Todos los cretenses son mentirosos”.
Fue un duro golpe. Muchos matemáticos abandonaron directamente el campo de la Lógica. El propio Russell se dedicó a sus otros intereses, y terminó ganando el Premio Nobel de Literatura en 1950. John von Neumann, que había demostrado el segundo teorema de Gödel antes que Gödel, también abandonó la Lógica y se dedicó a la física (y también terminó siendo instrumental en el desarrollo de las computadoras). Muchos de estos matemáticos alemanes, claro, no sólo abandonaron la Lógica sino que se vieron forzados a abandonar su país. Con el tiempo la situación se normalizó, y hoy en día la Lógica goza de buena salud.
Quedaba un resquicio, sin embargo, en lo que Hilbert había llamado el Entscheidungsproblem, una cuestión de decidibilidad: ¿Puede existir un método por el cual uno pueda decidir si una dada afirmación matemática es demostrable? El teorema de Gödel no decía nada sobre esto. Decía que no podía determinarse la verdad de una proposición por un método de este tipo. Pero nada decía sobre su demostrabilidad. Si esto se pudiera hacer, habría una esperanza: uno podría detectar las antipáticas proposiciones indecidibles y quedarse con la buenas, como cuando uno recorta la grasita del matambre.
Para responder esta pregunta (existe un método para decidir…) se necesita definir lo que queremos decir por “método”. Parece algo demasiado general y filosófico, y fue el principal escollo con que se encontró Göedel después de haber despachado las dos primeras preguntas del programa de Hilbert. Se necesita una definición precisa y convincente. Y esto fue lo que Turing hizo. Para su sorpresa, descubrió que tampoco esto se podía hacer. La matemática no era como un matambre. Era más bien como un vacío, con grasita entremezclada que no se podía recortar. Lo cual es un resultado sumamente valioso en el campo de la Lógica, claro está. Pero lo que inventó en el camino no sólo fue importante, sino que transformó nuestra civilización.
En el camino, Turing inventó la ciencia de la computación.
Continúa en la Parte 2 de El enigma de Turing...
By the way... Hilbert era un optimista. Él creía que su Programa tendría éxito. Sostenía que el desengaño de Compte, quien buscando algo que estaría por siempre fuera del conocimiento humano había puesto como ejemplo la composición química de las estrellas (desentrañada por la espectroscopía de Kirchoff y Bunsen poco después) se debía a que simplemente no existía algo que no pudiéramos conocer:
ALAN TURING, FUNDADOR DE LA CIENCIA DE LA COMPUTACIÓN
Hoy en día se suele definir a Turing de esta manera super simplificadora, tratándose de uno de los pensadores más originales del siglo XX. Pero es estrictamente cierto: en un época sin computadoras, sin computadoras de NINGÚN tipo, Alan Turing plantó la semilla de la cual surgió todo lo que hoy en día está relacionado con las computadoras: el procesador, la memoria, el procesamiento digital, el software…
Finalmente lo mandaron a una escuela secundaria, internada por supuesto, una de las top del sistema de public schools de Inglaterra (que no son públicas sino privadas, ojo). Allí, en 1928, conoció a otro chico con intereses similares, Christopher Morcom, y se hicieron grandes amigos, aunque pertenecían a houses distintas. Compartían el gusto de la astronomía y de la física y la matemática en general. Chris era brillante y Alan lo admiraba, con una mezcla de admiración y enamoramiento adolescente. Su relación con Chris parece haber dejado una marca de por vida.
LA MECANIZACIÓN DEL PENSAMIENTO MATEMÁTICO
A comienzos de los años ‘30, Turing había pasado de las cuestiones matemáticas de la fundamentación de la mecánica cuántica a las cuestiones lógicas de la fundamentación de la matemática. Empezó a interesarse en la Lógica a partir de la influyente obra de Russell y Whitehead, y obras filosóficas de Russell, en las que se trataba el problema de cómo capturar “la verdad” dentro de un sistema formal.
Esta idea de una máquina pasando de un estado a otro obedeciendo un conjunto de reglas se convirtió en un núcleo que dominaría el pensamiento de Turing durante toda su carrera. Entreveía que era un concepto muy poderoso, e imaginaba máquinas que jugaban al ajedrez, otras que producían teoremas, otras que escribían poesía, etc.
El Programa de Hilbert estaba basado en tres conceptos que tenían que ser satisfechos por el sistema formal: consistencia, completitud y decidibilidad. En 1930 (año en que Hilbert se jubiló) Kurt Gödel demostró que el Programa era en gran medida imposible: en todo sistema formal, con axiomas y reglas, y que no sea inconsistente (que no contenga contradicciones) había proposiciones indecidibles, esto es proposiciones que son ciertas pero que no se pueden demostrar. Estas proposiciones están basadas en paradojas de la lógica conocidas desde la Antigüedad, como la famosa de Epiménides de Creta: “Todos los cretenses son mentirosos”.
Fue un duro golpe. Muchos matemáticos abandonaron directamente el campo de la Lógica. El propio Russell se dedicó a sus otros intereses, y terminó ganando el Premio Nobel de Literatura en 1950. John von Neumann, que había demostrado el segundo teorema de Gödel antes que Gödel, también abandonó la Lógica y se dedicó a la física (y también terminó siendo instrumental en el desarrollo de las computadoras). Muchos de estos matemáticos alemanes, claro, no sólo abandonaron la Lógica sino que se vieron forzados a abandonar su país. Con el tiempo la situación se normalizó, y hoy en día la Lógica goza de buena salud.
Para responder esta pregunta (existe un método para decidir…) se necesita definir lo que queremos decir por “método”. Parece algo demasiado general y filosófico, y fue el principal escollo con que se encontró Göedel después de haber despachado las dos primeras preguntas del programa de Hilbert. Se necesita una definición precisa y convincente. Y esto fue lo que Turing hizo. Para su sorpresa, descubrió que tampoco esto se podía hacer. La matemática no era como un matambre. Era más bien como un vacío, con grasita entremezclada que no se podía recortar. Lo cual es un resultado sumamente valioso en el campo de la Lógica, claro está. Pero lo que inventó en el camino no sólo fue importante, sino que transformó nuestra civilización.
En el camino, Turing inventó la ciencia de la computación.
Continúa en la Parte 2 de El enigma de Turing...
By the way... Hilbert era un optimista. Él creía que su Programa tendría éxito. Sostenía que el desengaño de Compte, quien buscando algo que estaría por siempre fuera del conocimiento humano había puesto como ejemplo la composición química de las estrellas (desentrañada por la espectroscopía de Kirchoff y Bunsen poco después) se debía a que simplemente no existía algo que no pudiéramos conocer:
“La verdadera razón por la cual Compte fue incapaz de hallar un problema insoluble es, en mi opinión, que no hay problemas absolutamente insolubles. En lugar de un tonto ignorabimus, nuestra respuesta es, por el contrario: Debemos saber. Vamos a saber. Wir muss en wissen. Wir werden wissen.”Dicen que la reacción de Hilbert cuando le contaron lo que había demostrado Gödel (recién se había jubilado, a los 68 años) fue de “enojo”.
09/08/2012
El enigma de Turing
Si estás en Bariloche, venite el viernes 10 al Coloquio del Instituto Balseiro, a las 14:30 en el Salón de Actos. Los Coloquios son seminarios de variado interés, a veces más técnicos, a veces menos, destinados al público en general. Este viernes tengo el gusto de ser el expositor, y voy a hablar sobre la vida y la obra de Alan Turing. Si puedo, si puedo, voy a hacer además una serie de posts sobre Turing acá en el blog.
El enigma de Turing
Guillermo Abramson
Viernes 10 de agosto, 14:30, Salón de Actos del Instituto Balseiro
El pasado mes de junio se cumplieron 100 años del nacimiento de Alan Turing,
y se han organizado numerosos eventos a nivel mundial para celebrar la
vida, breve y trágica pero llena de logros, de este matemático inglés.
Pionero de las computadoras y de la inteligencia artificial, criptógrafo, matemático genial en variadas áreas que van desde la lógica hasta la biología matemática, Turing dejó un profundo legado en la ciencia del siglo XX. Los matemáticos recordarán al hombre que resolvió uno de los difíciles problemas de Hilbert. Los criptógrafos e historiadores a quien quebró el código de los mensajes cifrados de la Armada Nazi, permitiendo a Gran Bretaña sobrevivir la batalla del Atlántico. Ingenieros y computadores reconocerán al fundador de la era digital, las computadoras programables y la inteligencia artificial. Los teóricos de la biología saludarán al pionero del estudio matemático de la morfogénesis y los físicos al de la dinámica no lineal. En estos días los Juegos Olímpicos se están disputando en Londres y vale la pena recordar que en 1948 también, y que Alan pudo haber corrido el maratón de no ser por una lesión (su mejor tiempo estaba apenas 11 minutos por detrás del oro de ese año, el argentino Delfo Cabrera).
Cuando su carrera se encontraba en plenitud, y habiendo realizado extraordinarios servicios a su patria, fue procesado y condenado por un crimen que hoy resulta difícil de creer: Alan Turing era homosexual. Poco después puso fin a su vida, a los 41 años de edad.
En este seminario repasaremos la vida y los trabajos de este hombre extraordinario, que se merecía algo mejor.
El enigma de Turing
Guillermo Abramson
Viernes 10 de agosto, 14:30, Salón de Actos del Instituto Balseiro
Pionero de las computadoras y de la inteligencia artificial, criptógrafo, matemático genial en variadas áreas que van desde la lógica hasta la biología matemática, Turing dejó un profundo legado en la ciencia del siglo XX. Los matemáticos recordarán al hombre que resolvió uno de los difíciles problemas de Hilbert. Los criptógrafos e historiadores a quien quebró el código de los mensajes cifrados de la Armada Nazi, permitiendo a Gran Bretaña sobrevivir la batalla del Atlántico. Ingenieros y computadores reconocerán al fundador de la era digital, las computadoras programables y la inteligencia artificial. Los teóricos de la biología saludarán al pionero del estudio matemático de la morfogénesis y los físicos al de la dinámica no lineal. En estos días los Juegos Olímpicos se están disputando en Londres y vale la pena recordar que en 1948 también, y que Alan pudo haber corrido el maratón de no ser por una lesión (su mejor tiempo estaba apenas 11 minutos por detrás del oro de ese año, el argentino Delfo Cabrera).
Cuando su carrera se encontraba en plenitud, y habiendo realizado extraordinarios servicios a su patria, fue procesado y condenado por un crimen que hoy resulta difícil de creer: Alan Turing era homosexual. Poco después puso fin a su vida, a los 41 años de edad.
En este seminario repasaremos la vida y los trabajos de este hombre extraordinario, que se merecía algo mejor.
Suscribirse a:
Entradas (Atom)