Berço da Computação -Alan Mathison Turing 
Alan Mathison Turing
nasceu em 23 de junho de 1912 em Londres, filho de um oficial britânico, Julius
Mathison e Ethel Sara Turing. Seu interesse pela ciência começou cedo, logo que
aprendeu a ler e escrever, distraia-se fatorando números de hinos religiosos e
desenhando bicicletas anfíbias. A maior parte do seu trabalho foi desenvolvido
no serviço de espionagem, durante a II Grande Guerra, levando-o somente por
volta de 1975 a ser reconhecido como um dos grandes pioneiros no campo da
computação.
Em 1928, Alan começou a estudar a Teoria da Relatividade, conhecendo Christopher
Morcom, que o influenciou profundamente. Morcom morreu em 1930 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 mecânica
quântica. Chegou inclusive a escrever sobre a possibilidade do espirito sobreviver
após a morte
.
Depois de concluir o mestrado em King's College (1935) e receber o Smith's prize em 1936 com um trabalho sobre a Teoria das Probabilidades, Turing se enveredou pela área da computação. Sua preocupação era saber o que efetivamente a computação poderia fazer. As respostas vieram sob a forma teórica, de uma máquina conhecida como Turing Universal Machine, que possibilitava calcular qualquer número e função, de acordo com instruções apropriadas.
Quando a II Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicações da Gran Bretanha (Government Code and Cypher School) em Buckinghamshire, com o intuito de quebrar o código das comunicações alemãs, produzido por um tipo de computador chamado Enigma. Este código era constantemente trocado, obrigando os inimigos a tentar decodifica-lo correndo contra o relógio. Turing e seus colegas cientistas trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor dos computadores digitais.
Durante a guerra, Turing foi enviado aos EUA a fim de estabelecer códigos seguros para comunicações transatlânticas entre os aliados. Supõe-se que foi em Princeton, NJ, que conheceu Von Neumann e daí ter participado no projeto do ENIAC na universidade da Pensilvânia..
Terminada a guerra, Alan se
juntou ao National Physical Laboratory para desenvolver um computador totalmente
inglês que seria chamado de ACE (automatic computing engine). Decepcionado com
a demora da construção, Turing mudou-se para Manchester. Em 1952, foi preso por
"indecência", sendo obrigado a se submeter à psicanálise e a
tratamentos que visavam curar sua homosexualidade. Turing suicidou-se em
Manchester, no dia 7 de junho de 1954, durante uma crise de depressão, comendo
uma maçã envenenada com cianeto de potássio.
O Teste de Turing
O teste consistia em submeter um operador, fechado em uma sala, a descobrir se
quem respondia suas perguntas, introduzidas através do teclado, era um outro
homem ou uma máquina. Sua intenção era de descobrir se podíamos atribuir à
máquina a noção de inteligência. A revolução do computador começou efetivamente
a realizar-se no ano de 1935, em uma tarde de verão na Inglaterra, quando Alan
M. Turing (1912-1954), estudante do King's College, Cambridge, durante
curso ministrado pelo matemático Max Neumann, tomou conhecimento do Entscheidungsproblem
de Hilbert. Enquanto isso, conforme foi brevemente citado no item
precedente, uma parte da comunidade dos matemáticos buscava um novo tipo de
cálculo lógico, que pudesse, entre outras coisas, colocar em uma base
matemática segura o conceito heurístico do que seja proceder a um cômputo.
O resultado destas pesquisas era fundamental para o desenvolvimento da
matemática: tratava-se de saber se é possível haver um procedimento efetivo
para se solucionar todos os problemas de uma determinada classe que estivesse
bem definida. O conjunto desses esforços acabou por formar a fundamentação
teórica da que veio a ser chamada "Ciência da Computação".
Os resultados de Gödel e o problema da decisão motivaram Turing primeiramente a tentar caracterizar exatamente quais funções são capazes de ser computadas. Em 1936, Turing consagrou-se como um dos maiores matemáticos do seu tempo, quando fez antever aos seus colegas que é possível executar operações computacionais sobre a teoria dos números por meio de uma máquina que tenha embutida as regras de um sistema formal. Turing definiu uma máquina teórica que se tornou um conceito chave dentro da Teoria da Computação. Ele enfatizou desde o início que tais mecanismos podiam ser construídos e sua descoberta acabou abrindo uma nova perspectiva para o esforço de formalizar a matemática, e, ao mesmo tempo, marcou fortemente a História da Computação.
A percepção genial de Turing foi a substituição da noção intuitiva de procedimento efetivo por uma idéia formal, matemática. O resultado foi a construção de uma conceituação matemática da noção de algoritmo, uma noção que ele modelou baseando-se nos passos que um ser humano dá quando executa um determinado cálculo ou cômputo. Turing formalizou definitivamente o conceito de algoritmo.
A Máquina de Turing
O trabalho de Alan Turing ficou documentado no
artigo On Computable Numbers with an aplication to the Entscheidungsproblem, publicado
em 1936. Turing descreveu em termos matematicamente precisos como pode ser
poderoso um sistema formal automático, com regras muito simples de operação.
"O que faz o raciocínio humano quando executa um cálculo"?,
perguntou-se Turing. Ele definiu que os cálculo mentais consistem em operações
para transformar números em uma série de estados intermediários que progridem
de um para outro de acordo com um conjunto fixo de regras, até que uma resposta
seja encontrada. Algumas vezes é usado o papel e o lápis para não se perder o
estado dos nossos cálculos. As regras da matemática exigem definições mais
rígidas que aquelas descritas nas discussões metafísicas sobre os estados da
mente humana, e Turing concentrou-se na definição destes estados de tal maneira
que fossem claros e sem ambigüidades, para que tais definições pudessem ser
usadas para comandar as operações da máquina.
Turing começou com uma descrição precisa de um sistema formal, na forma de
"tabela de instruções" que especificariam quais movimentos a fazer
para qualquer configuração possível dos estados no sistema. Provou então que os
passos de um sistema axiomático formal semelhante à lógica e os estados da
máquina que fazem os "movimentos" em um sistema formal automático são
equivalentes entre si. Estes conceitos estão todos subjacentes na tecnologia
atual dos computadores digitais, cuja construção tornou-se possível uma década
depois da publicação de Turing.
Um sistema formal automático é um dispositivo físico que manipula
automaticamente os símbolos de um sistema formal de acordo com as suas regras.
A máquina teórica de Turing estabelece tanto um exemplo da sua teoria da
computação como uma prova de que certos tipos de máquinas computacionais
poderiam, de fato, ser construídas. Efetivamente, uma Máquina de Turing
Universal, exceto pela velocidade, que depende do hardware, pode simular
qualquer computador atual, desde os supercomputadores até os computadores
pessoais, com suas complexas estruturas e poderosas capacidades computacionais,
dado o tempo e memória necessários. Alan Turing provou que para qualquer
sistema formal existe uma Máquina de Turing que pode ser programada para
imitá-lo. Ou em outras palavras: para qualquer procedimento computacional bem
definido, uma Máquina de Turing Universal é capaz de simular uma máquina que
execute tais procedimentos.
De um ponto de vista teórico, a importância da Máquina de Turing está no fato
de que ela representa um objeto matemático formal. Através dela, pela primeira
vez, se deu uma boa definição do que significa computar algo. E isso levanta a
questão sobre o que exatamente pode ser computado com tal dispositivo
matemático.
O problema da parada e o problema da decisão
Turing mostrou que o
funcionamento de sua máquina (usar-se-á a sigla MT a partir de agora) e a
aplicação das regras de formação de um sistema formal não têm diferença. Ele
demonstrou também que seu dispositivo poderia resolver infinitos problemas mas
havia alguns que não seriam possíveis, porque não haveria jeito de se prever se
o dispositivo pararia ou não. Colocando de uma outra maneira: dado um programa
P para uma MT e uma determinada entrada de dados E, existe algum programa que
leia P e E, e pare após um número finito de passos, gerando uma configuração
final na fita que informe se o programa P encerra sua execução após um número
finito de passos ao processar E?
Comparando-se com as afirmações sobre verdades aritméticas, dentro de um
sistema formal consistente da aritmética, que não são passíveis de prova dentro
deste sistema, percebe-se que o problema da parada de Turing nada mais é do que
o Teorema de Gödel, mas expresso em termos de uma máquina computacional e
programas ao invés de uma linguagem de um sistema dedutivo da Lógica
Matemática.
Em 1936 Turing provou formalmente o seguinte teorema:
Teorema da Parada: Dado um programa P qualquer para uma Máquina de
Turing e uma entrada E qualquer de dados para esse programa, não existe uma
Máquina de Turing especifica que pare após um número finito de passos, e que
diga se P em algum momento encerra sua execução ao processar E.
A solução negativa deste problema computacional implica também numa solução
negativa para o problema de Hilbert. Portanto nem todos os enunciados
verdadeiros da aritmética podem ser provados por um computador. 
Figura:
Relacionamento entre os mundos formais, matemáticos e computacionais
A tese de Church-Turing e outros resultados teóricos
Após os resultados de Gödel em 1931 muitos lógicos matemáticos partiram em busca do que seria uma noção formalizada de um procedimento efetivo (por efetivo entenda-se mecânico), ou seja, o que pode ser feito seguindo-se diretamente um algoritmo ou conjunto de regras (como já visto, antigo sonho de séculos,que remonta a Leibniz). Destas buscas surgiram: a sistematização e desenvolvimento das funções recursivas (introduzidas nos trabalhos de Gödel) por Stephen Cole Kleene (1909-1994) em sua teoria lógica da computabilidade (parte de seu livro Introdução à Metamatemática, um dos cumes da lógica matemática as Máquinas de Turing; dos últimos anos); cálculo-lambda (componente característico fundamental da linguagem de programação LISP) de Alonzo Church;a Máquina de Post, análoga à de Turing, tornada pública um pouco depois, fruto de trabalho independente, e seu sistema para rescrita de símbolos (cuja gramática de Chomsky é um caso particular), de Emil L. Post (1897-1954).
Com efeito, todos estes conceitos levaram à mesma conclusão e acabaram por ter o mesmo significado, dentro do citado escopo da busca de uma definição bem elaborada de processo efetivo. No presente trabalho referirer-se-á mais a Church e Turing (Kleene fez em seu trabalho uma ampla abordagem de ambos, tirando várias conseqüências, e Post trata do mesmo tema de Turing), para se ter uma visão mais clara da diversificação dos estudos desta década de 1930 para a fundamentação teórica de toda a Computação.
Alan Turing ajudou no planejamento de um poderoso computador, no pós-guerra; era uma máquina que incorporava um programa armazenado e outras idéias que ele concebera para sua máquina universal. O modelo piloto da ACE, ou Máquina de Computação Automática (Automatic Computing Engine), tornou-se operacional em maio de 1950. Ele poderia aperfeiçoá-lo ainda mais; suas excentricidades, porém, interpuseram-se no caminho. Turing preocupava-se cada vez mais com questões abstratas sobre a inteligência da máquina (ele até inventara um teste para determinar se os computadores podem realmente pensar) e com seus próprios e urgentes problemas pessoais. Sua homossexualidade declarada levou-o à prisão em 1952 por "grosseira indecência", a psicanálise o sentenciou e Turing fez tratamentos com hormônios. Dois anos depois, enquanto se entretinha com o que chamava de jogo da "ilha deserta" onde fabricava produtos químicos a partir de substâncias comuns de uso doméstico, Turing fez cianureto de potássio e suicidou-se. A simplicidade do problema de Hilbert é apenas aparente, e somente após 70 anos de esforços foi encontrada a solução, por Matijasevic, um matemático russo de apenas 22 anos na época. É uma solução bastante complexa, dependendo tanto de resultados da Teoria do Números, conhecidos há muitíssimos anos, como do trabalho anterior de três americanos, Martin Davis, Julia Robinson e Hilary Putnan, que por sua vez baseia-se em certos resultados fundamentais sobre lógica e algoritmos descobertos na década de 30 por Kurt Gödel, Alan Turing, Emil Post, Alonso Church e Stephen Kleene. A resposta a esse problema de Hilbert é: tal algoritmo não existe: o décimo problema é indecidível.
CONHEÇA UM POUCO SOBRE / LINKS E REFERÊNCIA BIBLIOGRÁFICAS /