컴퓨터과학이 여는 세계_1.5 괴델의 불완전성 정리와 튜링의 증명_이광근

강좌 동영상

 1931년 괴델에 의해서 '기계적인 방식만으론 사실인지 판정할 수 없는 그런 명제가 존재한다'라는 괴델의 불완성 정리가 증명이 되었다. 당시 수학학계에선 이 사실이 쓰여진 논문에 대해서 엄청난 파장이 일어났다.

 이후, 비슷한 시기에 청년 튜링이 막스 뉴먼 이라는 교사에게 미국으로 유학가기 전에 괴델의 증명 강의를 듣게 되었다.

[사진 출처: 위키피디아]

 이것을 듣고 튜링은 새로 생긴 취미인 달리기를 한 뒤 풀밭에 누워 갑자기 한 생각이 떠올라 논문을 작성하게 된다. 논문의 제목은 『On Computable Numbers, with an Application to the Entscheidungsproblems(계산 가능한 수에 대해서, 구리명제 자동판별 문제에 응용하면서)』

 이 논문은 괴델의 정리를 다른 방법으로 증명한 것이다. 논문은 막스 뉴먼에게 제출했고 막스 뉴먼은 런던 수리학회 논문지에 넣어주며 튜링에게 프리스던 처칠교수를 추천해 주었다.