Uma breve Historia da Computação (parte II)

[parte 1] O que era um algoritmo? Interessava associar à ideia intuitiva,

Um algoritmo (ou procedimento efectivo), é um conjunto de regras bem definidas, que nos informa, de momento a momento, o que se deve fazer.

uma precisa definição matemática (apesar de não ser óbvio que fosse possível descobrir um conceito formal equivalente a esta definição intuitiva). O problema desta explicação é que está baseada na capacidade do executor de interpretar correctamente as regras. Um observador incapaz poderia não entender a explicação ou, por outro lado, um observador demasiado capaz (ou totalmente fora do contexto) poderia induzir efeitos secundários não previstos por quem a determinou. Uma melhor forma para definir um algoritmo, para além de fornecer o conjunto das regras, seria dar os detalhes do mecanismo de interpretação dessas mesmas regras. Assim, um algoritmo passaria a ser:

a) uma linguagem que introduz a sintaxe e a gramática das regras,
b) um mecanismo de interpretação dessa linguagem,
c) um conjunto de regras respeitando as restrições estabelecidas em a).

Durante um curso em Cambridge, Alan Turing ouviu falar do Entscheidungsproblem e ao pensar nele considerou que era necessário modelar o processo pelo qual o matemático atinge a prova de uma dada conjectura. Assim, tomou a expressão ‘processo mecânico’ usada por Hilbert figurativamente, no sentido literal. Em 1936, apresentou o que é hoje conhecido por Máquina de Turing, um formalismo que não tendo um cariz essencialmente matemático, era uma máquina no sentido intuitivo do termo. Possuía um sistema de controle que determinava o comportamento da máquina, uma fita onde armazenava informação e uma cabeça de leitura/escrita.

Com esta estranha máquina, Turing conseguiu responder à questão deixada aberta por Gödel: seria possível saber algoritmicamente se uma proposição arbitrária é indecidível num dado sistema? A resposta de Turing deu o golpe final no programa de Hilbert: não! [cont.]