괴델의 불완전성 정리, 그 진짜 의미는 무엇일까

수학의 '완벽함'을 무너뜨린 사건

혹시 "수학은 절대적인 진리"라는 말을 들어보셨나요. 1+1=2처럼 한 번 증명된 건 영원히 참이고, 수학 안에서는 모든 것이 명확하게 참 또는 거짓으로 갈린다는 믿음이죠. 그런데 1931년, 25살의 오스트리아 수학자 쿠르트 괴델이 이 믿음을 송두리째 뒤흔든 논문을 발표했어요. 바로 불완전성 정리(Incompleteness Theorems) 예요. 이게 발표된 지 거의 100년이 다 되어가는데, 아직도 사람들이 그 의미를 두고 갑론을박을 벌이고 있거든요. Quanta Magazine이 이 정리의 진짜 의미가 무엇인지, 그리고 흔히 퍼져 있는 오해는 무엇인지 정리한 글을 실었어요.

괴델 이전의 수학계는 자신감에 가득 차 있었어요. 다비드 힐베르트라는 거장이 "수학의 모든 진리를 유한한 공리(axiom, 증명 없이 받아들이는 출발점이 되는 명제예요)에서 출발해 기계적으로 증명할 수 있다"는 프로그램을 추진하고 있었거든요. 이게 성공했다면 수학은 일종의 거대한 자판기가 됐을 거예요. 질문을 넣으면 답이 톡 튀어나오는. 그런데 괴델이 이걸 "불가능하다"고 증명해버린 거예요.

두 개의 정리, 무엇을 말하는가

괴델의 정리는 두 개로 이루어져 있어요. 첫 번째 정리는 이렇게 말해요. "산술(arithmetic, 자연수와 더하기 곱하기 같은 기본 연산을 다루는 수학이에요)을 포함하는 어떤 일관된 형식 체계에도, 그 체계 안에서는 증명할 수도 반증할 수도 없는 참인 명제가 존재한다." 말이 좀 어렵죠. 쉽게 풀면 이래요. 아무리 잘 만든 수학 시스템이라도, 그 시스템 안에서 "이건 참인데 증명은 못 해"라는 명제가 반드시 있다는 뜻이에요.

괴델이 이걸 어떻게 증명했냐면, 정말 천재적인 방법을 썼어요. 수학 명제 하나하나에 고유한 번호를 매기는 거예요. 이걸 괴델 수(Gödel numbering) 라고 해요. 그러면 "이 명제는 증명될 수 없다"라는 자기 자신을 가리키는 문장을 수학 공식으로 표현할 수 있게 되거든요. 이게 "이 문장은 거짓이다"라는 거짓말쟁이 역설의 수학판이에요. 만약 이 문장이 증명 가능하다면 거짓을 증명한 게 되니까 시스템이 모순이고, 증명 불가능하다면 이 문장은 참인데 시스템 안에서는 증명할 수 없는 거죠. 즉, 어느 쪽이든 '완전하면서 모순 없는 시스템'은 불가능하다는 거예요.

두 번째 정리는 더 충격적이에요. "수학 시스템은 자기 자신의 무모순성(consistency, 모순이 없다는 것)을 자기 안에서 증명할 수 없다." 즉, 수학이 정말 안전하고 모순이 없다는 걸 수학 스스로는 증명 못 한다는 거예요. 마치 "내 말은 다 진실이야"라고 자기 입으로 말해봤자 신뢰의 근거가 안 되는 것과 비슷해요.

흔한 오해들

Quanta의 기사가 특히 강조하는 건 이 정리에 대한 잘못된 해석이에요. 가장 흔한 오해는 "괴델이 수학에 한계가 있다는 걸 증명했다"거나 "AI는 인간을 따라잡을 수 없다는 걸 증명했다"는 식의 확장이에요. 로저 펜로즈 같은 유명 물리학자조차 이 정리를 인용해서 "인간의 마음은 알고리즘으로 환원될 수 없다"고 주장하기도 했죠.

그런데 수학자들 사이에서는 이런 해석이 과장이라는 의견이 많아요. 괴델의 정리가 적용되는 건 매우 특정한 조건을 만족하는 형식 체계예요. 자연수 산술을 포함할 만큼 표현력이 있고, 일관되며, 공리들이 알고리즘적으로 나열 가능한 시스템이요. 일상에서 우리가 쓰는 대부분의 수학은 이 정리에 의해 "증명 불가능한 참"의 존재가 보장되지만, 그게 실제 수학 연구를 멈추게 하지는 않아요. 오히려 수학자들은 그동안 잘만 일해왔거든요.

또 다른 오해는 "괴델 문장은 인공적이고 실용적 의미가 없다"는 거였는데, 1977년 패리스-해링턴 정리가 이걸 깼어요. 자연스럽고 의미 있는 수학 명제 중에도 페아노 산술 안에서는 증명 불가능한 게 있다는 걸 보여줬거든요.

컴퓨터 과학과의 연결

개발자 입장에서 흥미로운 건 괴델의 정리가 컴퓨터 과학의 뿌리와 직접 닿아 있다는 점이에요. 앨런 튜링이 5년 뒤 발표한 "정지 문제(Halting Problem, 어떤 프로그램이 영원히 돌아갈지 멈출지를 미리 알 수 있냐는 문제예요)"의 해결 불가능성 증명은 괴델의 아이디어를 직접 이어받은 거거든요. 튜링은 사실상 "증명"을 "계산"으로 바꿔서 같은 결론을 끌어냈어요. 어떤 알고리즘으로도 임의의 프로그램이 멈출지 여부를 판별할 수 없다는 거죠.

이게 추상적으로 보이지만, 실무에서도 의미가 있어요. 정적 분석 도구가 모든 버그를 자동으로 잡을 수 없는 이유, 컴파일러가 모든 무한 루프를 미리 경고할 수 없는 이유, 형식 검증(formal verification)에 본질적 한계가 있는 이유의 뿌리가 여기 있거든요.

한국 개발자에게 주는 시사점

사실 매일 코드 짜는 입장에서 괴델 정리는 멀게 느껴질 수 있어요. 그런데 두 가지 정도는 생각해볼 만해요. 첫째, "모든 걸 자동화할 수 있다"는 환상에 대한 경계심이에요. AI 코드 생성, 자동 증명, 자동 테스트가 발전하더라도 어떤 문제들은 본질적으로 자동으로 풀 수 없다는 걸 알면, 도구의 한계를 더 잘 이해할 수 있어요. 둘째, 타입 시스템이나 형식 검증 도구를 쓸 때, 이 도구들이 왜 항상 "보수적"으로 동작하는지 이해하는 데 도움이 돼요. Rust 컴파일러가 안전한 코드도 가끔 거부하는 이유, TypeScript의 타입 추론에 한계가 있는 이유가 다 이런 깊은 수학적 결과와 연결돼 있거든요.