Alan Turing

1. Infância

Alan Mathison Turing nasceu no dia 23 de junho de 1912 em Paddington, Londres – Inglaterra. Seu pai, Julius Mathison Turing, era membro Britânico no Serviço Civil Indiano, e sua mãe, Ethel Sara Stoney, era filha do chefe de máquinas do Alan Madras ferrovias.

Desde a infância, Turing já se interessava pela ciência, distraia-se fatorando números de hinos religiosos e desenhando bicicletas anfíbias. Era um garoto tímido e nas series iniciais não era bom aluno, destacava-se apenas por ser esquisito, introvertido, irônico, pouco disposto a respeitar regras. Um cara tão estranho que, no futebol, gostava de ser bandeirinha.

Ainda jovem Alan começou a estudar a Teoria da Relatividade, conhecendo Christopher Morcom, nesse momento Turing descobriu um fato que mudou sua vida, ele era homossexual. Morcom faleceu em 1930 com pneumonia bobina e Alan se motivou a fazer o que o amigo não teve tempo, durante anos trocou correspondências com a mãe de Morcom a respeito das idéias do amigo e se maravilhou com a possibilidade de resolver problemas com a teoria da mecânica quântica.

Turing iniciou sua carreira na área da matemática em 1931 no King’s College em Cambridge, onde pode explorar suas próprias idéias, lia livros sobre filosofia da matemática e mecânica quântica. Formou-se em 1934, Turing então, enveredou-se pela área da computação. Sua preocupação era saber o que efetivamente a computação poderia fazer. Em 1935 foi nomeado membro do King’s College. Em 1936 ele publicou um artigo intitulado “On Conputable Numbers, with an Application to the Entscheidungsproblem”onde tentou capturar a noção de algoritmo e descrevia uma máquina abstrata, hoje chamada de “Máquina de Turing” que se movia de um estado para outro usando um conjunto de regras precisas finitas, e dependendo de um único símbolo lê-lo a partir de uma fita. No artigo ele mostrou também que o “Entscheidungsproblem”(Decisão Problema) não pode ser resolvido e junto Alonzo Church definiram a tese que leva seus nomes, a tese Church-Turing enunciada como “Toda função que seria naturalmente considerada computável pode ser computada por uma máquina de Turing”, ou seja, o que pode ser calculado pelo método de Church, também pode ser calculado por uma máquina de Turing. Alan Turing introduziu também conceitos como memória, programa, programa armazenado na memória e linguagem de programação.

2. Máquina de Turing

A máquina de Turing poderia escrever um símbolo na fita ou excluí-lo.

Ele descreveu uma máquina que leria uma série de uns e zeros a partir de uma fita. Esses zeros e uns descreviam os passos que precisavam ser realizados para resolver um cálculo ou executar uma determinada tarefa. A máquina de Turing iria ler cada um dos passos e realizá-las na seqüência. Este conceito era revolucionário na época. As maiorias dos computadores da década de 50 eram de uso específico, tendo uma gama limitada de efeitos. Já a máquina de Turing poderia fazer qualquer tarefa, desde que programado apropriadamente.

O modelo da máquina de Turing usa uma fita infinita como sua memória ilimitada. Ela tem um cabeçote que pode ler e escrever símbolos e mover-se sobre a fita. Inicialmente, a fita contém apenas a cadeia de entrada e está em branco em todo o restante. Se a máquina precisa armazenar informações, ela pode escrevê-la sobre a fita. Para ler a informação escrita, a máquina pode mover sua cabeça de volta para a posição onde a informação foi escrita. A máquina continua a computar até que ela decida produzir uma saída. As saídas aceite e rejeite são obtidas entrando em estados designados de aceitação e de rejeição. Se não entrar num estado de aceitação ou de rejeição, ela continuará para sempre, nunca parando.

Admitindo que o cabeçote de leitura e gravação possa mover-se da direita para a esquerda e que a máquina possua dois caracteres, “0” e “1”, onde 0 representa o símbolo branco conferimos o exemplo do programa abaixo, seguindo uma lista de regras. Ela espera uma série de 1's na fita, com o cabeçote inicialmente no 1 mais à esquerda, e duplica os 1's com um 0 no meio. Por exemplo, "111" torna-se "1110111". O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1. A tabela de ação é dada a seguir.

Old Read Wr. New

St. Sym. Sym. Mv. St.

- - - - - - - - - - - - - - - - - - - -

s1 1 -> 0 D s2

s2 1 -> 1 D s2

s2 0 -> 0 D s3

s3 0 -> 1 E s4

s3 1 -> 1 D s3

s4 1 -> 1 E s4

s4 0 -> 0 E s5

s5 1 -> 1 E s5

s5 0 -> 1 D s1

A primeira linha desta tabela pode ser lida como: "Se a máquina estiver no estado s1 e o símbolo lido pelo cabeçote for 1, então escreva o símbolo 0, mova uma posição para a direita e mude o estado para s2".

Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito)

Passo Estado Fita

- - - - - - - - - - - - -

01 s1 11

02 s2 01

03 s2 010

04 s3 0100

05 s4 0101

06 s5 0101

07 s5 0101

08 s1 1101

09 s2 1001

10 s3 1001

11 s3 10010

12 s4 10011

13 s4 10011

14 s5 10011

15 s1 11011

O funcionamento desta máquina