모든 악의 근원 : 불완전성의 원리

불완전성의 원리는 쿠르트 괴델이 증명한 원리이다.

쿠르트 괴델이 불완전성을 증명한 과정은 BBC에서 제작한 "Dangerous Knowledge" 라는 제목의 다큐멘터리에 잘 나와 있다.

게오르그 칸토어는 미지의 대상이던 무한에 관한 이론을 정립하고자 노력한 수학자였다. 그는 무한과 무한과의 관계를 정립하는 과정에서 연속체 가설을 증명하고자 하였다. 이전까지는 수학이 논리적으로 완전하다는 의식이 팽배해 있었는데, 칸토어가 연속체 가설을 내놓은 이후부터 수학에는 논리적 완전성을 증명하기 난해한(당대까지는) 문제가 있음을 알게 되었다. 즉, 단편적인 논리적 사실은 증명이 되지만 전체 체계를 놓고 보면 완전함이 증명되지 않는 것이다.

이후 많은 수학자들이 어떤 논리적인 체계가 완벽하게 증명되기를 기대하면서 연구를 진행했는데(이 기대는 수천년간 수학의 논리적인 완전성을 믿어왔던 수많은 수학자들의 바램이기도 했다) 쿠르트 괴델도 그 중 한 사람이다.

하지만 수많은 수학자들의 바램과는 달리 괴델은 "불완전성의 원리"로 불리우는 반대 증명을 해낸다.

불완전성의 원리

정리1. 자연수의 사칙연산을 포함하는 어떠한 공리계도 무모순인 동시에 완전할 수 없다. 어떤 체계가 무모순이라면, 그 체계에서는 참이면서도 증명할 수 없는 명제가 존재한다.

정리2. 자연수의 사칙연산을 포함하는 어떠한 공리계가 무모순일 경우, 그 공리계는 자기 자신의 무모순에 대한 정리를 포함할 수 없다.

불완전성의 원리를 해석해보면 다음과 같다. (실제가 아닌) 순수 논리의 세계에서 어떤 논리 체계가 완전하게 참과 거짓으로 증명될 수 있느냐는 물음에 불완전성의 원리는 "그럴 수 없다"는 답을 내놓은 것이다. 특히 이 과정에서 괴델은 "스스로 증명(계산)하는 논리적 체계"를 고안해 내고 이를 통해 불완전성 원리를 증명해 냈는데, 이 체계가 우리가 알고 있는 "알고리즘"의 시초이다. 알고리즘과 불완전성의 원리가 내포하는 관계를 명확히 해보면 다음과 같다.

대응관계

알고리즘 : 스스로 계산하는 논리적 체계

불완전성의 원리 : 알고리즘은 스스로 논리적으로 완전함을 증명할 수 없다.

컴퓨터, 특히 소프트웨어의 시작을 알리는 이 대응 관계는 비참하게도 커다른 악과 함께 탄생한 셈이다. 어떤 알고리즘도 스스로 완전하다고 증명할 수 없다. "스스로 할 수 없다면 다른 알고리즘으로 증명하면 되지 않을까?" 하는 생각도 금방 깨지게 된다. 다른 알고리즘의 완전함을 증명할 방법이 없기 때문이다. 그래서 소프트웨어 영역에는 "알고리즘은 자기 스스로 논리적 완결성을 증명할 수 없다"는 명제가 있는 것이다.

만약 불완전성이 없다면, 즉 논리적 체계가 스스로 완전함을 증명할 수 있다면 소프트웨어가 의도한 대로 동작하는지를 인간이 증명해야 할 필요가 없었을 것이다. 그렇다면 인간은 어떻게든 스스로 증명할 수 있는 알고리즘을 구현만 한다면 그 후에는 오류나 버그가 나오지 않는다는 것을 확신할 수 있게 될테고, 현대 개발자들이 가지고 있는 불안감이 모두 해결될 것이다. 반대로 이야기 하자면, 불완전성의 원리 때문에 자동으로 소프트웨어의 완전함을 증명할 방법이 없어지고, 소프트웨어의 완전함을 관리할 수 있는 도구는 오직 인간의 두뇌 밖에 없다는 말이 된다. 이것이 악의 근원이 아니면 무엇이겠는가?

불완전성과 소프트웨어

불완전성의 원리는 이후 소프트웨어의 발전 과정과 현대에 개발된 소프트웨어 기술에 대한 미래, 그리고 소프트웨어가 가진 본질적인 특성을 규정하게 되었다. 이 부분은 추후 포스팅을 통해서 계속 다룰 예정이다.

한가지 명료하게 이야기 해 두자면, 불완전성의 원리는 소프트웨어의 탄생이자 성격의 규정자라는 사실이다. 우리는 소프트웨어 및 프로그래밍, 소프트웨어 설계나 개발 방법론들을 접하는데, 이들은 모두 불완전성이라는 악을 다스리는 기술이다. 그리고 우리가 프로그래밍을 공부하면서 받아 들이는 수많은 격언, 설계 원칙, 변수나 함수의 명명 규칙

과 같은 사소한 규정까지도 사실 불완전성에 기인하는 것이다. 

이미 소프트웨어로 생계를 꾸려 나가기로 결정한 개인이나 소프트웨어를 이용해서 돈을 벌고자 하는 기업에게 한마디 하자면 다음과 같다.

"You have a big problem!"