20세기 초에 가장 위대한 수학자 가운데 한 사람으로손꼽히는 독일 수학자 다비트 힐베르트 David Hilbert는 ‘결정 가능성 문제decision problem‘를 세상에 던졌다. 쉽게 말해, 임의의 어떠한 명제라도 그 명제가 참인지 거짓인지 판별하는 방법이 무조건 존재하는지를 묻는 문제였는데, 수학자들은 인류가 아직 완벽하게 발견하지 못했을 뿐이지그런 방법이 당연히 있을 것이라고 기대하고 있었다. 하지만 앨런 튜링은 모두의 예상을 뒤엎고 그러한 판별 방법이존재하지 않는다는 것을 증명했다.