관리 메뉴

ScienceBooks

13편 컴퓨터 증명은 반칙?? 본문

(연재) 나는 생각한다, 고로 수학한다

13편 컴퓨터 증명은 반칙??

Editor! 2020. 9. 9. 16:41

사회 생물학의 창시자이자 통섭의 과학자인 하버드 대학교 교수 에드워드 윌슨은 과학이 과“인간의 뇌가 만든 독특하면서 지극히 인간적인 산물이다.”라고 강조했죠. 칼 세이건의 부인이자 「코스모스」 프로젝트의 현재 총 책임자인 앤 드루얀은 과학이 “코스모스를 이해하고 코스모스로 돌아갈 길”이라고 얘기했죠. 많은 사람들이 과학은, 그리고 수학은 인간을 인간답게 만들고, 지구 인류를 은하계의 시민으로 만들어 줄 인간만의 것이라고 생각해 왔죠. 하지만 수학의 최전선에서 과학과 수학인 인간만의 것이라는 인류의 자부심을 송두리째 흔드는 일들이 벌어지고 있습니다. 최근 대화형 인공 지능 GPT-3가 화제죠. 수학 난제와 물리학 이론을 해결하는 인공 지능 등장이 멀지 않았을까요? 인류는 코페르니쿠스 이후 우주의 중심에서 쫓겨났고, 다윈 이후 만물의 영장 자리에서 물러났습니다. 인공 지능 이후 인류는 수학과 과학의 주인이라는 자리에서도 쫓겨날지도 모릅니다. 그 무시무시한 현장을 고호관의 수요 수학 에세이가 취재해 봤습니다.


고호관의 수요 수학 에세이 13편

나는 생각한다, 고로 수학한다

 

컴퓨터 증명은 반칙??

 

 

네 자리 비밀 번호로 열리는 문이 있다고 하자. 스마트폰이라고 해도 상관없다. 어쨌든 비밀 번호를 알아내서 열어 보고 싶다고 하자. 비밀 번호를 어떻게 알아낼 수 있을까? 가능한 한 논리적으로 추측하는 수밖에 없다.

 

생일이나 다른 기념일을 시도해 보거나 좋아하는 숫자를 조합해 볼 수 있을 것이다. 비밀 번호를 정한 사람이 게으른 성격이라면, 0000이나 1234 같은 단순한 번호를 시험해 볼 수도 있겠다. 아니면, 키패드 위에서 일직선이 되는 수라거나. 물론 대부분 잘 안 될 것이다. 기껏해야 네 자리 비밀 번호라고 해도 알아맞히는 건 쉽지 않다.

 

하지만 끈질기기만 하다면 알아낼 방법이 있다. 0000에서 9999까지 일일이 모두 입력해 보는 것이다. 경우의 수는 1만 개. 운이 좋다면 몇 번 안 하고도 알아낼 수 있고, 운이 나쁘면 1만 번을 다 입력해야 알아낼 수도 있다. 생각만 해도 지루한 일이다. 그런데 만약 컴퓨터를 이용해 빠른 속도로 비밀 번호를 넣어 볼 수만 있다면, 걸리는 시간을 대폭 줄일 수 있다. 그러면 해 볼 만하지 않을까?

 

그렇게 해서 비밀 번호를 알아냈다. 한 자리에 들어갈 수 있는 숫자는 각각 10개씩이니 순서대로 1만 번을 시도하면 된다는 건 내가 생각해 냈지만, 실제로 입력은 컴퓨터가 했다. 이때 과연 비밀 번호를 ‘내’가 알아냈다고 할 수 있을까? 조악한 비유지만, 이번 글에서 할 이야기와 관련이 있는 예시다.

 

우주의 수수께끼를 풀 비밀 번호를 알아내는 데 컴퓨터를 이용했다고 치자. 이때 과연 비밀 번호를 ‘내’가 알아냈다고 할 수 있을까?

 

90년 만에 풀린 문제

 

얼마 전, 켈러 추측(Keller's conjecture)이라는 문제가 해결되었다는 소식이 들려왔다. 켈러 추측은 1930년에 독일 수학자 오트하인리히 켈러(Ott-Heinrich Keller, 1906∼1990년)가 제시한 기하학 문제로, 90년 동안 미해결로 남아 있었다. 문제를 간략하게 설명해 보자면, 이렇다. 2차원 평면을 정사각형 모양의 2차원 타일로 채운다고 하자. 그러면 적어도 타일 2개는 모서리를 접해야 한다. 이건 어렵지 않게 알 수 있다. 3차원 공간을 정육면체 모양의 3차원 입방체로 채우는 것도 비슷하다. 그런데 4차원, 5차원, …으로 차원을 높여 가도 계속 성립할까?

 

이후 독일 수학자 오스카르 페론(Oskar Perron, 1880∼1975년)이 6차원까지는 성립한다는 사실을 증명했다. 그리고 한동안 진전이 없다가 1992년이 되어서야 10차원일 때는 성립하지 않는다는 사실이 밝혀졌다. 어떤 차원에서 성립하지 않으면 그보다 높은 차원에서는 성립하지 않으므로 11차원 이상에서는 모두 성립하지 않았다. 그리고 10년 뒤에는 8차원 이상에서 성립하지 않는다는 사실도 밝혀졌다. 남은 건 7차원뿐이었다.

 

더 낮은 차원으로 나눌 수 있었던 8차원과 달리 7은 소수기 때문에 7차원을 해결하는 건 어려웠다. 수학자들은 이 문제를 그래프로 변형해 푸는데, 7차원의 경우 가능한 조합을 일일이 확인해야 했다. 여기에 필요한 변수는 무려 3만 9000개에 달하는데, 각 변수는 0 또는 1이 될 수 있으므로 2의 3만 9000제곱 가지의 조합이 생길 수 있다. 컴퓨터로 계산해도 벅찬 양이다.

 

연구진은 가능한 한 효율적인 방법을 찾아 컴퓨터가 계산해야 하는 경우의 수를 10억 가지 정도로 줄였다. 그 결과는 ‘그렇다.’였다. 켈러 추측은 7차원에서 참이었다. 7차원까지는 참이고, 8차원부터는 거짓. 90년 묵은 문제는 이렇게 컴퓨터의 도움을 받아 마침내 증명되었다.

 

 

 

2차원 켈러 그래프. 켈러 추측을 푸는 데 사용한다. 위키피디아에서.

 

컴퓨터로 해결한 난제들

 

컴퓨터를 이용해 증명한 최초의 난제는 4색 정리였다. 1852년 영국 수학자 프랜시스 구드리(Francis Guthrie, 1831∼1899년)는 영국의 지도를 색칠해 각 주를 구분하다가 떠올린 문제로, 서로 접해 있는 지역을 다른 색으로 칠해 구분하면서 지도 전체를 칠한다면 네 가지 색이면 충분할지도 모른다는 것이다. 굳이 수학자가 아니어도 이해할 수 있는 문제지만, 증명은 결코 쉽지 않았다.

 

세 가지 색으로는 가능하지 않다는 점은 금세 알 수 있다. 종이에 이리저리 선을 그려 보면 세 가지 색만 가지고서는 모든 영역이 구분되도록 칠할 수 없는 반례를 어렵지 않게 만들 수 있다. 이건 누구나 할 수 있는 일이니 궁금하다면, 한번 직접 해 보기를 권한다.

 

그런데 네 가지 색은 반례를 찾는 게 쉽지 않았다. 웬만한 지도는 네 가지 색으로 다 영역을 구분해 칠할 수 있었다. 그렇다면 모든 지도를 네 가지 색으로 칠하는 게 가능할까? 아무리 지도가 복잡해도 네 가지 색만 있으면 다 구분해서 칠할 수 있을까?

 

이 간단하면서도 복잡한 문제가 해결되기까지는 100년이 넘게 걸렸다. 그동안 여러 수학자가 도전했고, 일부는 증명했다고 발표했다가 나중에 오류로 판명 나기도 했다. 그사이에 다섯 가지 색만 있으면 지도를 다 칠할 수 있다는 사실은 밝혀졌다. 하나만, 색깔 하나만 더 줄이면 4색 정리가 증명되는 것이다.

 

 

4색 지도의 예. 위키피디아에서.

 

마침내 1976년 미국의 케네스 아펠(Kenneth Ira Appel, 1932∼2013년)과 볼프강 하켄(Wolfgang Haken, 1928년∼)이 컴퓨터를 이용해 4색 정리를 증명했다. 가능한 모든 지도의 모양을 1800여 개(나중에는 약 1500개)의 유형으로 분류한 뒤 1000시간이 넘게 컴퓨터로 하나하나 확인해 다섯 가지 색이 필요한 반례가 존재하지 않음을 밝힌 것이다.

 

케플러의 추측도 수백 년 만에 컴퓨터를 이용해 증명된 문제다. 독일의 천문학자이자 수학자인 요하네스 케플러(Johannes Kepler, 1571∼1630년)는 1611년에 3차원 공간 안에 구를 가장 많이 배열할 수 있는 방법을 추측했다. 케플러가 생각한 것은 바로 피라미드 모양으로 쌓는 것. 일단 구가 서로 맞닿도록 촘촘하게 배열한다. 그리고 구와 구 사이의 움푹 들어간 곳에 계속 구를 쌓아 올린다. 이것을 케플러 추측(Kepler conjecture)이라고 한다. 하지만 케플러는 자신의 추측을 증명하지 못했다.

 

 

케플러 추측을 그린 다이어그램. 위키피디아에서.

 

이 역시 문제 자체는 일반인도 이해할 수 있을 정도로 쉽지만, 증명은 결코 그렇지 않다는 사실이 드러났다. 무려 387년이나 지난 1998년에야 미국의 토머스 칼리스터 헤일스(Thomas Callister Hales, 1958년∼)가 컴퓨터를 이용해 증명했다.

 

커넥트 포(Connect Four)라는 보드게임도 한 사례다. (우리나라에서는 ‘입체 사목 게임’이라는 이름으로 알려져 있다.) 위에서 말을 떨어뜨려 가로, 세로, 대각선으로 4개가 일직선이 되도록 만들면 이기는 게임인데, 먼저 두는 사람이 무조건 이길 수 있는 방법이 이미 밝혀져 있다. 역시 컴퓨터를 이용해 경우의 수를 하나씩 따지는 방식으로 문제가 풀렸다.

 

 

컴퓨터로 한 증명은 진짜 증명인가?

 

컴퓨터를 이용한 증명은 여러 논란을 불러일으켰다. 그중 한 가지 문제는 컴퓨터가 만들어 낸 증명은 인간 수학자가 검증하기 어렵다는 것이다. 애초에 사람이 직접 하기에는 무지막지하게 시간이 오래 걸리기 때문에 컴퓨터를 이용했는데, 오류가 있는지 사람이 일일이 검증할 수가 없다. 케플러의 추측 증명은 용량이 3기가바이트였고, 수학자 12명이 4년 동안 달라붙어 검증한 끝에 99퍼센트 확실하다는 결론을 내렸다. 켈러의 추측 7차원의 증명은 용량이 200기가바이트에 달한다.

 

그리고 컴퓨터를 이용한 증명을 ‘진짜 증명’이라고 할 수 없다는 의견도 있다. 컴퓨터의 막강한 연산력을 사용해 사람이 할 수 없을 정도로 많은 계산을 해낸 것이지 논리적으로 그렇게 될 수밖에 없음을 보여 주는 아름다운 증명은 아니라는 것이다. 모든 경우의 수를 다 시도해서 비밀 번호를 알아내는 건 실용적일 수는 있어도 그렇게 아름답다고 하기는 어렵다. 그런 소재로 영화를 만든다고 해도 무작정 풀어내는 것보다는 영화 「미션 임파서블」처럼 절묘한 작전으로 비밀을 캐내는 게 더 재미있지 않을까?

 

그렇다면 ‘증명’의 정의에 관해 생각하지 않을 수 없다. 증명 과정에 필요한 막대한 양의 계산을 컴퓨터가 대신하게 한다면, 사람이 온전히 풀어냈다고 할 수 있을까? 아펠과 하켄이 4색 정리 증명을 발표했을 때 많은 수학자가 컴퓨터를 사용한 증명이라는 이유로 시큰둥한 반응을 보였다. 심지어는 적대적인 반응을 보이는 사람도 있었다.

 

결론은 나지 않았지만, 수학에서 컴퓨터 사용은 점점 늘어나고 있다. 컴퓨터로 증명을 하지는 않더라도 사람이 한 증명을 검증하는 데 컴퓨터를 사용할 수도 있다. 최초로 프로그램이 가능한 컴퓨터를 만들었던 영국 수학자 찰스 배비지(Charles Babbage, 1791~1871년)는 노동과 같은 단순 계산은 기계에 맡기고 사람은 여유 시간에 창조적이고 고차원적인 활동을 할 수 있게 하는 게 목적이라고 한 바 있다. 그런데 컴퓨터를 사용한 증명에 부정적인 이야기를 들어보면, 애초에 컴퓨터를 사용하지 않아도 될 정도로 아름다운 논리로 밝혀야 진정한 증명이라는 것처럼 들린다. 어려운 문제다.

 

 

컴퓨터를 이용한 수학 증명은 정말로 증명일까, 컴퓨터를 이용한 물리학 연구는 정말로 과학일까? 컴퓨터와 인공 지능의 발전은 새로운 문제를 우리에게 던지고 있다.

 

 

참고 문헌

Donald Mackenzie, “Slaying the Kraken: The Sociohistory of a Mathematical Proof,” Social Studies of Science (1999), Feb, 7-60.

https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/


고호관

대학에서 건축과 과학사를 공부했다. 《과학동아》 기자, 《수학동아》 편집장으로 일했고, 현재 과학 저술가이자 SF 작가 또는 번역자로 활동 중이다. 『우주로 가는 문 달』을 썼고, 『아서 클라크 단편 전집』 등을 옮겼다.

 

 

 

함께 읽으면 좋은 책들

 

『세상 모든 비밀을 푸는 수학』 [도서정보]
재난 예측에서 온라인 광고까지 미래 수학의 신세계

 

 

『수학의 파노라마』 [도서정보]
수학을 다시 시작하는 이들을 위한 최고의 비주얼 가이드

 

 

『자연의 패턴』 [도서정보]
우리 시대의 과학 큐레이터가 엄선한 형태학 미술관을 탐험하라

 

 

『세계를 바꾼 17가지 방정식』 [도서정보]
위대한 방정식에 담긴 영감과 통찰

 

 

『수학 학습 심리학』 [도서정보]
수학 학습을 위한 독창적인 아이디어로 가득한 고전

 

 

『로봇 수업』 [도서 정보]

인공 지능은 물론, 로봇과 사이 좋게 사는 법?

 

 

『아서 클라크 단편 전집 1953-1960』 [도서정보]
경이로운 소설가이자 예언자인 아서 클라크의 걸작 단편



0 Comments
댓글쓰기 폼