Alan Mathison Turing
Anny Key de Souza Mendonça
Cesar Duarte Souto-Maior
Régis Sangoi Padilha
1
Alan Turing
 23
de Junho de 1912 – V7 de Junho de 1954
 Contribuições:

Máquina de Turing e a tese de Church-Turing

Colossus (Enigma)

Teste de Turing
2
Infância






Nasceu em Londres em 1912.
O pai era servidor público nas Índias.
Em 3 semanas aprendeu a ler sozinho com um livro chamado
“Reading without tears”.
Diziam que era gago.
Durante sua infância a família morava na França para pagar
menos impostos.
Em 1922 (10 anos) ele ganhou um livro chamado “Natural
Wonders Every Child Should Know”, e segundo Turing esse
livro abriu sua mente para a ciência.
3
Infância





Estudava química desde os 12 anos.
Em 1926 (14 anos) ele foi aceito para estudar em Sherborne.
Quando chegou na Inglaterra, estava tendo uma greve de trem e
ele foi até a escola de bicicleta (cerca de 60 milhas), evento que
foi até publicado no jornal local .
Começou a ler os trabalhos de Einstein em 1928 (16 anos).
Christopher: amizade, amor platônico e morte.
4
Alan Turing

Em outubro de 1931, ganhou uma bolsa de estudo - King’s College, em
Cambridge
 Estudou Matemática
 Conversava muito pouco
 Compreensão da sexualidade
 Descobriu que um de seus colegas partilhava de sua
inclinação sexual

Inicio da década de 30, Cambridge era uma das mais
importantes instituições do mundo em matemática e ciência
 O físico Paul Dirac e seus colaboradores haviam alçado
a universidade a uma posição em física quântica.
King’s College tinha o privilegio de ter como professor:
 George Hardy – um dos mais exímios matemático da
época
 Arthur Eddington – cujo trabalho havia confirmado
a teoria da relatividade de Einstein
 Ambos deram aulas para Turing

5
Alan Turing



Sra. Turing não sabia sobre a sexualidade do filho
 Embora o filho tivesse sido admitido na Pós-graduação do King’s College
(fosse o cérebro matemático mais brilhante da Grã-bretanha)
 A mãe tinha a necessidade de envergonhar o filho dizendo que tinha a
cabeça nas nuvens
 Sua relação com a mãe era estreita, em suas cartas tentava mantê-la
informada ate de seus pensamentos matemáticos
 Mencionava coisas relacionadas a teoria quântica
Em 1933 depois que Hitler tomou o poder na Alemanha, muitos exilados
alemães passaram por Cambridge fazendo conferencia e Turing pode ouvir
 Schrodinger – falando sobre mecânica quântica
 Max Born – ministrar um curso sobre mecânica quântica
1935 foi nomeado membro do King’s College
6
Máquina de Turing
São dispositivos extremamente básicos que manipulam
símbolos
 Simples, porém podem ser adaptadas para simular a
lógica de qualquer computador
 Descritas pela 1ª vez em 1936 por Turing no artigo "On
Computable Numbers, with an Application to the
Entscheidungsproblem" ("problema de decidibilidade")
 Introduziu conceitos computacionais como memória,
programa, programa armazenado na memória e
linguagem de programação.

7
Máquina de Turing



Apesar de ser possível sua construção,
estas máquinas não foram concebidas
para ser uma tecnologia usada na
prática e sim um experimento mental
sobre os limites da computação
mecânica.
O estudo de suas propriedades
abstratas permitiu muitas descobertas
sobre a ciência da computação e a
teoria da complexidade computacional
(problema da parada).
Tese de Church-Turing (Kleene-1943):
Toda função que seria naturalmente
percebida como computável, pode ser
computada por uma máquina de Turing
8
Máquina de Turing – Descrição Informal




Uma fita que é divida em células, uma
adjacente à outra. Cada célula contem um
símbolo de algum alfabeto finito.
Um cabeçote, que pode ler e escrever
símbolos na fita e mover-se para a esquerda
e para a direita.
Um registrador de estados, que armazena o
estado da máquina de Turing. O número de
estados diferentes é sempre finito e há um
estado especial denominado estado inicial
com o qual o registrador de estado é
inicializado.
Uma tabela de ação (ou função de transição)
que diz à máquina que símbolo escrever,
como mover o cabeçote (para esquerda,
para direita ou ficar parado) e qual será seu
novo estado, dados o símbolo que ele
acabou de ler na fita e o estado em que se
encontra. Se não houver nenhuma entrada
na tabela para a combinação atual de
símbolo e estado então a máquina pára.
9
Máquina de Turing – Descrição Formal

A definição formal usual da Máquina de Turing com uma fita é uma sêxtupla
M = (Q,Γ,s,b,F,δ), onde:







Q é um conjunto finito de estados
Γ é o alfabeto da fita (conjunto finito de símbolos)
é o estado inicial
é o símbolo branco
é o conjunto dos estados finais
é uma função parcial chamada função de transição,
onde E é o movimento para a esquerda e D é o movimento para a direita.
A definição varia na literatura, para tornar argumentos ou provas mais fáceis
ou mais claras, mas isto sempre é feito mantendo o poder computacional da
máquina resultante. Acrescentar a possibilidade do cabeçote permanecer na
mesma célula da fita em vez de mover-se não aumenta o poder computacional
da máquina, por exemplo.
10
Máquina de Turing
 Exemplos:
11
Máquina de Turing – Variações
 Fitas
Finitas e Infinitas de um lado ou em ambos
os lados
 Fitas Bi-dimensionais
 Movimento arbitrário do cabeçote
 Número arbitrário de cabeçotes
 Alfabeto finito arbitrário
 Maquinas de Turing não-determinísticas
12
Doutorado em Princeton





Foi orientado por Alonzo Church e obteve o título de PHD.
Concluiu que o que podia ser calculado pelo método de Church,
também podia ser calculado por uma máquina de Turing.
Após 1933, muitos alemães foram para os EUA. Em Princeton
estava Einstein e outros cientistas famosos.
Lá encontrou um ambiente menos formal, jogou hóquei e
aprendeu a dirigir
Von Neumann reconheceu seu trabalho e usou idéias de Turing
na construção do EDVAC
13
Bletchley Park

Historia de Bletchley começou em 1938, quando o engenheiro Robert
Lewinski apareceu afirmando ter trabalhado na construção de uma máquina
que sinalizava códigos
Fotografia de Bletchley Park, sede do centro de criptografia britânica na Segunda Guerra Mundial.
14
Enigma



Era uma máquina de codificar usada pelo comando alemão para enviar ordens
codificadas para sua forca no campo
A operação era simples, seu sistema de codificação, no entanto, parecia ser
indecifrável
Consistia de duas máquinas:
 Máquina emissora – era fixada uma chave, e a mensagem não codificada
era introduzida por datilografia.
 A mensagem era imediatamente embaralhada por três (ou mais)
rotores elétricos que eram ajustado de acordo com a chave, e em
seguida transmitida.
 Máquina receptora – estava fixada a mesma chave, e a mensagem podia
então ser desembaralhada e impressa sob forma decodificada
15
Enigma




Os rotores, que giravam de maneira independente, permitiam bilhões de
permutações de modo que qualquer inimigo que detectasse a transmissão
embaralhada via-se diante de uma tarefa aparentemente impossível se
quisesse decifrar o código
Milhões de mensagens eram enviadas a cada 24 horas, e a chave era
alterada três vezes por dia
Graças a Lewinski, os dirigentes do serviço de informação de Bletchley
sabiam como a maquina funcionava
 Mas, não era o bastante
 Depois que cada letra de uma mensagem era teclada, os rotores
giravam mais uma vez
 Assim, mesmo que a mesma letra fosse teclada varias vezes em
seguida, isso iria produzir letra diferentes na versão embaralhada
Para decifrar o código, era preciso conhecer a chave em que a maquina
fora fixada: somente isso determinava a posição inicial dos rotores
16
Máquina Enigma
17
Colossus


Em 1943 – começou a operar o COLOSSUS
Colossus era a máquina de decodificar de Turing ( as dificuldades eram tais
que foram preciso construir dez versões dela em Bletchley)



Computador inglês – Segunda Guerra Mundial.
Símbolos perfurados em fitas de papel
O Colossus tinha como objetivo fazer a criptoanálise de códigos alemães
ultra-secretos produzidos pela máquina de codificação Enigmas
18
Bombe

A Bombe era uma máquina eletro-mecânica com vários
conjuntos de rotores idênticos aos da Enigma.
Cripto-analista da marinha
Norte-Americana com uma
Bombe (cerca de 1944).
Imag.The Mariners's Museum
19
Bombe


Ao contrário da Enigma, os rotores da Bombe rodavam
automaticamente para percorrer todas as configurações
possíveis.
Quando encontrasse uma configuração que tornasse compatível
a palavra adivinhada e o texto cifrado, a máquina parava e o
cripto-analista iria testar aquela configuração com o resto do
texto cifrado numa Enigma;
 se o resultado não fosse correto, reinicializava a bombe para
continuar a procura.
20
Final da Guerra



Em novembro de 1942, retornou aos EUA para trabalhar com a marinha sobre
o ENIGMA naval e ajudou a Bell Labs no desenvolvimento de dispositivos
de conversa seguros.
Após seu retorno começou a aprender sozinho eletrônica, no intuito de
desenvolver uma maquina portátil que permita comunicação segura por voz,
denominada Delilah. Ela não podia ser usada em transmissões por rádio de
longas distâncias, e foi terminada muito tarde para seu uso na guerra, apesar
de seu uso ser demonstrado através da transmissão de um discurso de
Winston Churchill.
Em 1945, foi condecorado com o Order of the British Empire pelo seus
esforços na guerra.
21
Após a Guerra




Trabalhou no desenvolvimento do ACE (Automatic Computing
Engine), mas abandonou o projeto antes da conclusão.
Na Universidade de Manchester coordenou o projeto do MARK
I, onde criou um programa para jogar xadrez.
Criou o Teste de Turing.
De 1952 até a sua morte, trabalhou com matemática biológica
(morfogênese).
22
Teste de Turing



O Teste de Turing é baseado no jogo da imitação e envolve um
computador, um interrogador humano e um entrevistado
humano.
O interrogador deve tentar descobrir, por meio de perguntas qual
dos participantes é o computador.
Toda comunicação é feita através de um terminal de computador.
23
Teste de Turing
24
Teste de Turing



O interrogador pode perguntar qualquer tipo de pergunta.
O computador pode adotar qualquer estratégia para enganar o
entrevistador, como por exemplo:
 Mentir. Ex: Você é um computador? Não.
 Se o entrevistador pedir o resultado da multiplicação de
dois números grandes, o computador pode demorar para
responder e responder errado.
O humano entrevistado não deve tentar enganar o
entrevistador e deve tentar ajudar o entrevistador.
25
Teste de Turing




Turing defendia a idéia de que se várias pessoas diferentes
atuam como entrevistador e entrevistado e um número
suficiente de entrevistadores não for capaz de descobrir qual é
o computador, então o computador pensa.
Desde 1991 existe o concurso de Loebner para premiar
anualmente o melhor chatterbot.
O chatterbot mais famoso é o Eliza. Que tinha apenas 204
linhas de código.
Existe uma aposta de 10 mil dólares, registrada no “Long Bets
Foundation”, entre Mitch Kapor e Ray Kurzweil. Kapor acha
que o Teste de Turing vai ser superado até 2029.
26
Escândalos





Julgamento
Homossexual declarado - foi humilhado em
público
Impedido de acompanhar estudos sobre
computadores
Teve que passar por terapias à base de hormônios
Deprimido, em 7 de Junho de 1954, com apenas
41 anos, cometeu suicídio comendo uma maçã
envenenada.
27
Pós Morte







Alan Turing aparece em diversos livros escritos
Conta com 3 biografias, a definitiva sendo
considerada a escrita por Andrew Hodges, intitulada
Alan Turing: The Enigma (1983)
Turing Award, dado pela Association for Computing
Machinery, desde 1966. É considerado o “prêmio
Nobel da computação”.
Seu nome foi dado uma rua que faz parte do anel
central de Manchester e a um instituto de pesquisa
em matemática da universidade de Manchester, entre
outros.
Duas estátuas foram dedicadas a ele.
Diversos eventos anuais e comemorativos.
Complementações de outros autores sobre seu
trabalho... (Computers are not Turing machines,
super-Turing computation)
28
FIM
29