가장 느린 컴퓨터 프로그램이 보여주는 수학의 본질적 한계

How the Slowest Computer Programs Illuminate Math’s Fundamental Limits | Quanta Magazine

How the Slowest Computer Programs Illuminate Math’s Fundamental Limits

 

"바쁜 비버" 게임의 목표는 가장 오래 실행되는 컴퓨터 프로그램을 찾는 것입니다. 이 과정에서 수학의 가장 근본적인 질문과 개념과 놀라운 연관성이 드러납니다.

프로그래머는 보통 코드 실행 시간을 최소화하려고 합니다. 하지만 1962년, 헝가리 수학자 티보르 라도(Tibor Radó)는 정반대의 문제를 제기했습니다. 단순한 컴퓨터 프로그램이 종료되기 전까지 얼마나 오래 실행될 수 있는가를 묻는 문제였습니다. 라도는 이러한 최대한 비효율적이면서도 여전히 작동하는 프로그램을 "바쁜 비버(Busy Beaver)"라고 불렀습니다.

이후 이 프로그램을 찾는 것은 프로그래머와 수학 애호가들 사이에서 큰 도전이자 재미있는 퍼즐로 자리 잡았습니다. 특히 1984년 『사이언티픽 아메리칸』의 "컴퓨터 레크리에이션" 칼럼에 소개된 이후 널리 알려졌습니다. 그런데 최근 몇 년 동안 이 바쁜 비버 게임은 단순한 퍼즐 이상의 학문적 연구 대상으로 떠올랐습니다. 그 이유는 이 게임이 수학의 높은 개념과 미해결 문제들과 연결되기 때문입니다.

"수학에서는 단순한 재미와 중요한 연구의 경계가 매우 유연합니다."라고 최근 바쁜 비버 연구 성과를 발표한 텍사스 대학교 오스틴 캠퍼스의 이론 컴퓨터 과학자 스콧 애런슨(Scott Aaronson)은 말했습니다.

최근 연구에 따르면, 오래 실행되는 프로그램을 찾는 과정을 통해 수학 지식의 상태를 조명하고, 심지어 알아낼 수 있는 것과 없는 것을 구분할 수 있습니다. 연구자들에 따르면 바쁜 비버 게임은 특정 문제의 난이도를 평가하는 구체적인 기준을 제공합니다. 예를 들어, 미해결 상태인 골드바흐 추측이나 리만 가설 같은 문제들을 평가할 수 있습니다. 또한, 수학의 논리적 토대가 무너지는 지점에 대한 힌트도 제공합니다. 논리학자 쿠르트 괴델(Kurt Gödel)은 거의 한 세기 전에 이러한 수학적 미지의 영역의 존재를 증명했지만, 바쁜 비버 게임은 이를 실제 수직선 위의 특정 위치에 놓아 '세상의 끝'을 묘사한 고대 지도처럼 보여줍니다.

 

# 계산 불가능한 컴퓨터 게임: 바쁜 비버 문제

바쁜 비버 게임은 튜링 머신의 행동에 관한 게임입니다. 튜링 머신은 1936년 앨런 튜링이 고안한 원시적이고 이상화된 컴퓨터입니다. 이 튜링 머신은 정사각형으로 나누어진 무한한 테이프에 행동을 수행합니다. 각 정사각형은 0 또는 1을 담고 있으며, 머신은 일정한 규칙에 따라 테이프를 읽고 행동을 결정합니다. 첫 번째 규칙은 다음과 같은 방식일 수 있습니다.

“만약 현재 정사각형에 0이 있으면, 1로 바꾸고 오른쪽으로 한 칸 이동한 후 두 번째 규칙을 참조하라. 만약 1이 있으면, 1을 그대로 두고 왼쪽으로 한 칸 이동하여 세 번째 규칙을 참조하라.”

각 규칙은 이러한 분기 구조를 가지고 있어 특정 규칙으로 되돌아가기도 하며, 마침내 "정지(halt)"라는 명령을 포함한 규칙이 나타나게 됩니다. 튜링은 이러한 단순한 컴퓨터가 적절한 지침과 충분한 시간이 주어지면 모든 가능한 계산을 수행할 수 있음을 증명했습니다.

1936년에 튜링은 계산을 수행하기 위해서는 튜링 머신이 결국 정지해야 한다고 지적했습니다. 무한 반복에 빠져서는 안 된다는 것입니다. 그러나 튜링은 정지하는 머신과 영원히 실행되는 머신을 구별할 수 있는 신뢰할 만한 방법이 존재하지 않음을 증명했습니다. 이 문제는 "정지 문제"로 알려져 있습니다.

바쁜 비버 게임은 다음과 같은 질문을 던집니다: 주어진 규칙 수 안에서 튜링 머신이 정지하기 전에 최대 몇 번의 단계를 수행할 수 있는가?

예를 들어, 하나의 규칙만 허용된다면, 정지하도록 하려면 바로 정지 명령을 포함해야 합니다. 따라서 1개의 규칙을 가진 머신의 바쁜 비버 수, 즉 BB(1)은 1입니다.

그러나 몇 개의 규칙만 더 추가해도 고려해야 할 머신의 수는 기하급수적으로 증가합니다. 두 개의 규칙을 가진 6,561개의 가능한 머신 중에서 가장 오래 실행된 후 정지하는 머신은 여섯 단계 동안 실행되며, 이것이 바쁜 비버입니다. 그러나 이들 중 일부는 영원히 실행됩니다. 이들이 바쁜 비버가 아닌 것은 명확하지만, 이를 확실히 배제하는 것은 쉽지 않습니다. 튜링은 천 단계 또는 백만 단계를 실행하는 머신이 결국 정지할지 여부를 자동으로 판단하는 방법이 없음을 증명했습니다.

이 때문에 바쁜 비버를 찾는 것은 매우 어렵습니다. 임의의 지시어 수를 가진 튜링 머신 중에서 가장 오래 실행되는 머신을 식별할 수 있는 일반적인 접근법이 존재하지 않습니다. 각 경우를 하나씩 세부적으로 분석해야만 합니다. 즉, 바쁜 비버 게임은 원칙적으로 "계산 불가능"합니다.

BB(2) = 6과 BB(3) = 21을 증명하는 것조차도 매우 어려운 작업이었으며, 이를 위해 라도의 제자 셴 린(Shen Lin)은 1965년에 박사 학위를 받았습니다. 라도는 BB(4)를 “전혀 불가능한 문제”로 여겼지만, 결국 1983년에 해결되었습니다. 그 이후 값들은 거의 폭발적으로 증가합니다. 예를 들어 다섯 개의 규칙을 가진 튜링 머신 중 47,176,870번의 단계를 실행한 후 정지하는 머신이 발견되었으므로 BB(5)는 최소한 그 정도 크기입니다. BB(6)는 최소한 $7.4 \times 10^{36,534}$입니다. 정확한 값을 증명하려면 “완전히 새로운 아이디어와 통찰이 필요할 것이며, 가능할지조차 확실하지 않다”고 애런슨은 말했습니다.

# 알 수 없는 한계: 바쁜 비버와 수학적 인식의 한계

메릴랜드 대학교의 컴퓨터 과학자 윌리엄 가사치(William Gasarch)는 바쁜 비버 수를 정확히 계산하는 것보다 “이 게임이 실제로 계산 불가능하다는 개념 자체”에 더 흥미를 느낍니다. 그는 다른 수학자들과 함께 이 게임을 중요한 미해결 수학 문제의 난이도를 측정하거나 무엇이 수학적으로 인식 가능한지를 판단하는 기준으로 사용합니다.

예를 들어, 골드바흐 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있는지를 묻습니다. 이 추측을 참 또는 거짓으로 증명하는 것은 수학에서 혁명적인 사건이 될 것이며, 소수의 분포에 대한 이해를 크게 넓혀줄 것입니다. 2015년, "Code Golf Addict"라는 익명의 GitHub 사용자가 골드바흐 추측이 거짓일 때만 정지하는 27개의 규칙을 가진 튜링 머신의 코드를 공개했습니다. 이 머신은 4보다 큰 모든 짝수를 순차적으로 확인하며, 각 짝수에 대해 두 소수를 더해 해당 짝수를 만들 수 있는 모든 경우를 점검합니다. 적절한 소수 쌍을 찾으면 다음 짝수로 넘어가 과정을 반복하고, 만약 두 소수의 합으로 표현할 수 없는 짝수를 발견하면 정지합니다.

이 머신을 실행한다고 해서 현실적으로 추측을 해결할 수 있는 것은 아닙니다. 이 머신이 정지할지 여부를 알기 전까지는 아무도 그 결과를 알 수 없기 때문입니다. 그러나 바쁜 비버 게임은 이 문제에 대해 흥미로운 통찰을 제공합니다. 만약 BB(27)을 계산할 수 있다면, 골드바흐 추측이 자동으로 해결되기까지 최대 얼마나 기다려야 하는지에 대한 상한선을 제공할 것입니다. BB(27)은 이 27개의 규칙을 가진 튜링 머신이 정지하기까지 필요한 최대 단계 수를 의미하므로, 이 수만큼 단계를 실행했을 때 정지하면 골드바흐 추측이 거짓임을 알 수 있습니다. 반면 그 단계 동안 정지하지 않는다면, 그 머신은 영원히 정지하지 않을 것이며, 따라서 골드바흐 추측이 참이라는 결론을 내릴 수 있습니다.

문제는 BB(27)이 상상할 수 없을 만큼 거대한 수치이기 때문에, 이 수치를 기록하거나 골드바흐 추측을 반증하는 머신을 그 단계 수만큼 실행하는 것이 물리적으로 불가능하다는 점입니다. 하지만 그 엄청난 수치는 여전히 정확한 값이며, 애런슨에 따르면 이 수치의 크기는 현재 우리가 수론에서 가지고 있는 지식 수준을 상징한다고 할 수 있습니다.

2016년 애런슨은 유리 마티야세비치(Yuri Matiyasevich)와 스테판 오리어(Stefan O'Rear)와의 협업을 통해 리만 가설이 거짓일 때만 정지하는 744개의 규칙을 가진 튜링 머신을 만들었습니다. 리만 가설 역시 소수 분포와 관련이 있으며, 클레이 수학 연구소에서 밀레니엄 문제로 지정하여 100만의 상금을 걸어놓은 문제입니다. 애런슨의 이 머신은 BB(744) 단계만큼 실행되면 자동으로 가설의 진위를 판별합니다. (이 머신도 골드바흐 머신과 마찬가지로 무작정 상향 반복하면서 반례를 찾는 방식으로 작동합니다.)

물론 BB(744)는 BB(27)보다도 훨씬 더 접근할 수 없는 수치입니다. 하지만 애런슨은 BB(5)처럼 상대적으로 쉽게 계산할 수 있는 값을 찾으려는 과정에서 새로운 수학적 질문들이 발견될 가능성이 있다고 말했습니다. 예를 들어, 수학자 파스칼 미셸(Pascal Michel)은 1993년에 다섯 개의 규칙을 가진 튜링 머신이 콜라츠 추측에 등장하는 함수와 유사한 행동을 보인다는 것을 증명했습니다. 콜라츠 추측 역시 수론에서 유명한 미해결 문제 중 하나입니다.

애런슨은 “만약 모든 바쁜 비버 수를 알 수 있다면, 이러한 모든 질문을 해결할 수 있을 것이다”라고 말했습니다. 최근에 그는 바쁜 비버에서 파생된 척도를 사용하여 그가 “알 수 없음의 한계”라고 부르는 수학적 체계 전체의 경계를 측정하려고 했습니다. 괴델의 1931년 불완전성 정리는 수학의 논리적 기초가 될 수 있는 기본 공리의 집합이 두 가지 운명 중 하나를 맞이하게 될 것임을 증명했습니다: 하나는 공리가 일관성이 없어 모순을 초래하는 경우(예: $0 = 1$을 증명하는 경우), 또 다른 하나는 공리가 불완전하여 수와 관련된 일부 참된 진술을 증명할 수 없는 경우입니다(예: $2 + 2 = 4$이라는 사실을 증명할 수 없는 경우). 오늘날 대부분의 현대 수학의 토대를 이루는 체계인 체르멜로-프렝켈(Zermelo-Fraenkel, ZF) 집합론도 괴델의 한계에 직면해 있으며, 애런슨은 바쁜 비버 게임을 통해 이 경계를 구체적으로 드러내고자 했습니다.

2016년, 애런슨과 그의 대학원생 애덤 예디디아(Adam Yedidia)는 ZF 집합론이 일관성이 없을 때만 정지하는 7,910개의 규칙을 가진 튜링 머신을 설계했습니다. 이는 BB(7,910)이 ZF 집합론의 공리로는 계산할 수 없는 수라는 것을 의미합니다. ZF 공리 체계에서는 이 BB(7,910)의 값이 특정한 수인지 아닌지를 증명할 수 없습니다. 이는 마치 $2 + 2 = 4$임을 증명할 수 없는 것과 유사한 상황입니다.

그 후 오리어(Stefan O'Rear)는 ZF가 일관성이 없을 때만 정지하는 훨씬 간단한 748개의 규칙을 가진 머신을 설계해, 알 수 없음의 경계를 BB(7,910)에서 BB(748)로 크게 줄였습니다. “이 숫자(규칙 수)가 완전히 터무니없지 않다는 것은 매우 극적인 일입니다.”라고 오하이오 주립 대학교의 수리 논리학자 하비 프리드먼(Harvey Friedman)은 말했습니다. 프리드먼은 그 숫자가 더 낮아질 수 있다고 믿습니다. 그는 “아마도 50이 정답일 수 있다”라고 덧붙였습니다. 애런슨은 실제 한계가 BB(20)에 가까울 수 있다고 추정합니다.

가깝든 멀든, 이러한 알 수 없음의 경계는 확실히 존재합니다. “이것이 우리가 괴델 이후로 가지고 있는 세계관입니다.” 애런슨은 말합니다. “바쁜 비버 함수는 이러한 경계를 구체적으로 드러내는 또 하나의 방식입니다.”