결정문제
'결정 문제'란 모든 수학적 명제에 대해 참인지 거짓인지를 유한 시간내에 판별할 수 있는 일반적인 절차, 즉 알고리즘이 존재하는지를 묻는 것이었습니다. 이 문제를 처음 제기한 힐베르트는 이러한 알고리즘이 존재할 것이라 기대했습니다. 1920년대에는 수학적 엄밀성에 대한 열정이 고조되어 있었고, 수학적 진리를 탐구하는 강력한 체계들이 속속 등장하고 있었기 때문입니다. 힐베르트는 수학이 충분히 강력하다면, 모든 문제에 대해 확실한 답을 구할 수 있을 것이라 보았던 것입니다.
하지만 10년이 채 지나지 않은 1936년, 영국의 젊은 수학자 앨런 튜링은 '계산 가능한 수와 결정 문제에 관한 적용에 관하여'라는 논문을 통해 모든 수학적 명제를 증명하거나 반증할 수 있는 하나의 보편적인 절차, 즉 알고리즘이 존재하지 않는다는 사실을 증명합니다.
튜링 기계(Turing Machine)
튜링의 논증은 매우 독창적이었는데, 그는 '튜링 기계'라는 개념적인 장치를 통해 어떤 명제가 주어졌을 때 이 명제를 풀기 위해 필요한 단계별 과정이 존재하는지 검토했습니다. 유한하고 기계적인 절차를 통해 계산 가능한 함수라는 직관적 개념을 형식화하는 데 성공한거죠.
튜링 기계는 무한히 긴 테이프(tape)를 갖춘 상상의 계산 기계입니다. 이 테이프는 같은 크기의 작은 칸(셀, cell)으로 나누어져 있으며, 각 셀에는 특정 기호가 기록됩니다. 튜링 기계의 헤드(head)는 테이프 위를 이동하며 셀에 기록된 기호를 읽거나 새로운 기호를 써넣을 수 있습니다. 튜링 기계의 현재 상태는 상태 기록기(state register)에 저장되며, 상태에 따라 기계의 동작은 동작 지침(action table)이라는 지침표에 의해 결정됩니다.
테이프(Tape)
테이프(Tape) 는 무한히 긴 종이와 비슷한 것으로, 작은 칸들로 나뉘어 있으며 각각의 칸에는 글자나 숫자(기호, Symbol)가 적혀 있을 수 있고, 비어 있을 수도 있습니다. 테이프는 상징적인 것으로 필요한 만큼 양쪽으로 더 길게 늘어날 수 있습니다. 대부분의 튜링 기계 문제에서 일관된 초기적은 제공하기 위해 테이프가 모두 0으로 채워진 상태에서 시작합니다.
머리(Head)
머리(Head)는 테이프 위에서 이동하며 기호를 읽거나 쓸 수 있는 작은 장치입니다. 머리는 칸을 하나씩 움직이며 현재 위치에 어떤 기호가 적혀 있는지를 읽고, 그에 따라 명령을 실행합니다. 예를 들어, 머리가
0이라는 기호를 읽고1로 바꾸거나, 테이프를 오른쪽으로 한 칸 이동하는 식입니다. 머리는 한 번에 한 칸씩 움직이며 읽기(read)와 쓰기(write) 작업을 수행하는 역할을 합니다.상태 기록기 (State Register)
튜링 기계에는 상태(State) 라는 개념이 있습니다. 상태 기록기 (State Register)는 기계가 지금 어떤 상황에 있는지를 기억하는 역할을 합니다. 튜링 기계은 항상 하나의 상태에 있으며, 이 상태가 바뀌면서 수행할 작업도 달라집니다.
동작 지침 (Action Table)
튜링 기계는 기계가 무엇을 해야 할지 미리 정해진 동작 지침(Action Table) 에 따라 작동합니다. 동작 지침은 기계가 특정 상태에 있을 때 특정 기호를 읽으면 어떤 행동을 해야 하는지를 알려줍니다. 예를 들어, 동작 지침에는 다음과 같은 내용이 있을 수 있습니다.
- 상태가 $A$이고 $0$을 읽고 있다면, $1$을 쓰고, 오른쪽으로 한 칸 이동하며($R$), $B$라는 상태로 전환(Change State)한다.
- 상태가 $B$이고 $1$을 읽고 있다면, 그대로 두고, 왼쪽으로 한 칸 이동하며($L$), $C$라는 상태로 전환한다.
이해하기 쉽게 수식으로 정리해보겠습니다. 전이 함수 $\delta$는 튜링 기계의 동작을 정의하며 다음과 같은 형식으로 표현됩니다.[^2]
$$\delta(\text{현재 상태}, \text{읽은 기호}) = (\text{쓰는 기호}, \text{이동 방향}, \text{다음 상태})$$
예를 들어 $\delta(A, 0) = (1, R, H)$을 보겠습니다. 이 식을 한 줄로 요약하면, 현재 상태가 $A$이고 읽은 기호가 $0$이면, $1$을 쓰고, 헤드를 오른쪽으로 이동한 후, 종료 상태 $H$로 변경하는 것을 의미합니다. 따라서 모든 셀이 $0$인 빈 테이프에서 시작하여, 첫 번째 셀에서 $0$을 읽고 $1$을 쓰고 오른쪽으로 이동한 후 종료합니다.
다음으로 $\delta(A, 0) = (1, R, A)$이라면, 첫 번째 셀에서 $0$을 읽고 $1$을 쓰고 오른쪽으로 이동하여 상태 $A$를 유지합니다. 두 번째 셀에서도 $0$을 읽고 $1$을 쓰고 오른쪽으로 이동하여 상태 $A$를 유지합니다. 그런데 초기 테이프에는 $1$이 없으므로 기계는 무한히 $1$을 출력하는 루프에 빠지며 기계는 종료되지 않습니다.
앨런 튜링는 오늘날 튜링 머신이라 불리는 개념을 정의하며, 정수에 대한 함수가 직관적으로 계산 가능하다는 것이 오직 튜링 머신으로 계산 가능할 때만 해당된다고 주장했습니다. 이와 비슷한 시기에 다른 연구자들도 다양한 계산 모델을 제안했으나, 이들 역시 튜링 머신과 동일한 함수 집합을 계산하는 것으로 판명되었습니다.
일련의 연구를 통해 계산 가능성에 대한 직관적 개념을 튜링 머신의 형식적 개념으로 포착하여 "어떤 함수가 계산 가능하다면, 그 함수는 튜링 머신으로 계산 가능하다."는 처치-튜링 논제(Church-Turing Thesis)로 발전했습니다.[^4] 따라서 우리가 직관적으로 계산 가능하다고 여기는 모든 함수는 튜링 머신이라는 형식적 모델을 통해서만 계산될 수 있으며, 다른 어떤 계산 모델로도 이보다 더 많은 함수를 계산할 수 없다고 볼 수 있습니다. 이 논제는 수학적 정리가 아닌 가설로 간주되지만, 아직까지 이 논제를 반박할 만한 계산 모델이 아직 발견되지 않았고, 실용적인 컴퓨팅의 모든 영역에서 튜링 모델은 표준으로 받아들여지고 있습니다.
계산 가능한 함수와는 달리 어떤 계산 모델이 주어지면, 대각화 방법을 통해 쉽게 계산 불가능한 함수를 정의할 수 있습니다. 대각화 방법이란 모든 계산 가능한 함수들의 목록을 작성한 후, 목록에 있는 각 함수와 구별되는 함수를 정의하는 방법입니다. 이렇게 정의된 함수는 계산 불가능한 함수가 됩니다. 그러나 대각화를 통한 정의는 목록 선택과 마지막 함숫값 선택에 너무 많은 여지를 남깁니다. 따라서 계산 불가능한 함수도 단순하고 자연스러우며 모호함이 없는 정의가 필요했습니다.
계산할 수 없는 함수
티보르 라도(Tibor Radó)는 튜링의 연구가 남긴 한계를 더욱 확장하며, 계산할 수 없는 함수의 본질에 초점을 맞췄습니다. 라도는 계산 불가능성을 단순히 추상적인 한계로 두기보다, 한계를 실제로 체감할 수 있는 구체적인 예로 설명하고자 했습니다. 이렇게 탄생한 개념이 바로 바쁜 비버 함수(Busy Beaver Function)입니다.
바쁜 비버 함수는 $\Sigma$ 함수와 $S$ 함수를 포괄하는 개념으로 사용됩니다.[^3]
$\Sigma(n,k)$는 $n$개의 상태와 $k$개의 기호를 가진 튜링 기계들 중에서 멈추기 전까지 테이프에 남길 수 있는 최대 $1$(또는 특정 기호)의 개수를 나타냅니다. 즉, 최대한 많은 $1$을 남기는 기계를 찾는 것이 목표입니다.
$S(n,k)$는 $n$개의 상태와 $k$개의 기호를 가진 튜링 기계들 중에서 멈추기 전까지 수행하는 최대 이동 횟수 즉, 가장 오래 이동하는 기계를 찾는 것을 목표로 합니다.
이 두 함수는 각각 다른 기준으로 튜링 기계의 '바쁨'을 측정하는 지표로, 튜링 기계가 계산 가능한 최대한의 작업량을 정의합니다. 자연에서 가장 부지런한 동물로 꼽히는 비버는 항상 일하는 모습으로 잘 알려져 있습니다. 이러한 비유에서 착안하여, 주어진 조건 내에서 최대한 많은 작업을 수행하는 튜링 기계의 특성을 강조하며 이 함수를 ‘바쁜 비버 함수’라고 부르게 되었습니다. 나무 막대기 처럼 생긴 $1$로 둑을 쌓는 점도 유사점이라 생각합니다.
바쁜 비버 문제의 고전적인 정의가 기호가 $2$개인 튜링 기계를 기반으로 했고, 기호 수가 늘어나면 튜링 기계의 복잡성이 크게 증가하기 때문에 일반적으로 $\Sigma(n)$이나 $S(n)$이라 하면 $k=2$인 경우를 고려한 것입니다.
$$\Sigma(n)=\Sigma(n,2), \quad S(n)=S(n,2)$$
때에 따라 $BB(n)=\Sigma(n)$이나, $BB(n)=S(n)$으로 나타내긴 하지만 저는 각각 나누어 값을 찾아보도록 하겠습니다.
$BB(1)$
구체적인 예시로 $BB(1)$의 값을 구해보겠습니다. $BB(1)$은 상태가 하나인 바쁜 비버가 다음과 같은 조건에서 수행할 수 있는 최대 작업을 의미합니다:
- 기계가 멈출 때까지 테이프에 남기는 1의 최대 개수인 $\Sigma(1)$.
- 기계가 멈출 때까지 수행하는 최대 이동 횟수인 $S(1)$.
이 값을 찾기 위해 상태가 한 가지인 바쁜 비버가 수행할 수 있는 모든 동작을 고려해보겠습니다. 우선 기계의 동작을 결정하는 전이 함수를 정의해보겠습니다. [^1]
상태가 하나이므로, 현재 상태 $A$에서 읽을 수 있는 기호 $0$과 $1$에 대한 전이 함수를 설정해야합니다. 초기 테이프는 모두 $0$이므로, 첫 번째로 고려해야 할 전이 함수는 $\delta(A, 0)$입니다. 다음으로, 최대한 많은 $1$을 테이프에 남기기 위해 $0$을 $1$로 바꿔야 합니다. 마지막으로 바쁜 비버가 멈추기 위해서는 종료 상태 $H$로 변경해야 합니다.
$$\delta(A, 0) \rightarrow (1, R, \textbf{H})$$
반면에 상태가 하나뿐인 조건에서, 바쁜 비버가 더 많은 $1$을 남기기 위해서는 추가적인 상태 변경이 필요합니다. 그러나 상태를 하나 더 추가하면 $BB(1)$의 조건을 벗어나게 됩니다. 만약 상태 $A$에서 다시 $A$로 변경하도록 설정하면,
$$\delta(A, 0) \rightarrow (1, R, A)$$
기계는 무한 루프에 빠져 멈추지 않게 됩니다. 따라서 바쁜 비버가 멈추면서 최대한 많은 $1$을 남기기 위해서는 $\delta(A, 0) = (1, R, \textbf{H})$가 최선입니다. 결국 상태가 한 가지인 바쁜 비버는 최대 한 개의 $1$을 테이프에 남기고, 한 번의 이동 후 멈출 수 있다는 것을 알 수 있습니다.$$\Sigma(1) = S(n) = 1$$
$BB(2)$
나아가, $BB(2)$의 값도 구해보겠습니다.[^7] 이 경우에는 앞선 상황에 비해 다양한 전이함수를 다뤄야하므로[^6]
$$\delta =
\begin{cases}
(A, 0) \rightarrow (1, R, B) \\
(A, 1) \rightarrow (1, L, B) \\
(B, 0) \rightarrow (1, L, A) \\
(B, 1) \rightarrow (1, R, \textbf{H})
\end{cases}$$
표로 나타내어 설명하겠습니다.
$$\begin{array}{c|c|c}
\delta& A & B \\ \hline
0 & 1RB & 1LA \\ \hline
1 & 1LB & 1R \textbf{H}
\end{array}$$
전이 함수를 표로 명확하게 나타내기 위해 표의 첫 번째 행에는 현재 상태를, 첫 번째 열에는 읽은 기호를 적습니다. 다음으로 각 행과 열이 교차하는 칸에는 해당 전이 함수의 값을 쓰는 기호(Write symbol), 이동 방향(Move tape), 다음 상태(Next state) 순서로 작성합니다. 예를 들어 상태 $A$에서 읽은 기호가 $0$이면, $1$을 쓰고, 오른쪽으로 이동하여 상태 $B$로 변경하라는 것으로 이해할 수 있습니다.
$BB(2)$의 값을 찾는 작업은 위의 전이 함수 표를 만드는 것 처럼 단순해 보일 수 있습니다. 하지만 각 상태와 기호의 모든 전이를 고려하면 가능한 조합이 기하급수적으로 많아집니다. ($n$개의 상태를 가진 바쁜 비버의 총 수는 $[4(n+1)]^{2n}$ 가지이다.) 결국 가능한 바쁜 비버의 수가 급격히 늘어나므로, 모든 경우를 검토해 $BB(2)$를 찾는 것은 인간의 계산 능력을 넘어섭니다.
그렇다면 이렇게 많은 조합 중에서 $BB(2)$의 값을 어떻게 찾아야 할까요? 조합이 많더라도, 중복되거나 무한히 반복되는 조합을 최적화하여 제거할 수 있습니다. 동일한 결과를 내는 전이 조합을 하나의 유형으로 묶거나, 특정 패턴을 통해 무한 반복 여부를 미리 확인하여 계산 시간을 줄일 수 있지요. 그럼에도 불구하고, 두 개의 상태를 갖는 기계는 무려 $6,561$개이며 이 중에서 가장 오래 실행되는 기계를 식별할 수 있는 일반적인 접근법은 존재하지 않습니다.[^5]
수 많은 조합 중 가장 긴 실행 시간을 가진 바쁜 비버를 찾는 과정은 단순하지 않지만 모든 경우를 일일이 검토한 결과 앞서 소개한 전이 함수가 $BB(2)$의 값을 찾는 함수라는 것이 밝혀져있습니다. 앞선 전이 함수를 이용해 시뮬레이션 해보겠습니다.
바쁜 비버는 초기 상태 $A$에서 출발합니다. 상태 $A$에서 $0$을 읽으면, $1$을 기록하고 오른쪽으로 이동하며 다음 상태 $B$로 변경합니다. 이어서 상태 $B$에서는 $0$을 읽으면 $1$을 적고 왼쪽으로 이동한 후 상태를 $A$로 변경합니다. 이와 같이 상태와 테이프 값을 분석하며 작업을 계속 수행합니다. 마지막으로 상태 $B$에서 $1$을 읽게 되면, $1$을 쓰고 오른쪽으로 이동하면서 헤드는 작동을 멈춥니다. 두 개의 상태를 가진 이 튜링 머신은 최대 $4$개의 $1$을 기록할 수 있으며, 총 $6$번 이동하게 됩니다. 따라서 $\Sigma(2) = 4$이고, $S(2) = 6$입니다.
$BB(n)$ 값을 찾는 과정에서 궁금증이 하나 생깁니다. 상태의 개수 $n$이 $1$ 또는 $2$ 이었을 때, 최대 $1$의 개수 $\Sigma(n)$와 최대 이동 횟수 $S(n)$를 모두 극대화하는 전이함수가 동일했습니다. 그렇다면 $n$이 커져가도 $\Sigma(n)$과 $S(n)$를 만들어 내는 전이함수가 같을까요?
$BB(3)$
$\Sigma(n)$과 $S(n)$를 만들어 내는 전이 함수가 언제나 같은 것이 아니라면 서로 다른 전이함수에서 이동 횟수와 $1$의 개수를 각각 극대화 할 가능성이 생깁니다. $BB(3)$의 경우를 통해 이 궁금증을 풀어보겠습니다.
세가지 상태 $A$, $B$, $C$에 대하여 전이 함수 $\delta_1$을 다음과 같이 정의한 후 시뮬레이션을 진행해보겠습니다. 이 바쁜 비버는 $6$개의 $1$을 적고 $14$번을 이동한 후 멈추게 됩니다.
$$\begin{array}{c|c|c|c}
\delta_{1}& A & B & C\\ \hline
0 & 1RB & 0RC & 1LC \\ \hline
1 & 1R\textbf{H} & 1RB &1LA
\end{array}$$
반면에 전이 함수 $\delta_2$로 작동하는 바쁜 비버는 $5$개의 $1$을 쓰지만 무려 $21$번을 이동한 후 멈추게 됩니다.
$$\begin{array}{c|c|c|c}
\delta_{2}& A & B & C\\ \hline
0 & 1RB & 1LB & 1LC \\ \hline
1 & 1R\textbf{H} & 0RC &1LA
\end{array}$$
$\Sigma(3) = 6$, $S(3) = 21$로 $\delta_1$과 $\delta_2$는 $BB(3)$에서 각각 최대 $1$의 개수와 최대 이동 횟수를 만들어내는 전이 함수입니다. 두 전이 함수는 특정 목표에 따라 최적화된 형태로 작동합니다. 하나의 바쁜 비버로 모든 최댓값을 달성하기는 어렵지요. 이는 바쁜 비버 문제의 다양성을 보여줌과 동시에 계산 가능성 이론에서 다양한 최적화 가능성을 탐구할 수 있는 중요한 기반이 됩니다.
$BB(n)$
$n=4$인 경우, $\Sigma(4) = 13$이고 $S(4) = 107$입니다. 이미 알려진 값을 단순히 시뮬레이션하려 해도 이전보다 훨씬 긴 테이프와 많은 시간이 요구됩니다. 바쁜 비버 문제를 처음 제안한 라도조차 $BB(4)$를 '해결 불가능한 문제'로 여겼지요. 그러나 1983년에 이 문제는 마침내 해결되었습니다. 이후의 값들은 과연 어떨까요?
$$\begin{array}{c|c|c|c}
\delta& A & B & C & D\\ \hline
0 & 1RB & 1LA & 1R\textbf{H} & 1RD\\ \hline
1 & 1LB & 0LC &1LD & 0RA
\end{array}$$
다섯 가지 상태를 가진 바쁜 비버의 수는 약 $17$조 개에 달합니다. 이 모든 머신을 $1$밀리초마다 하나씩 나열한다고 가정하면, 약 $500$년이 소요될 정도로 엄청난 양이지요. 1989년, 하이너 막센(Heiner Marxen)과 요헨 분트록(Jochen Buntrock)은 $n=5$일 때 테이프에 $4,098$개의 $1$을 기록하며 $47,176,870$단계 후에 멈추는 바쁜 비버를 잡았습니다.
$$\begin{array}{c|c|c|c|c}
\delta& A & B & C & D & E\\ \hline
0 & 1RB & 1RC & 1RD & 1LA & 1R\textbf{H} \\ \hline
1 & 1LC & 1RB & 0LE & 1LD & 0LA
\end{array}$$
이 발견은 $BB(5)$의 하한선을 제시했지만, 해당 기계가 실제로 최적의 바쁜 비버인지에 대한 증명은 이루어지지 않았습니다. 이후 2000년대 초반, 연구자들은 $43$개의 유력한 후보 비버를 추려냈습니다. 이러한 후보들 중 일부는 멈추지 않는다는 것을 증명하기 위해 수십 년간의 노력이 필요했습니다. 마침내 2024년, 수학자들의 대규모 협업 연구를 통해 막센과 분트록이 발견한 바쁜 비버가 $BB(5)$의 최적 해임을 증명했습니다.
$\Sigma(5) = 4098$를 만족하는 다른 비버
$$\begin{array}{c|c|c|c|c}
\delta& A & B & C & D & E\\ \hline
0 & 1RB & 1LC & 1RA & 1RA & 1R\textbf{H} \\ \hline
1 & 1RA & 1LB & 1LD & 1LE & 0LC
\end{array}$$
이 비버는 $11,798,826$번의 이동 만에 $4,098$번의 $1$을 작성한다.
$n=6$일 때, $BB(6)$은 아직 얼마인지 모릅니다. 다만 현재까지 발견된 가장 바쁜 비버는 2022년 파벨 크로피츠(Pavel Kropitz)에 의해 발견된 것으로,
$$\begin{array}{c|c|c|c|c|c|c}
\delta & A & B & C & D & E &F\\ \hline
0 & 1RB & 1RC & 1LC & 0LE & 1LF & 0RC \\ \hline
1 & 0LD & 0RF & 1LA & 1R\textbf{H} & 0RB &0RE
\end{array}$$
이 바쁜 비버는 쓸 수 있는 $1$의 개수가 무려 $10$의 거듭 제곱을 $15$번 반복한 수보다도 큽니다.
$$S(6) > \Sigma(6) > 10 \uparrow\uparrow 15 = \underbrace{10^{10^{10^{\cdots^{10}}}}}_{15 \text{번 반복}}$$
여기서 위쪽 화살표는 테트레이션(Tetration)을 나타내는 기호로, 거듭제곱을 반복적으로 수행하는 연산입니다. 수학에서 이 표기법은 주로 빠르게 증가하는 함수나 수학적 정의를 단순화할 때 사용됩니다.
$$
\begin{align}
10 \uparrow\uparrow 1 &= 10\\
10 \uparrow\uparrow 2 &= 10^{10}\\
10 \uparrow\uparrow 3 &= 10^{10^{10}}
\end{align}
$$
보시다시피 상태의 개수가 단지 $6$개 밖에 되지 않았음에도 이동 횟수는 기하급수보다 훨씬 더 빠르게 증가합니다. 비버가 정말 바쁠만 하죠.
바쁜 비버를 잡는게 중요한 이유
계산 이론에서는 시간 복잡도와 관련된 문제가 핵심이므로, 기계가 얼마나 많은 이동을 수행할 수 있는지가 특히 중요하게 다뤄집니다.
$$S(n) > \Sigma(n)$$
어떤 계산 문제에 대해 "계산 가능하지 않다"는 것을 증명하기 위해서는 해당 기계가 멈추지 않고 매우 많은 단계의 작업을 수행하게 만드는 상황을 제시하는 것이 유리하기 때문이죠. 그리고 이러한 성질은 중요한 미해결 수학 문제의 난이도를 측정하거나 무엇이 수학적으로 인식 가능한지를 판단하는 기준으로 사용합니다.
골드바흐 추측은 $2$보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있는지를 묻는 명제입니다. 이 추측은 수학에서 가장 매력적인 미스테리 중 하나로 참 또는 거짓을 수 세기동안 증명하지 못했습니다. 그러던 2015년, "Code Golf Addict"라는 익명의 GitHub 사용자가 골드바흐 추측이 거짓일 때만 정지하는 $27$개의 규칙을 가진 튜링 기계의 코드를 공개했습니다.[^8]
이 코드는 $4$보다 큰 모든 짝수를 순차적으로 확인하며, 각 짝수에 대해 두 소수를 더해 해당 짝수를 만들 수 있는 모든 경우를 점검합니다. 적절한 소수 쌍을 찾으면 다음 짝수로 넘어가 과정을 반복하고, 만약 두 소수의 합으로 표현할 수 없는 짝수를 발견하면 정지합니다. 즉, 이 튜링 기계는 골드바흐 추측이 거짓일 경우 멈추고, 참일 경우 끝없이 실행됩니다.
결국 이 말은 우리가 $BB(27)$의 값을 알고 있다면, 골드바흐 추측의 참·거짓 여부를 결정할 수 있다는 의미입니다. 왜냐하면 골드바흐의 추측을 증명하는 코드는 $27$-상태 튜링 기계이므로 기껏해야 $BB(27)$보다 적은 실행에서 멈추거나 영원히 실행됩니다. 따라서 이 코드를 실행해 $BB(27)$이후에도 멈추지 않는다는 것을 확인하면 골드바흐의 추측은 참이 되는거지요. $BB(27)$의 값을 알고 있다는 것은 상태가 $27$개인 튜링 기계를 모두 확인한 것이므로, 수백 년 동안 풀리지 않은 골드바흐 추측에 대한 직접적인 해결책을 제시하는 셈입니다.
물론 이 뜻이 골드바흐의 추측을 증명하거나 해결했다는 것은 아닙니다. $27$-상태 튜링 기계의 모든 동작 원리를 이해하는 것이 골드바흐의 추측보다 더 어려울 수 있지요. 하지만 골드바흐 추측의 참·거짓을 결정하기 위해 튜링 기계를 구현하고 검증하는 사례는 수학적 명제와 계산 가능성의 관계를 탐구하는 흥미로운 시도를 보여줍니다.
이러한 결과는 수학문제의 복잡성 척도로 “바쁜 비버”를 사용할 수 있다는 가능성을 보여줍니다. 쉽게 말해 드래곤볼의 스카우터 처럼 수학 명제가 얼마나 어려운지 측정할 수 있지요. 예를 들어 에르되시의 $2$의 거듭제곱 추측($n > 8$일 때, $2^n$의 $3$진법 표현에는 반드시 숫자 $2$가 포함된다는 추측)은 $15$개의 상태를 가진 튜링머신으로 참, 거짓을 판별할 수 있습니다.[^9] 따라서 $BB(15)$는 적어도 $2$의 거듭제곱 추측보다는 어렵습니다. 같은 방법으로 리만 가설을 반증하는 튜링기계는 상태가 무려 $744$개나 필요합니다.
$$\begin{array}{c|c}
n & BB(n)\\ \hline
5 & 47,176,870 \\
6 & > 10 \uparrow\uparrow 15\\
15 & \text{Erdős’ conjecture}\\
25 & \text{Goldbach conjecture}\\
744 & \text{Riemann Hypothesis}\\
748 & \text{independent of ZF}\\
7,910 & \text{independent of ZFC}\\
\end{array}$$
그나마 다행인 것은 많은 수학자들의 노력으로 골드 바흐의 추측을 반증하는 기계는 현재 $n$의 수를 $25$까지[^12] 줄였고, 리만 가설도 초기 $5,372$개[^11]의 상태를 갖는 코드에서 $744$개[^10] 까지 줄이는데 성공했습니다. 이 수들은 앞으로 더 낮아질 수 있고, 언젠가는 해결 가능한 영역으로 들어올 수도 있지요.
물론 $BB(6)$만 하더라도 우주의 있는 원자 수를 아득히 뛰어넘는 수입니다. 이러한 기계들을 실행하는 것은 물리적으로 불가능할지도 모릅니다. 하지만 수학은 꾸준히 발전하기에 먼 훗날 모든 바쁜 비버 수를 알게 된다면, 튜링 기계로 증명할 수 있는 모든 질문을 해결할 수 있을지도 모릅니다. 가장 바쁜 비버가 멈춘 순간을 기다리며,
[^1]: Michel, P. (2022). The Busy Beaver Competition: a historical survey
[^2]: Hopcroft, John; Ullman, Jeffrey. (1979). Introduction to Automata Theory, Languages, and Computation
[^3]: T. RADO. (1962). On Non-Computable Functions
[^4]: Computability and Recursion
[^5]: How the Slowest Computer Programs Illuminate Math’s Fundamental Limits
[^6]: Busy Beavers, Theoretical Computer Science (2021).
[^7]: Lin and Rado. (1965). Computer Studies of Turing Nlachine Problems
[^8]: C. G. Addict. No name, 2016.
[^9]: The Busy Beaver Challenge
[^10]: metamath-turing-machines/riemann-matiyasevich-aaronson.nql at master · sorear/metamath-turing-machines
[^11]: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
[^12]: lengyijun/goldbach_tm25
You know what's cooler than magic? Math.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
