결정문제'결정 문제'란 모든 수학적 명제에 대해 참인지 거짓인지를 유한 시간내에 판별할 수 있는 일반적인 절차, 즉 알고리즘이 존재하는지를 묻는 것이었습니다. 이 문제를 처음 제기한 힐베르트는 이러한 알고리즘이 존재할 것이라 기대했습니다. 1920년대에는 수학적 엄밀성에 대한 열정이 고조되어 있었고, 수학적 진리를 탐구하는 강력한 체계들이 속속 등장하고 있었기 때문입니다. 힐베르트는 수학이 충분히 강력하다면, 모든 문제에 대해 확실한 답을 구할 수 있을 것이라 보았던 것입니다.하지만 10년이 채 지나지 않은 1936년, 영국의 젊은 수학자 앨런 튜링은 '계산 가능한 수와 결정 문제에 관한 적용에 관하여'라는 논문을 통해 모든 수학적 명제를 증명하거나 반증할 수 있는 하나의 보편적인 절차, 즉 알고리즘이 ..