Ciências da computação de Alan Turing: Uma viagem pessoal

Abstract

[Excerto] O moderno cientista da computação, interessado na correção dos seus artefatos, navega num terreno construído sobre as respostas a algumas questões fundamentais. Primeiro ele/ela pode perguntar “O que é demonstrável, refutável ou decidível?”, imediatamente seguido de “O que é inconsistente e o que pode ser validado?”. Mais ainda, é seguro dizer que, quando comparado com o âmbito do artefacto, ele/ela terá sobretudo que basear-se em respostas a outra questão “o que é que se pode aprender?”. Finalmente, quando o interesse se estende à segurança do artefacto e à privacidade do utilizador, o cenário é complicado por questões adicionais, nomeadamente “O que é aleatório? O que é obscuro e à prova de fuga, no sentido da teoria da informação?”. Através de toda a paisagem da Ciência e Engenharia da Computação (CEC) podem detetar-se as pegadas de Turing, algumas desmaiadas, mas outras muito claras e incisivas. Nesta breve monografia tentarei delinear algumas dessas pegadas, escolhendo aquelas que eu acredito serem as mais significativas para a minha visão da CEC. A questão que mais interessou Turing não foi nenhuma das anteriores mas antes O que é computável e, de entre essas ‘coisas computáveis’, o que é fazível? É bem conhecido o papel de Turing (Turing 1936; Soare 2016) na construção de uma resposta pelo menos à primeira parte da questão. A fazibilidade das computações veio mais tarde e é o domínio da Teoria da Complexidade; a sua importância e o papel de Turing foram reconhecidos há algum tempo (Hartmanis 1994). Algumas décadas antes, o início do Séc. XX viu o florescimento de novos fundamentos para o pensamento matemático: a axiomatização dos conjuntos de Zermelo-Fraenkel, construtivismo & intuicionismo e os problemas de decisão de Hilbert são alguns dos programas2 desta era; para além do seu impacto na matemática como um todo, estes programas tiveram um efeito direto nos fundamentos da CEC; de facto, podemos dizer que estes “são” três quartos dos fundamentos da CEC, o restante quarto sendo, obviamente, a computabilidade. [...]