--
Em 1900, no Segundo Congresso Internacional de Matemática, realizado em Paris, David Hilbert propôs uma lista de problemas de 10 problemas de grande envergadura, cuja solução desafiaria futuras gerações de matemáticos. Vários destes problemas estavam relacionados com questões fundamentais da matemática e sobre a verdadeira natureza da matemática.
Hilbert era um grande defensor de uma corrente matemática chamada de formalismo. Hilbert queria organizar e fundamentar a matemática de forma sólida e concreta. Dessa maneira, a matemática poderia ser entendida como um jogo quanto à forma. Na verdade, para conseguir uma axiomatização ou formalização completa para a matemática precisava-se responder as seguintes matemática:
1. A matemática é completa, ou seja, todas as afirmações poderiam ser demonstradas através de um método formal.
2. A matemática é consistente, ou seja, nenhuma afirmação inválida poderia ser demonstrada.
3. A matemática é decídivel, ou seja, existe um método bem definido que possa ser aplicado a qualquer asserção matemática para demonstrar sua validade.
Gödel assombrou o mundo matemático demonstrando que a matemática era imcompleta. Gödel mostrou como codificar fórmulas como inteiros e como codificar demonstrações como inteiros de forma que tinha toda a aritmética codificada dentro do seu sistema. Seu sistema era tão expressivo que seria possível escrever fórmulas matemáticas com auto-referência.
Gödel construi em seu sistema asserções do tipo “Essa asserção não é demonstrável”. Dessa maneira, Gödel mostrou que a aritmética era incompleta. O problema da auto-referência era um problema bastante conhecido na matemática e originou vários paradoxos na matemática como o paradoxo do barbeiro (conhecido como paradoxo de Russell):
Se um barbeiro faz a barba de todos que não fazem a própria barba, então o barbeiro deve fazer a sua própria barba?
A auto-referência causou problemas na teoria dos conjuntos de Cantor permitindo a existência de conjuntos de todos os conjuntos e um conjunto formado por elementos cujos elementos não pertencem a si mesmo.
Gödel mostrou que a auto-referência surge em qualquer sistema formal que contenha pelo menos a aritmética deixando tal sistema formal incompleto. Mesmo a aritgmética, considerada a parte mais intuitiva da matemática, não estaria livre da auto-referência. Gödel demonstrou que a matemática não poderia ser demonstrada consistente dentro do seu próprio sistema.
A terceira questão sobre a decidibilidade da matemática ainda estava sem solução. Encontrar um método efetivo ou mecânico que pudesse ser aplicado a qualquer afirmação matemática e decidisse se a afirmação é valida ou não era um problema bastante difícil. O grande problema era definir a natureza de um método efetivo. Um método é dito efetivo quando:
1. M é expresso em termos de um número finito de instruções e cada instrução definida através de um número finito de símbolos.
2. M produz o resultado desejado em número finito de passos, quando executado sem erros.
3. M pode ser executado por um ser humano com papel e caneta ou por uma máquina
4. M não demanda um discernimento superior ou ingenuidade na parte do ser humano.
Um exemplo de um método efetivo é o teste da tabela verdade para descobrir se uma fórmula proposicional é uma tautologia. A pergunta era se a matemática era totalmente algorítmica. Mas a definição de método efetivo ou mecanizável ainda era bastante informal: que tipo de instruções podem ser executadas por máquinas , o que seria não assumir ingenuidade ou ainda não exigir um discernimento superior. Tudo isso ainda estava sem explicação até que Alan Turing propôs uma máquina chamada LCM (Logical Computer Machine) que ficou conhecida como Máquina de Turing. Este dispositivo formal foi concebido para ser um substituto formal para o predicado informal “o que pode ser calculado por meios de métodos efetivos”. A máquina de Turing era um dispositivo tão simples que a sua simples apresentação já era uma garantia da sua efetividade. O que assustou outros matemáticos é que outros modelos de computação propostos eram todos equivalentes a Máquina de Turing. Este fato motivou a preposição da famosa Tese de Church-Turing:
Toda função é efetivamente computável somente se for Turing computável.
Em certo sentido, a máquina de Turing capturaria a noção informal de procedimento efetivo ou computável.
