컴퓨터과학이 여는 세계_3. 괴델의 불완전성 정리

3. 괴델의 불완전성 정리

1.5 괴델의 불완전성 정리와 튜링의 증명

[ 책 p.27~31 ]

 하지만 20세기 수학자들의 원대한 꿈은 1931년, 3년만에 쿠르트 괴델이라는 젊은 수학자에 좌절된다. 그는 다음과 같이 말했다. 

진리임에도 증명될 수 없는 수학적 명제가 존재한다. 

 그는 기계적인 방식만으로는 참인지 거짓인지 판결할 수 없는 명제가 항상 존재한다고 말했다. 즉, 힐베르트가 주장한 "기계적인 방식으로 모든 명제를 만들어내는 것"은 불가능하다는 것이었다. 

 조금 수학적으로 들어간다면 다비트 힐베르트는 집합론의 공리를 제안했지만, 버트런드 러셀이 러셀의 역리를 발표하며 흔들리게 되고, 쿠르트 괴델에 의해 완전히 좌절되고 만다. 이는 수학들에게 수학기초론의 근본적인 인식에 동의하게 되는 계기를 마련해주어 초기 수리논리학의 역사를 안정시켰다.  괴델의 정리는 후에 분석철학, 인지과학, 언어학, 논리학, 코딩이론, 등 폭 높은 학문에 영향을 미치게 되었다. 

 이러한 정리를 1936년 5월 28일, 앨런 튜링은 보다 직관적인 방식으로 제증명하였다. 그의 논문의 제목은 "On Numbers, with an Application to the Entscheidungsproblems(계산 가능한 수에 대해서, 수리명제 자동판결 문제를 응용하면서"이다. 그는 기계적인 방식 자체를 정의를 내려 직관적으로 문제를 풀어냈다. 

컴퓨터과학이 여는 세계_저자 이광근