ALAN TURING

UN VISIONARIO DE LA INFORMÁTICA Y LA INTELIGENCIA ARTIFICIAL

Universidad Popular “Carmen de Michelena”

2012 Año Turing

¿Por qué es importante Turing? (1)

● Ayudó a ganar la Segunda Guerra Mundial, mediante decodificación mensajes alemanes.

● Imaginó una máquina teórica de computación cuando todavía no existían los ordenadores.

● Usó esa máquina para demostrar importante teorema fundamentos de las matemáticas.

● Imaginaba que algún día las máquinas podrían llegar a pensar como los humanos, al menos bajo el punto de vista de comportamiento observable.

¿Por qué es importante Turing? (2)

● Participó en construcción algunos primeros ordenadores.

● Fue un precursor de la inteligencia artificial:

– Ejemplo: programa de ajedrez cuando no había ordenadores.

● Hizo algunos de los primeros trabajos de biología matemática, que 60 años después se han considerado acertados.

● Como curiosidad, veremos que también fue un atleta de élite.

● “Solo podemos ver poco del futuro, pero lo suficiente para darnos cuenta de que hay mucho que hacer” (Alan Turing – “Maquinaria de computación e inteligencia”).

Premio Turing

● Es por decirlo así, el premio Nobel de los informáticos.

● Lo concede la ACM, Association for Computing Machinery (“Asociación para la Maquinaria Computacional”).

● Sirve para premiar los mejores avances en lenguajes de programación, inteligencia artificial, análisis de algoritmos, bases y estructuras de datos, complejidad computacional, diseño de ordenadores, construcción de sistemas operativos y compiladores, análisis numérico, etc.

Turing

Infancia de Turing (1)

● Nace el 23-6-1912 en Paddington, Londres.

● Alan Mathison Turing.

● Segundo hijo de Julius Mathison Turing y Ethel Sara Stoney.

● Sara educada en la Sorbonne, Julius empleado del Indian Civil Service, residían en Chatrapur, India.

● Viajaron a Londres para que naciera Alan.

● Julius vuelve a la India, tras nacimiento. Sara un año después.

● Alan y su hermano se quedan al cuidado matrimonio confianza.

● Los padres viajaban de vez en cuando a ver a sus hijos.

El niño Alan

Infancia de Turing (2)

• Aficionado desde muy pequeño a números, letras y rompecabezas.

• 7 años: ideó cómo localizar un panal de miel.

• 6 años: Colegio público St. Michael's.

• 9 años: Hazelhurst Preparatory School (interno).

• Lee: “Natural Wonders Every Child Should Know”

• Marlborough School: acoso escolar.

Juventud de Turing (1)● 1926-1931 Escuela privada Sherborne School.

– Por huelga general recorrió 100 Km. desde Southampton (procedente de Francia) en bici el primer día de clase con parada en un hotel.

– El director decía: “Si permanece en la escuela privada, debe tener la intención de ser

educado. Ahora bien, si solo pretende ser un científicoespecialista, entonces está

perdiendo el tiempo aquí”; “el alquimista”; “decididamente antisocial”.

– Lee: “The Nature of the Physical Word” (A. Eddigton).

– 16 años (1929): entiende teoría de la Relatividad.

El joven Alan

Juventud de Turing (2)

● Sherborne (continuación)

– Aquí Turing avanza mucho en Matemáticas, pese a que su profesor decía que “era alguien a quien resultaba difícil enseñar, puesto que prefería sus propios métodos independientes”.

– 1929: Lee a Schrödinger (mecánica cuántica).

– 1929: Conoce a Christopher Morcom, que fallece 2 años más tarde por tuberculosis.

– La muerte de Morcom le afecta profundamente. Se aparta de la religión, pero se preocupa sobre como la mente humana puede alojarse en la materia, es decir, el cuerpo. Pensaba que quizá la mente pudiera sobrevivir al cuerpo y que a lo mejor la mecánica cuántica podía tener algo que ver.

1931: Turing en King's College (Universidad de Cambridge) (1)

● Lee:

– Trabajo John von Neumann sobre fundamentos matemáticos mecánica cuántica.

– “Introduction to mathematical philosophy” (Bertrand Rusell)

– “Principia mathematica” (Rusell y Alfred North Whitehead).

– Trabajo de Kurt Gödel sobre los teoremas de incompletitud, que le inspiró la idea de la máquina de Turing.

Turing en King's College (Universidad de Cambridge) (2)

● Remaba, corría, jugaba al bridge y al tenis, iba al teatro, ópera y aprendió a tocar el violín.

● Tuvo su primera relación amorosa con un estudiante de matemáticas, Andrew Hodge (1932).

● Viajó por Europa y se unió al movimiento antibélico.● Extraordinarios exámenes finales (1934).

● 1935: Asiste a un curso de Max Newman sobre fundamentos de las matemáticas.

Turing en King's College (Universidad de Cambridge) (3)

1936:

– Gana el premio Smith por un trabajo en teoría de la probabilidad.

– Publica “On Computable Numbers with an Application to the Entscheidungsproblem” (“Sobre números computables con una aplicación al problema de la decisión”) en donde aparece el concepto de Máquina-A (de Turing).

– La publicación fue posible por la intercesión de Newman, ya que Alonzo Church acababa de demostrar lo mismo. (Mediante cálculo lambda).

Turing en King's College (Universidad de Cambridge) (4)– Posteriormente Gödel dijo que el trabajo de Church era

insatisfactorio, pero apreció el de Turing.

Otra foto de Alan

Turing se va a las Américas (Universidad de Princeton) (1)

● Encontró un grupo selecto de matemáticos, incluyendo Church.

● Bien recibido por Church, pero su entorno social no gustaba a Turing.

● Escribe su tesis doctoral en dos años:

– “Systems of Logic Based on Ordinals”, en la que describe las que él llama Máquinas Oraculares.

– De alguna forma trata del papel de la intuición en las matemáticas.

Turing se va a las Américas (Universidad de Princeton) (2)

● Comienza a pensar en usar circuitos electrónicos o componentes electromecánicos.

● Construye una máquina multiplicadora con relés electromagnéticos.

● 1938: John von Neuman le ofrece un trabajo, pero vuelve al King's College.

Turing regresa a Inglaterra

● Verano 1938: regreso.

● 1939:

– Alan dicta conferencias lógica matemética en King's.

– Asiste a conferencias fundamentos matemáticas de Wittgestein:

● “No sirve de nada que yo les intenté convencer de algo con lo que Turing no estaría de acuerdo”.

● Turing: “Ya veo lo que quiere decir”. Wittgestein : “Yo no quiero decir nada”.

Turing se alista voluntario (1)

● ¿Entiende usted que al enrolarse en los voluntarios de la defensa local de su Majestad se halla sujeto a la jurisdicción militar? (En la hoja de reclutamiento).

● Turing pensó: “No puedo imaginar ningún cúmulo de circunstancias en las cuales pudiera ser de mi provecho responder afirmativamente a esta pregunta”.

● Consejo de guerra por no asistir a desfiles:

– ¿Es cierto, soldado raso Turing, que no ha asistido a ninguno de los 8 últimos desfiles?.

– Si, señor.

Turing se alista voluntario (2)

– ¿Se da cuenta de que eso es una infracción muy grave?

– No, señor.

– Soldado raso Turing: ¿está intentando tomarme el pelo?

– No, señor, pero si mira mi solicitud de admisión a la guardia nacional, verá que yo no entiendo estar sujeto a la jurisdicción militar.

– (Llevaron la hoja con la solicitud y la leyó el coronel).

– Se alistó usted de manera inadecuada. ¡Salga de mi vista!

La máquina Enigma (1)

● Enigma es inventada por Koch, que la vende a Arthur Sherbius. (Primera fabricada en 1.923).

● Tenía un teclado e inicialmente 3 rotores con las letras del alfabeto.

La máquina Enigma (2)

● Contactos eléctricos entre caras rotores.

● Cables que conectaban internamente caras rotor.

● Para cada pulsación de una letra se originaba una distinta.

● Antes de cifrar mensaje, se ponían rotores en cierto orden.

● Tanto para codificar como para decodificar, el resultado aparecía en un panel de luces con 26 bombillas.

● Enigma del Ejército y Fuerza Área alemanes tenían 5 rotores.

● Enigma Marina llegó a tener 8 rotores.

La máquina Enigma (3)

● Se le añadió sistema clavijas para convertir una letra en otra antes cifrado por rotores.

● Por otra parte, los rotores llegaron a ser extraíbles y se intercambiaban por otros almacenados en una caja.

● Después también se hizo posible modificar cableado contactos internos.

● El denominado reflector hacía posible el decodificado.

● El reflector estaba conectado al último rotor.

La máquina Enigma (4)

● Para cada día del mes, la máquina se ponía en cierta configuración rotores y clavijero.

● Nº configuraciones cifrado, es el número de permutaciones entre todos los dispositivos y por consiguiente muy elevado.

● Los polacos consiguieron analizar funcionamiento Enigma comercial.

● Alemanes codificaban posición inicial rotor por duplicado.

● Ambas cosas fueron aprovechadas por grupo matemáticos polacos, (Rejewski), a partir 1.932.

La máquina Enigma (5)

● Polacos construyen ciclómetro y después Bomba (Bomba Kriptologiczna).

● Con 3 rotores y sin clavijero, un experto británico, Foss, había roto la codificación. (Los alemanes también lo sabían y vendieron cientos de máquinas, incluyendo al bando franquista en nuestra Guerra Civil).

● Alemanes pasan de 3 a 6 rotores (1938) y polacos necesitarían 60 Bombas, por lo que dejan de decodificar.

● Un grupo polacos se va Francia y colabora con Bletchley Park, donde estaba Turing.

Marian Rejewski

Máquina Enigma cifrando

● En los siguientes enlaces vemos ejemplos de máquinas Enigma encriptando y desencriptando:

● Enigma cifrando

● Enigma descifrando

Turing en Bletchley Park (1)

● Bletchley Park estaba organizado en sectores llamados barracones.

– En un barracón se interceptaban mensajes.

– Otro descifraba.

– A partir de lo descifrado, se intentaba averiguar intenciones alemanes.

– También se repartía trabajo en función distintas redes comunicación.

– Turing se incorpora barracón 8 para descifrar Enigma Marina.

– 4 septiembre 1.939, (día siguiente declaración guerra inglesa).

– Diseña sistema cifrado conversaciones telefónicas (Dalila) (1.943).

Turing descifrando

Turing en Bletchley Park (2)

● Idea una nueva Bomba, que construirá Harold Keen y mejorará Gordon Welchman (Bomba de Turing-Welchman).

● Bomba pesaba casi 1 Tm. e incluía 108 rotores agrupados de 3 en 3. Los grupos de 3 rotores se agrupaban por docenas.

● Los rotores tenían el mismo cableado interno que Enigma.

● Cuando se interceptaba un mensaje Turing tenía que decidir cableado entre grupos de 3 rotores.

● La primera se construye el 18 marzo 1.940.

● Llegó a haber 211 con 2.000 personas para manejarlas.

Bomba de Bletchley Park (reconstrucción)

WRENS

Cómo se cifraba/descifraba en red Delfín (Marina alemana) (1)

● Operador elige posición de ventanilla. Ejemplo: MBO.

● Para enviar esa información, la cifra dos veces:

– Gira rotores posición base del día. Ejemplo: LIC.

– Pulsa MBO y obtiene: SAM.

– Elige otras 3 letras. Ejemplo: WAK.

– Pone: W A K

S A M

- Con la tabla de bigramas correspondiente al día cifra: WS, AA, KM.

- Obtiene: IK, PQ, GO.

Cómo se cifraba/descifraba en red Delfín (Marina alemana) (2)

– Envía: IKPQGO.

– Operador receptor hace operación inversa. Primero usa tabla de bigramas obteniendo: WS, AA, KM.

– Después pone rotores en posicíon LIC.

– Teclea SAM y apunta el resultado: MOB.

– Ahora podrá ya codificar los mensajes, tras poner los rotores en posición MBO.

● Todo esto lo averiguó Turing en una noche de 1.939 a partir de mensajes antiguos descifrados.

Métodos que usaba Turing (1)

● Uso de “chuletas” = “texto alemán sin cifrar”.

– Ejemplos:● “FORT” (“Forsetsung” = Continuación del mensaje anterior).

● “WEWA” (“Wetter Warte” = Estación Meteorológica).

● “WETTER FUER DIE NACHT” = Tiempo para la noche.

– Se localizaban zonas de texto en que no aparecieran letras de la chuleta (Enigma cifraba cada letra por otra distinta).

● “Pellizcos” = Captura de algún barco y su información.

● Ian Fleming diseñó un pellizco espectacular, pero no se pudo llevar a cabo, (“operación Ruthless”).

Métodos que usaba Turing (2)

● Desarrolló procedimientos estadísticos para usar mejor Bomba (“banburismo”).

● Otros métodos matemáticos, por ejemplo, teoría de grafos.

● Al cifrar la posición inicial de rotores, los alemanes lo hacían dos veces. Este error lo corrigieron en mayo 1940, pero poco después empezó a funcionar la primera Bomba de Turing y con ella pudieron seguir descifrando.

Algunas cosas que hacía Turing en Bletchley

● Iba a reuniones en Londres corriendo (64 Km.).

● Se comprometió con Joan Clarke (brillante matemática y criptoanalista).

● Rompió con Joan.

● También iba a ver a amigos suyos, corriendo unos 30 Km.

● Ganó una carrera organizada por militares.

● Tenía algunas curiosas manías; por ejemplo, ataba su taza para que no se la quitaran.

● Iba en bici con una máscara antigás para evitar la alergia.

La máquina Lorentz (“Tunny”)

● Cada carácter se pasaba a código Baudot (cinco bits).

● Mediante un sistema de 12 ruedas, se generaba nº de 5 bits (pseudoaleatorio) a partir de los 5 bits del carácter a cifrar.

● Se aplicaba XOR entre los bits del original y su cifrado.

● Si lo obtenido no era un carácter Baudot, se volvían a generar otros 5 bits.

● Se transmitía por Morse y el operador emisor y receptor no veían el texto cifrado, sino directamente en alemán.

● John Tiltman descifró mensaje de 4.000 caracteres.

Tunny

¿Cómo pudo descifrar Tiltman?

● A veces mensaje no llegaba bien a su destino.

● Por lo tanto, operador emisor repetía.

● Cuando repetía, quizá no cambiaba posición rotores.

● Si cifraba mensaje idéntico, el criptoanalista no podía hacer nada.

● En caso contrario, podía comparar diferencias.

● Tiltman trabajó 10 días para descifrar ese mensaje durante verano 1.941.

¿Qué se siguió haciendo?

● Bill Tutte a partir de la clave de Tiltman deduce funcionamiento Tunny.

● Turing elabora un método (“turingeria”) a partir de lo deducido por Tutte.

● Tutte decía que la turingeria era un método “más artístico que matemático”.

● Tutte inventa otro método, pero inabordable por los cálculos.

● Se lo cuenta a Max Newman.

● Tommy Flowers con las ideas de Newman construye Colossus.

Colossus

● Hubo una primera máquina, “Heath Robinson”, pero se averiaba.

● Primer ordenador electrónico, si exceptuamos Z3 de Zuse.

● Pesaba 1 Tm.

● Datos entrada: cinta de papel.

● Salida: impresora que parecía máquina de escribir.

● Completamente electrónico (válvulas).

● Se construyeron 10, el primero en diciembre de 1.943.

● Se destruyeron 8 y las otras 2 en la década de los 60.

Colossus

¿Qué decían de Turing en Bentchley?

● Knox (jefe y reclutador de Turing, descifraba desde la Primera Guerra Mundial y era un traductor de los poetas griegos):

– “Es muy difícil mantener a Turing a raya. Es muy inteligente, pero también bastante irresponsable y lanza montones de sugerencias de muy diferente valor.”

– “Yo tengo la autoridad y la habilidad justas, pero solo las justas para mantenerlos a él y a sus ideas en una suerte de orden y disciplina”. “Pero es muy bueno en lo suyo”.

● Birch (historiador y jefe Barracón 4 de Inteligencia Naval):

– “Turing y Twins son brillantes, pero como muchas personas brillantes, no son prácticos. Son desordenados, pierden cosas, no saben copiar correctamente y titubean entre la teoría y la fabricación de chuletas…”

Frase de Michie

● Donal Michie conoció a Turing en Bletchley y llegó a ser un buen amigo suyo y uno de los primeros grandes expertos en Inteligencia Artificial:

– “Cuando conocí a Alan, sus excéntricas maneras me llevaron erróneamente a creer que era todo cabeza y nada corazón. Cuando lo conocí mejor, me di cuenta de que sus emociones eran tan infantiles y en esencia tan buenas que, en un mundo tan ampliamente poblado por personas interesadas y egoistas, hacían de él una persona muy vulnerable”.

Breaking de Code

● El siguiente enlace es de un trozo de la película “Breaking de Code” en el que Turing es entrevistado por Knox, con objeto de reclutarle para su trabajo de decodificación en Bentchley Park.

● Breaking de Code

Alan después Guerra Mundial (1)

● En Laboratorio Nacional de Física (NPL) escribe “Proposed Electronic Calculator” (1.945).

● Ahí se describía por primera vez un ordenador digital de programa almacenado.

● Mucho detalle del hardware.

● ACE (“Automatic Computer Engine”).

● En 1.947 Turing abandona el proyecto y se va a Manchester.

● Allí participa en el proyecto de Bebé (“Baby”).

● Para él, escribe el primer manual de programación del mundo.

Alan después Guerra Mundial (2)

● En “Proposed Electronic Calculator” escribió: “Parece probable que se pueda desarrollar un sistema de almacenamiento adecuado sin involucrar ningún tipo nuevo de tubo, utilizando, de hecho, un tubo de rayos catódicos normal, con papel de aluminio sobre la pantalla para que actúe como plato de señal”.

● El jefe del proyecto, Williams, de hecho implementó esa forma de memoria, después de visitar el laboratorio de Eckert en Filadelfia, en el que se estaba trabajando con esa idea, pero realizando una modificación sustancial.

● Turing se llevaba muy mal con Kilburn el principal diseñador de Bebé, junto con Williams.

Alan después Guerra Mundial (3)

● En Manchester se compró una casa y estableció una relación excelente con los vecinos.

● También iba mucho a visitar a Max Newman. Su mujer se convirtió en una buena amiga.

● Turing fue el primero en conseguir que un ordenador tocará notas musicales.

● Strachey que había conocido a Turing en el King’s, se leyó el manual de programación y realizó un programa de 20 páginas que tocó “God Save the King”.

Alan después Guerra Mundial (4)

● Turing le dijo a un reportero de The Times: “No veía ninguna razón por la que el ordenador no debiera entrar en cualquiera de los campos normalmente cubiertos por el intelecto humano y, finalmente, competir en ellos en términos de igualdad”.

● Strachey crea un programa para escribir cartas de amor. Ejemplo: “QUERIDO ENCANTO. TÚ ERES MI SENTIMIENTO DE ÁVIDO COMPAÑERO. MI AFECTO CURIOSAMENTE SE AFERRA A TU APASIONADO DESEO. MI DESEO ANHELA TU CORAZÓN. TÚ ERES MI DESEOSA COMPASIÓN: MI TIERNO DESEO. TUYO HERMOSAMENTE. MUC

● Turing escribía cartas con el teclado del ordenador.

Alan y la Inteligencia Artificial

● Strachey elaboró (1.951) primer juego de ordenador: damas. Se ejecutó en el ordenador de Manchester.

● Pero, Turing con otro (Champernowne), había elaborado un programa de ajedrez en 1.948. Simulaban con papel y lápiz las jugadas de la máquina.

● En Bletchley Turing había ya escrito un documento sobre Inteligencia Artificial.

● En 2-1.947 da conferencia sobre I.A.: “Lo que queremos es una máquina que pueda aprender de la experiencia”. “No es en absoluto imposible hacer arreglos para controlar un ordenador remoto mediante una línea telefónica”.

Alan atleta de élite (1)

● Para ir a reuniones desde Bletchley corría 64 Km.

● Para ver a Max Newman, 20 Km.

● Para ir a otros sitios: ¿25?, ¿35?,…

● Perteneció al Walton Athletic Club.

● “I have such a stressful job that the only way I can get it out of my mind is by running hard.” (“Tengo un trabajo tan estresante que la única forma de sacarlo de mi mente es corriendo duro”).

● Estaba preseleccionado para el maratón de los Juegos Olímpicos de Londres de 1.948, pero no pudo por una lesión.

Alan atleta de élite (2)

● Su mejor tiempo en distancia maratón 2 h. 46 m. 3 s.

● Con ese tiempo hubiera sido el 15º en el maratón olímpico.

● El maratón de Londres del año 1.948 se ganó en 2:31:36.

● Actualmente el mejor tiempo olímpico en hombres es 2:06:32 (2.006, Pekín) y en mujeres 2:23:07 (2.012, Londres).

● Mejor tiempo en maratón no olímpico en hombres 2:03:23 (2.013, Berlín) y en mujeres 2:15:25 (2.003, Londres).

Alan corriendo

Castigo para Turing

● La policía descubre que Turing ha tenido relaciones homosexuales con ocasión de una denuncia por robo que este ha hecho.

● Se le deja elegir entre castración química o cárcel. (Elige lo 1º).

● Le produce degradación física.

● Lo toma con cierto humor:

– Pseudosilogismo: ● “Turing cree que las máquinas piensan. Turing yace con

hombres. Luego las máquinas no piensan”.

Muerte de Turing

● Es encontrado muerto el 8-6-1954 por su ama de llaves.

● Tres hipótesis:

– Suicidio con cianuro mordiendo manzana envenenada, (la del forense).

– Desgraciado accidente en su laboratorio, (la de su madre y algunos historiadores). Se descubrió tarro de mermelada con cianuro en su habitación.

– Asesinato por parte de los Servicios Secretos Británicos. (Era el hombre que sabía demasiado. Incluso en Manchester había realizado programa de cifrado para el Gobierno).

Disculpas por su muerte

● En 2.009 el primer ministro Gordon Brown pide disculpas en nombre del Gobierno, pero menciona que fue juzgado “según la ley del momento”.

● Los lores negaron el indulto porque: “Fue condenado correctamente por lo que en su tiempo era un delito“.

● El 24-12-2013 la Reina indulta a Turing, tras petición popular, incluyendo la de científicos como Stephen Hawkink.

● Miles de homosexuales británicos, que fueron castigados de forma similar, esperan todavía su indulto.

Máquina de Turing-A

● Turing inventa la Máquina-A (automática).

– Cinta infinita dividida en casillas.

– Cada casilla puede estar en blanco o tener un símbolo de un conjunto finito de los mismos. (Se suelen usar como símbolos 0 y1).

– La máquina tiene una unidad de lectura. En función del símbolo leído y del estado, (hay un conjunto finito de estados), escribe un nuevo símbolo, deja la casilla como estaba o pone un blanco.

– Además, cada vez que se lee un símbolo, la cinta puede desplazarse un cuadrado hacia la derecha o hacia la izquierda. (Puede no moverse).

– Tiene un estado inicial y cada vez que lee, puede cambiar su estado .

– La máquina puede llegar a parar o estar eternamente calculando.

Representación máquina Turing

Ejemplo máquina de Turing(Su cinta está inicialmente exclusivamente con blancos)

Estado Símbolo leído Símbolo escrito

Movimiento Siguiente estado

1 Blanco 0 R 2

2 Blanco Blanco R 3

3 Blanco 1 R 4

4 Blanco Blanco R 1

Máquina de Turing-Lego

Ejemplo máquina de Turing(Lector posicionado en primera casilla con 1, de un conjunto finito

unos contiguos, resto en blanco)

Estado Símbolo leído Símbolo escrito

Movimiento Siguiente estado

1 1 1 R 1

1 Blanco 1 Se para 2

Máquina de Turing de “diseño”

Máquina-U de Turing

● Máquina-U significa Máquina Universal.

● Simula a cualquier otra máquina de Turing con cualquier entrada, es decir, lo que tiene escrito en su cinta.

● Se le dan como datos una codificación de las instrucciones de la otra máquina y los datos de entrada.

● La idea es la misma que la de un ordenador de programa almacenado.

● Se admite que los ordenadores digitales tienen la misma posibilidad de cómputo que una máquina de Turing universal.

Primer teorema de incompletitud de Gödel

● Hizo trizas la pretensión de Hilbert de desarrollar todas las matemáticas a partir de axiomas y procedimientos mecánicos de deducción. Es decir, se trataba de formalizar la matemática.

● “Existen enunciados en el sistema formal de la aritmética que son verdaderos, pero indemostrables algorítmicamente a partir de cualquier conjunto de axiomas que elijamos”.

● Los axiomas son enunciados que tomamos como ciertos, por lo que no precisamos demostrarlos.

● En la aritmética se suelen usar los axiomas de Peano.

¿Qué demostró Turing?

● No es posible conocer si una máquina de Turing determinada ante cierta entrada se detendrá.

● Lo que hizo Turing fue numerar a sus máquinas, de tal manera que la pregunta es: ¿Se detendrá la máquina T(n) cuando se le introduce la entrada m, es decir, el número m ?

● Eso significa que existen funciones no computables o dicho de otra forma enunciados matemáticos para los que una máquina de Turing no puede probar la certeza de los mismos.

● Church había demostrado mediante el cálculo lambda un resultado equivalente.

● Actualmente se denomina “tesis de Church-Turing”.

Máquina-o de Turing (1)

● Turing la denominaba máquina oracular.

● Máquina de Turing conectada a una caja negra denominada oráculo. (Puede pensarse en una segunda cinta para oráculo).

● Se consulta a través de un símbolo especial denominado marcador.

● Entre 2 marcadores se sitúa símbolo sobre el que la máquina desea consultar al oráculo.

● Entonces la máquina pasa a estado especial denominado llamada, así envía petición al oráculo.

Máquina-o de Turing (2)

● Si este reconoce al símbolo como perteneciente a su conjunto de símbolos, la máquina pasa a estado-1 en caso contrario estado-0.

● Esta máquina la describe Turing en su tesis doctoral con la idea de ir más allá en su idea de computación, (hipercomputación).

● Algunos autores comparan el oráculo a una base de datos externa.

● Se podría decir que en ordenadores sería como consultar a Internet.

Otras máquinas de Turing

● Estas máquinas se han descrito posteriormente.

● Máquinas con varias cintas.

● Máquinas policefálicas, es decir, varias cabezas de lectura/escritura sobre una misma cinta.

● Máquina probabilística o no determinista. Selecciona aleatoriamente entre las transiciones disponibles con idéntica probabilidad para cada alternativa.

● El premio Nobel de Física Richard Feynman predijo que ciertos fenómenos cuánticos no serían calculables con una máquina de Turing convencional, pero si con una máquina cuántica.

Biología matemática

● 1952: “La base química de la morfogénesis”.

● Turing postula la existencia de ciertas sustancias químicas, los “morfógenos”.

● Denomina su teoría como “reacción-difusión”.

● Ondas de sustancias químicas se difunden por el embrión en desarrollo y dan forma a su crecimiento.

● Donde están más concentradas las sustancias, mayor es el crecimiento.

● Turing estudió Hydra, pequeño animal de agua dulce con un anillo de media docena de tentáculos.

Test de Turing

● Un interrogador tiene que averiguar si lo que hay encerrado en una habitación es una persona o un ordenador.

● Si es un ordenador y consigue engañar a la persona que pregunta, este pasa el test.

● Turing creía que se podrían construir máquinas que pensasen.

● En 1.948 propuso utilizar “cámaras de TV, micrófonos, altavoces y servomecanismos para construir un robot”.

● El robot necesitaría “vagar por el campo” para aprender cosas por si mismo.

Test de Turing

La habitación china de Searle

● Imaginemos que una persona no entiende chino.

● Se le pregunta en chino escrito.

● Tiene instrucciones escritas en castellano para en función de la pregunta, conseguir dar una respuesta en ideogramas chinos.

● Supongamos que es capaz de para toda pregunta dar la respuesta correcta.

● ¿Significa eso que comprende lo que le preguntan?.

● Si en lugar de una persona fuera un ordenador, habría pasado el test de Turing, pero no habría comprendido nada.

CAPTCHA

● “Completly Automatic Public Turing test to tell Computers and Humans Apart”.

● Es el test que casi todo el mundo que usa Internet, ha realizado más de una vez al registrarse como usuario de algunas webs.

● Consiste en escribir en un recuadro una serie de letras y en ocasiones cifras que se muestran totalmente deformadas para que sea difícil que un programa informático las pueda reconocer.

● De esa forma, se intenta que ciberdelincuentes no puedan hacer cosas indebidas, por ejemplo, spam.

Ejemplo de CAPTCHA

HAL 9000

● En la película “2.001 una odisea del espacio”, dirigida por Stanley Kubrick, aparece el ordenador “HAL 9000”, que tiene capacidades intelectuales por encima de las humanas. No solo sería capaz de pasar el test de Turing, sino que es un ser consciente.

● Según Roger Penrose, los ordenadores, aunque su capacidad futura les permitiera pasar el test de Turing, no serán capaces de tener una consciencia similar a la de los humanos o incluso a la de los animales superiores. Los siguientes son enlaces a trozos de la película significativos, doblado y versión original:

● HAL 9000 traducido HAL 9000 versión original

Muchas gracias por la asistencia

A continuación un poco de bibliografía y algunas películas.

Bibliografía – libros (1)

● B. Jack Copeland - “Alan Turing: El pionero de la era de la

información” - Turner.

● Rafael Lahoz-Beltra - “Turing: La computación. Pensando en

máquinas que piensan” – Grandes ideas de la ciencia (RBA).

● Roger Penrose - “La mente nueva del emperador: En torno a la

cibernética, la mente y las leyes de la física” - Fondo de Cultura Económica.

● Javier Fresán - “El sueño de la razón: La lógica matemática y sus

paradojas” – El mundo es matemático (RBA).

Bibliografía – libros (2)

● Vicenç Torra - “Del ábaco a la revolución digital: Algoritmos y

computación” - El mundo es matemático (RBA).

● Ricardo Peña – “De Euclides a Java: Historia de los algoritmos y de

los lenguajes de programación” - Nivola.

Bibliografía – Internet

● http://www.alanturing.net/● http://encuentros3cantos.blogspot.com.es/2012/04/alan-turing-p

ionero-de-las-ciencias-de.html

● http://www.turing.org.uk/index.html

● http://histinf.blogs.upv.es/2010/11/01/breve-biografia-de-alan-turing/

● http://www.kriptopolis.com/ (Pinchar en pestaña que pone Enigma)

● http://es.wikipedia.org/wiki/Turing

● http://blogs.elpais.com/turing/

Películas (1)

● Breaking de Code (Rompiendo el código)

– Director: Herbert Wise.

– Año: 1.996.

– Actor que hace de Turing: Derek Jacobi.

– Escritores: Andrew Hodges (novela), Hugh Whitemore (guión).

● Enigma

– Director: Michael Apted.

– Año: 2.001

– Reparto: Dougray Scott, Kate Winslet.

– Escritores: Robert Harris (novela), Tom Stoppard (guión).

Películas (2)

● The Turing Enigma.

– Director: Pete Wild.

– Año: 2.011.

– Actores: Sam Edge, Helen Webster, Ian Pink.

– Guión: Pete Wild.

● The Imitation Game. (El juego de la imitación).

– Director: Morten Tyldum.

– Año: 2.014.

– Actores: Benedict Cumberbatch (Turing), Keira Knightley (Joan Clarke), Charles Dance.

– Guión: Graham Moore.

Posters de películas (1)

Posters de películas (2)