Alan M. Turing

Recopilado por Yanin Castelazo Luna

Alan Mathison Turing (23 de junio de 1912 - 7 de junio de 1954).

Fue matemático, científico de la computación, criptógrafo y filósofo. Se le considera uno de los padres de la Ingeniería informática siendo el precursor de la Ciencia de la computación moderna. Proporcionó una influyente formalización de los conceptos de algoritmo y computación: la máquina de Turing. Formuló su propia versión de la hoy ampliamente aceptada Tesis de Church-Turing, la cual postula que cualquier modelo computacional existente tiene las mismas capacidades algorítmicas, o un subconjunto, de las que tiene una máquina de Turing. Durante la Segunda Guerra Mundial, trabajó en romper los códigos nazis, particularmente los de la máquina Enigma; durante un tiempo fue el director de la sección Naval Enigma del Bletchley Park. Tras la guerra diseñó uno de los primeros computadores electrónicos programables digitales en el Laboratorio Nacional de Física del Reino Unido y poco tiempo después construyó otra de las primeras máquinas en la Universidad de Manchester. Entre otras muchas cosas, también contribuyó de forma particular e incluso provocativa a la cuestión de si las máquinas pueden pensar.

Inicio de su vida

Alan Mathison Turing nació en Paddington, Inglaterra, el 23 de junio de 1912. Se cuenta que aprendió a leer por sí solo en tres semanas y que desde el principió mostró un gran interés por los números y los rompecabezas.
A los ocho años había desarrollado un interés explícito por las ciencias, y había establecido un pequeño laboratorio en el sótano de su casa. Progresivamente su interés científico fue derivando hacia el mundo abstracto de las matemáticas, incluyendo una gran capacidad para realizar cálculos mentales.
En 1926, con catorce años, ingresó en el internado de Sherborne en Dorset, en la que ya demostraba su facilidad para las matemáticas, teniendo una gran capacidad para realizar cálculos mentalmente y llegando a resolver problemas muy avanzados (para su edad) en 1927 sin ni siquiera haber estudiado cálculo elemental.
En 1928, con dieciséis años, Turing descubrió los trabajos de Albert Einstein y no sólo pudo comprenderlos sino que además infirió las críticas de Einstein a las Leyes de Newton de la lectura de un texto en el que no estaban explícitas. Durante su edad escolar Turing fue un joven cuyo optimismo y ambiciones se vieron acrecentados debido en gran parte a su intensa unión con su amigo Christopher Morcom, cuya muerte, aun joven, afectaría a Turing profundamente.

La Universidad y la computabilidad

Este artículo da respuesta (negativa) al problema de la decisión formulada por Hilbert en 1900, probando que existen problemas sin solución algorítmica y es uno de los cimientos más importantes de la teoría de la computación. Probó que no había ninguna solución para el Entscheidungsproblem, demostrando primero que el problema de la parada para las máquinas de Turing es irresoluble: no es posible decidir algorítmicamente si una máquina de Turing dada llegará a pararse o no.

También fue pionero con su concepto de "Máquina Universal (de Turing)", con la tesis de que dicha máquina podría realizar las mismas tareas que cualquier otro tipo de máquina. Su estudio también introduce el concepto de números definibles. Demostró que para cualquier sistema de sus máquinas que sea necesario para efectuar algoritmos cada vez más complicados existe una máquina de Turing capaz de hacerlo todo ella sola, y su existencia teórica pone de manifiesto que el concepto de máquina de Turing es de una versatilidad sin fin, al permitir que cualquier incremento de la complejidad del algoritmo pueda ser aceptado por una lista más larga de especificaciones… Los ordenadores actuales son realizaciones de las ideas de John von Newmann y de Alan Turing.

Expresó el análisis en términos de una máquina teórica que sería capaz de transformar con precisión operaciones elementales previamente definidas en símbolos en una cinta de papel. Con este análisis básico, Turing definió lo que hoy en día conocemos como un método definido o algoritmo.
En 1938 obtuvo el Doctorado en Princeton; en su discurso introdujo el concepto de hipercomputación, en el que ampliaba las máquinas de Turing con las llamadas máquinas oráculo, las cuales permitían el estudio de los problemas para los que no existe una solución algorítmica.

Criptografía en la guerra

En el año 1938 conoció a un joven ingeniero polaco llamado Robert Lewinsky, que había trabajo con los alemanes en el diseño de un sistema electromecánico de encriptación de comunicaciones. Lewinsky -que era judío- fue depurado por los nazis y entró en contacto con el servicio secreto británico, quien encomendó a Alan Turing la formación de un grupo de científicos e ingenieros dedicados a estudiar y descifrar este sistema de comunicaciones denominado Enigma.

Durante la Segunda Guerra Mundial fue uno de los principales artífices de los trabajos del Bletchley Park para descifrar los códigos nazis. Sus observaciones matemáticas contribuyeron a romper los códigos de la máquina Enigma y de los codificadores de teletipos FISH (máquinas de teletipos codificados que fabricaron conjuntamente Lorenz Electric y Siemens&Halske). Sus estudios del sistema Fish ayudarían al desarrollo posterior de la primera computadora programable electrónica digital llamada Colossus, la cual fue diseñada por Max Newman y su equipo, y construida en la Estación de Investigaciones Postales de Dollis Hill por un equipo dirigido por Thomas Flowers en 1943. Dicha computadora se utilizó para descifrar los códigos Fish (en concreto las transmisiones de la máquina Lorenz). Especializado en el descifrado de mensajes, de gran éxito, y de alguna manera fue precursor del ENIAC construido en la universidad de Pennsylvania dos años más tarde.

Réplica de una máquina bombe

Para romper los códigos de la máquina Enigma, Turing diseñó la bombe, una máquina electromecánica - llamada así en reconocimiento de la diseñada por los polacos bomba kryptologiczna - que se utilizaba para eliminar una gran cantidad de llaves enigma candidatas. Para cada combinación posible se implementaba eléctricamente una cadena de deducciones lógicas. Era posible detectar cuándo ocurría una contradicción y desechar la combinación. La bombe de Turing, con una mejora añadida que sugirió el matemático Gordon Welchman, era la herramienta principal que usaban los criptógrafos aliados para leer las transmisiones Enigma.

La prueba de Turing

De 1945 a 1948 trabajó en el Laboratorio Nacional de Física en el diseño del ACE (Máquina de Computación Automática). En 1949 fue nombrado director delegado del laboratorio de computación de la Universidad de Manchester y trabajó en el software de una de las primeras computadoras reales. Hacia 1947, Turing concibió la idea de las redes de cómputo y el concepto de subrutina y biblioteca de software. También describió las ideas básicas de lo que hoy se conoce como red neuronal. Abandonó la NLP en 1948. Turing se adelantó al proyecto de construcción de un ordenador de acuerdo con la arquitectura de von Neumann. El Manchester Mark I, estuvo acabado en 1948 antes que el EDVAC. Turing diseñó para esta máquina un lenguaje de programación basado en el código empleado por los teletipos. Otro de los campos de investigación de Turing fue la inteligencia artificial, se puede decir que esta disciplina nació a partir del artículo titulado "Computing Machinery and Inteligence" publicado por Turing en 1950. Es muy famosa la primera frase de este artículo: " Propongo considerar la siguiente cuestión: ¿Pueden pensar las máquinas?".

Turing propuso un método llamado el test de Turing con la intención de definir una prueba estándar por el que una máquina podría catalogarse como "sensible" o "sentiente". Se basa en la idea siguiente: si una persona se comunica sólo a través de un terminal con otras dos partes, que están escondidas, y no se puede discriminar a través de preguntas cuál de ambas partes es una persona y cuál es un ordenador, entonces no se puede negar que la máquina muestra la cualidad que, en las personas, se llama 'inteligencia'. Tal procedimiento tiene la ventaja de no tener que definir lo que es la inteligencia. Turing creía firmemente que máquinas que piensen llegarían a existir y predijo que hacia el año 2000 una máquina jugaría al 'juego de imitación', como él llamó al test, de manera que un interrogador medio no tendría más del 70 por 100 de posibilidades de efectuar la identificación correcta tras cinco minutos de preguntas."

En 1952 Turing escribió un programa de ajedrez. A falta de una computadora lo suficientemente potente como para ejecutarlo, él simulaba el funcionamiento de la computadora, tardando más de hora y media en efectuar un movimiento. Una de las partidas llegó a registrarse; el programa perdió frente a un colega de Turing.

Trabajó junto a Norbert Weiner en el desarrollo de la cibernética. Esta rama de estudios se genera a partir de la demanda de sistemas de control que exige el progresivo desarrollo de las técnicas de producción a partir del siglo XX. La cibernética pretende establecer un sistema de comunicación entre el hombre y la máquina como premisa fundamental para administrar los sistemas de control. Sus estudios profundizaron en esta relación estableciendo el concepto de interfaz y cuestionando los límites de simulación del razonamiento humano.

En 1951, es nombrado miembro de la Sociedad Real de Londres por sus contribuciones científicas. Y en su honor, la Association for Computing Machinery llama Turing Award a su premio más importante, el cual se otorga desde 1966 a los expertos que han realizado las mayores contribuciones al avance de la computación.

Renovó asimismo su interés en las carreras, llegando incluso a preparar su participación en los juegos olímpicos, aunque una lesión de cadera le impidió hacer los progresos que necesitaba.

Turing trabajó desde 1952 hasta que falleció en 1954 en la biología matemática, concretamente en la morfogénesis. Publicó un trabajo sobre esta materia titulado "Fundamentos Químicos de la Morfogénesis" en 1952. Su principal interés era comprender la filotaxis de Fibonacci, es decir, la existencia de los números de Fibonacci en las estructuras vegetales. Utilizó ecuaciones de reacción-difusión que actualmente son cruciales en el campo de la formación de patrones. Sus trabajos posteriores no se publicaron hasta 1992 en el libro "Obras Completas de A. M. Turing".

Su condena y muerte

Hacia los años 50 la carrera profesional de Turing se vio truncada cuando lo procesaron por su homosexualidad.
A pesar de todo, en sus últimos años Turing publicó otro artículo científico de gran impacto, titulado "Computing Machinery and Intelligence", que sentó las bases de una nueva rama de las ciencias de la computación, la inteligencia artificial, y planteó cuestiones muy curiosas en aquélla época, como el "test de Turing".

Sin embargo la vida personal de Turing se fue deteriorando a medida que los escándalos de sus relaciones homosexuales iban saliendo a la luz pública.

Como consecuencia de un affaire escandaloso con un joven que se encontraba sin empleo, fue juzgado y condenado, aunque en lugar de ser recluido en prisión, fue sometido a tratamiento de hormonas femeninas -estrógenos- con el fin de atenuar su impulso sexual. Este tratamiento le produjo importantes alteraciones físicas y le convirtió en impotente.

Dos años después del juicio, en 1954, Turing se suicidó comiendo una manzana envenenada con cianuro. A pesar de que su madre intentó negar la causa de su muerte, atribuyéndola a razones naturales, su vida terminó amargamente y envuelta en una nube de misterio.

Para mas detalles

Prueba de Turing

Se llama Prueba o Test de Turing al procedimiento desarrollado por Alan Turing para identificar la existencia de inteligencia en una máquina.

Expuesto en 1950 en un artículo (Computing Machinery and Inteligence) para la revista Mind, sigue siendo hoy día una de las cabezas de lanza de los defensores de la Inteligencia Artificial.
Está fundamentado en la hipótesis positivista de que, si una máquina se comporta en todos los aspectos como inteligente, entonces debe ser inteligente.

La prueba consiste en un desafío. La máquina ha de hacerse pasar por humana en una conversación con un hombre a través de una comunicación de texto estilo chat. Al sujeto no se le avisa si está hablando con una máquina o una persona. Si el sujeto es incapaz de determinar si la otra parte de la comunicación es humana o máquina, entonces se considera que la máquina ha alcanzado un determinado nivel de madurez: es inteligente. Todavía ninguna maquina puede pasar este examen en una experiencia con método científico.

Existe una versión modificada, propuesta por John Searle y popularizada por Roger Penrose: la sala china. En esencia es igual, pero la ejecución del algoritmo la realizan personas encerradas en una habitación, se requiere que las personas de la habitación no conozcan el idioma en que se realiza la conversación.

Pese a la brillantez de Penrose, esta modificación no aporta nada al problema, puesto que si los operadores consiguen comprender la conversación, lo harían gracias a su propia inteligencia, por otra parte, pese a lo aparentemente absurdo de la proposición, la sala podría pasar la prueba de turing sin que los operadores hubieran comprendido nada de la conversación.

Una de las aplicaciones de la prueba de Turing es el control de spam. Dado el gran volumen de correos electrónicos enviados, el spam es, por lo general, enviado automáticamente por una máquina. Así la prueba de Turing puede usarse para distinguir si el correo electrónico fue enviado por un remitente humano o por una máquina (por ejemplo por la prueba Captcha).

Máquina de Turing

La máquina de Turing es un modelo computacional creado por Alan Turing con el cual él afirmaba que se podía realizar cualquier cómputo.

La máquina de Turing, como modelo matemático, consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

• avanzar el cabezal lector/escritor para la derecha;
• avanzar el cabezal lector/escritor para la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado,valor) (\nuevo estado, \nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el caracter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.

De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crear una máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX.

Máquina de Turing probabilística

En Teoría de la complejidad computacional, se utilizan Máquinas de Turing probabilísticas para definir diferentes clases de complejidad.

Una Máquina de Turing probabilística es una Máquina de Turing no determinista que selecciona aleatoriamente entre las transiciones disponibles en cada punto con idéntica probabilidad para cada alternativa.

Alternativamente, se pude definir también como una máquina de Turing determinista con una instrucción adicional "escribir" donde el valor de la escritura está uniformemente distribuido en el alfabeto de la máquina.

Como consecuencia, una máquina de Turing probabilística puede (a diferencia de una máquina de Turing) tener un resultado estocástico: Dada una entrada y un programa para la máquina, puede ejecutar el programa en tiempos variables de ejecución o puede no parar; más aún, puede aceptar una entrada en una ejecución y no aceptarla en la siguiente.

Se desprende que la aceptación de una cadena de entrada en una máquina de Turing probabilística puede ser definida de varias formas. Y a esas formas de terminar corresponden diferentes clases de complejidad que incluyen RP, Co-RP. BPP y ZPP. Al restringirse la máquina a sólo usar espacio logarítmico en lugar de tiempo polinómico, se definen las clases análogas RL, Co-RL, BPL, y ZPL. Al incluir ambas restricciones se obtienen las clases RLP, Co-RPL, BPLP y ZPLP.
Los computadores cuánticos son otro modelo de cálculo que es inherentemente probabilístico.

Referencias:

http://es.wikipedia.org/wiki/Alan_Turing
http://es.wikipedia.org/wiki/Prueba_de_Turing
http://es.wikipedia.org/wiki/ %C3%A1quina_de_Turing
http://es.wikipedia.org/wiki/ Historia_de_la_Inteligencia_Artificial
http://es.wikipedia.org/wiki/ M%C3%A1quina_de_Turing_probabil%C3%ADstica
http://caminantes.metropoliglobal.com/web/biografias/turing.htm
http://www.imagia.com.mx/hmm/va/Turing.htm
http://www-etsi2.ugr.es/alumnos/mlii/Alan%20Turing.htm
http://www.cefi-unlp.com.ar/ cefi/contenidos.php?ObjID=32&Action=Show
http://www.infoamerica.org/teoria/turing1.htm
http://www.portalplanetasedna.com.ar/maquina_enigma.htm
http://www.rastersoft.com/articulo/turing.html

Recomendaciones de los compañeros

http://www.turing.org.uk/turing
Premios Turing