e outros teoricos para definir e descrever tais sistemas formais, incluindo conceitos como recursividade e calculo lambda. Em 1936 Alan Turing e Alonzo Church independentemente, e tambem juntos, introduziram a formalizacao de um algoritmo, definindo os limites do que pode ser computado, e um modelo puramente mecanico para a computacao. Tais topicos sao abordados no que atualmente chama-se Tese de Church-Turing, uma hipotese sobre a natureza de dispositivos mecanicos de calculo. Essa tese define que qualquer calculo possivel pode ser realizado por um algoritmo sendo executado em um computador, desde que haja tempo e armazenamento suficiente para tal. Turing tambem incluiu na tese uma descricao da Maquina de Turing, que possui uma fita de tamanho infinito e um cabecote para leitura e escrita que move-se pela fita. Devido ao seu carater infinito, tal maquina nao pode ser construida, mas tal modelo pode simular a computacao de qualquer algoritmo executado em um computador moderno. Turing e bastante importante para a ciencia da computacao, tanto que seu nome e usado para o Turing Award e o teste de Turing. Ele contribuiu para as quebras de codigo da Gra-Bretanha na Segunda Guerra Mundial, e continuou a projetar computadores e programas de computador pela decada de 1940; cometeu suicidio em 1954.Alan Turing Alan Mathison Turing nasceu em 23 de junho de 1912 em Londres, filho de um oficial britanico, Julius Mathison e Ethel Sara Turing. Seu interesse pela ciencia comecou cedo, logo que aprendeu a ler e escrever, distraia-se fatorando numeros de hinos religiosos e desenhando bicicletas anfibias. A maior parte do seu trabalho foi desenvolvido no servico 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 computacao, Em 1928, Alan comecou 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 nao teve tempo, durante anos trocou correspondencias com a mae de Morcom a respeito das ideias do amigo e se maravilhou com a possibilidade de resolver problemas com a teoria mecanica quantica.Chegou inclusive a escrever sobre a possibilidade do espirito sobreviver apos 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 area da computacao. Sua preocupacao era saber o que efetivamente a computacao poderia fazer. As respostas vieram sob a forma teorica, de uma maquina conhecida como Turing Universal Machine, que possibilitava calcular qualquer numero e funcao, de acordo com instrucoes apropriadas. Quando a II Guerra Mundial eclodiu, Turing foi trabalhar no Departamento de Comunicacoes da Gran Bretanha (Government Code and Cypher School) em Buckinghamshire, com o intuito de quebrar o codigo das comunicacoes alemas, produzido por um tipo de computador chamado Enigma. Este codigo era constantemente trocado, obrigando os inimigos a tentar decodifica-lo correndo contra o relogio. Turing e seus colegas cientistas trabalharam num sistema que foi chamado de Colossus, um enorme emaranhado de servo-motores e metal, considerado um precursor