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.