괴델 불완전성 정리, 수학으로도 증명할 수 없는 것이 있다는 걸 증명하다

옛날 수학자들은 수학이 완벽한 답안지라고 진심으로 믿었다

시험 문제를 풀 때, 수학 문제에는 반드시 정답이 있다고 배웠죠? 1+1은 2이고, 삼각형 내각의 합은 180도예요. 틀릴 일이 없어요. 1900년대 초, 세계 최고의 수학자들도 똑같이 생각했어요. "수학은 우주에서 가장 완벽한 건물이다. 어떤 질문이든 던지면 참인지 거짓인지 반드시 답할 수 있다." 이렇게 믿었거든요.

특히 다비트 힐베르트라는 독일의 슈퍼스타 수학자가 있었어요. 이 사람은 전 세계 수학자들 앞에서 이렇게 선언했어요. "우리가 모르는 건 아직 안 풀었을 뿐이지, 수학으로 못 푸는 문제는 없다!" 마치 레고 블록으로 성을 쌓듯이, 기본 규칙(공리라고 해요)을 벽돌처럼 하나씩 쌓으면 모든 진리를 증명할 수 있다고 확신한 거예요.

수학자들은 이 거대한 레고 성을 더 높이, 더 단단하게 쌓는 데 인생을 걸었어요. 아무도 이 성에 금이 갈 수 있다고는 상상조차 못 했죠. 그런데 1931년, 오스트리아 빈이라는 도시에서 겨우 스물다섯 살짜리 청년 하나가 손을 들었어요.

스물다섯 살 청년이 '이 퍼즐에는 정답이 없는 문제가 반드시 숨어 있다'는 걸 수학으로 증명해버렸다

그 청년의 이름은 쿠르트 괴델이에요. 안경을 쓴 조용한 사람이었는데, 머릿속에서는 엄청난 폭풍이 몰아치고 있었어요. 괴델은 기발한 방법을 떠올렸어요. 수학 문장 하나하나에 고유한 번호를 매긴 거예요. 마치 유튜브 영상마다 고유한 URL이 있는 것처럼요. 이걸 '괴델 수'라고 불러요.

이 번호 시스템을 이용해서, 괴델은 아주 이상한 문장을 하나 만들었어요. 쉽게 풀어 쓰면 이런 뜻이에요. "이 문장은 증명할 수 없다." 잠깐, 이게 뭔가 이상하지 않나요? 만약 이 문장이 거짓이면, 증명할 수 있다는 뜻인데, 그러면 거짓인 걸 증명한 게 되니까 수학이 고장 나요. 반대로 이 문장이 참이면? 참인데 증명할 수 없는 문장이 수학 안에 존재한다는 거예요!

이걸 '불완전성 정리'라고 해요. 쉽게 말하면 이거예요. 아무리 규칙을 완벽하게 정해도, 그 규칙 안에서는 절대 증명할 수 없는 참인 문장이 반드시 하나는 숨어 있다는 거예요. 1000피스 퍼즐을 999개까지 맞췄는데, 마지막 한 조각이 아예 만들어지지 않은 것과 비슷해요. 힐베르트가 쌓던 완벽한 성? 그 성 안에는 절대 채울 수 없는 빈 방이 있을 수밖에 없다는 게 수학적으로 증명된 거예요.

완벽할 줄 알았던 수학의 벽에 금이 가자, 과학과 컴퓨터의 역사가 통째로 바뀌었다

수학의 성벽에 금이 가자, 오히려 그 틈 사이로 놀라운 빛이 쏟아졌어요. 괴델의 발견은 "수학에도 한계가 있다"는 슬픈 이야기가 아니었어요. 오히려 "그 한계가 뭔지 정확히 알게 됐으니, 새로운 길을 찾자!"라는 시작 신호였거든요.

괴델의 아이디어에 자극받은 앨런 튜링이라는 영국 수학자가 "기계가 계산할 수 있는 것과 없는 것의 경계"를 연구하기 시작했어요. 그리고 그 연구에서 탄생한 게 바로 '튜링 머신'이라는 개념이에요. 이게 뭐냐고요? 오늘날 컴퓨터의 할아버지예요! 여러분이 지금 쓰는 스마트폰, 노트북, 게임기 전부 튜링 머신의 후손인 셈이에요.

또 괴델의 증명 방식 자체가 혁명이었어요. 수학 문장에 번호를 매기는 아이디어는 나중에 컴퓨터가 데이터를 0과 1로 바꿔서 저장하는 원리와 통하거든요. 완벽한 성이 무너진 게 아니라, 무너진 자리에서 컴퓨터와 인공지능의 씨앗이 자라난 거예요. 수학이 한계를 인정한 바로 그날, 기술 문명의 새 장이 열린 셈이죠.

네가 쓰는 컴퓨터가 가끔 멈추는 이유도 사실 이 발견과 연결되어 있다

컴퓨터로 게임하거나 과제를 할 때, 갑자기 로딩 화면이 빙글빙글 돌면서 멈춘 적 있죠? 이른바 '무한 로딩'이요. 사실 이게 괴델의 불완전성 정리와 연결돼 있어요. 튜링은 괴델의 발견에서 힌트를 얻어, "어떤 프로그램이 언제 끝나고 언제 영원히 돌지 미리 알아낼 수 있는 완벽한 방법은 없다"는 걸 증명했어요. 이걸 '정지 문제'라고 해요.

쉽게 말하면 이거예요. 컴퓨터에게 "이 프로그램이 멈출지 안 멈출지 미리 판단해 줘"라고 시켜도, 컴퓨터 자체가 그걸 완벽하게 알아낼 수 없다는 거예요. 수학에 증명 불가능한 진실이 숨어 있듯이, 컴퓨터에도 절대 미리 답할 수 없는 질문이 있는 거죠.

괴델이 없었다면 이 사실을 몰랐을 거예요. 그리고 그 한계를 알았기 때문에 프로그래머들은 "완벽한 프로그램"을 만들겠다는 헛된 꿈 대신, 현실적이고 똑똑한 해결책을 만드는 데 집중할 수 있었어요. 다음에 컴퓨터가 멈춰서 짜증날 때, 한번 떠올려 보세요. "아, 이건 약 100년 전에 조용한 청년 괴델이 발견한 우주의 규칙 때문이구나." 좀 덜 짜증나지 않나요?