괴델의 아이디어에 대해 여러분 스스로 곰곰이 생각해 보기 바랍니다. 저는 꽤 머리가 아팠습니다. 괴델의 증명을 일부 읽었더니 머리가 더 아팠습니다. 솔직히 말해서 제가 그 증명의 일부분이라도 이해하고 있다면, 그것은 마치 우리 집 치와와가 아침마다 해가 뜨는 원리를 이해하는 수준일 것입니다.
불완전성 정리로 형식주의 수학 체계에 모순이 있을 수 있다고 증명한 괴델은 이어서 힐베르트의 두 번째 도전 과제14도 무너뜨립니다. 그는 어떤 형식적인 체계 안에서는 스스로 그 체계가 모순이 없음을 증명할 수 없다는 것을 밝혔습니다. 즉, 수학 체계 내부에서는 어떤 명제가 참이면서 동시에 거짓인 경우가 있는지 없는지조차도 알 수 없다는 것입니다.15
힐베르트가 제시한 마지막 과제인 결정 가능성 문제는 5년 후 앨론조 처치(Alonzo Church)와 앨런 튜링(Alan Turing)에 의해 무너집니다. 이 사건은 조금 뒤에 자세히 살펴봅니다.
v 역자노트 결정 가능성 문제
결정 가능성 문제(decidability problem)란 모든 수학적 명제에 대해 그것이 참인지 거짓인지를 판단해 주는 명확하고 기계적인 절차(알고리즘)가 존재하는지 묻는 문제입니다. 다시 말해 어떤 수학적 질문이 주어졌을 때, 그 답이 ‘참’인지 ‘거짓’인지를 자동으로 판별해 주는 방법이 항상 존재할 수 있는지 탐구하는 것입니다. 힐베르트는 이런 보편적 판별 절차의 존재를 믿었지만, 이후 앨론조 처치와 앨런 튜링은 그것이 불가능함을 증명했습니다.