O
Programa de Hilbert foi uma proposta, feita em 1921 pelo matemático alemão
David Hilbert, de reformular as bases da
matemática de forma rigorosa, partindo da
aritmética. Segundo ele, toda a matemática poderia ser reduzida a um número finito de
axiomas consistentes. Assim, qualquer proposição da matemática poderia ser provada dentro desse sistema (e o sistema seria dito completo).
Em 1931, o matemático
Kurt Gödel provou, através do seu
Teorema da incompletude, que esta tarefa era impossível. No teorema, Gödel mostra que um sistema axiomático consistente não pode provar sua própria consistência. Assim, se um sistema axiomático consegue provar sua própria consistência, ele só pode ser inconsistente. Além disso, em sistemas com o poder de definir os números naturais (como o que Hilbert idealizou), sempre há proposições (chamadas de
indecidíveis) que não podem ser provadas dentro do sistema (portanto o sistema é incompleto). Desta forma, o sistema não pode ser simultaneamente completo e consistente, e a exigência hilbertiana de completude e consistência não pode ser colocada em prática.
Gödel deixou em aberto a possibilidade de existir um método geral para determinar se uma dada proposição é decidível. Em 1936, entretanto, o matemático
Alan Turing provou que tal método não pode existir.