비지 비버 함수와 정지 문제: 튜링 기계가 드러내는 계산의 한계와 콜라츠 추측의 연결

핵심 메시지

• 비지 비버 함수는 n개 상태를 가진 모든 튜링 기계 중 멈춘 기계가 남긴 1의 최대 개수로, 어떤 계산 가능한 함수보다도 결국 빠르게 커진다.
• 5상태 챔피언 기계의 실제 동작을 뜯어보면 콜라츠 추측과 같은 계열의 연산을 반복하고 있다는 사실이 드러난다.
• 시프트 함수 S(n)의 값을 알면 골드바흐 추측 같은 무한에 대한 질문이 유한한 계산으로 바뀐다. 정지 문제가 수학의 밑바닥에 있다는 뜻이다.
• 산술적으로 건전한 공리 체계라면 어느 지점부터는 시프트 함수의 값을 증명할 수 없다는 정리가 존재하며, 이는 괴델의 두 번째 불완전성 정리에서 따라 나온다.
• 해설자는 이 주제가 '아, 이제 알겠다'는 해소의 순간 대신 파고들수록 신비가 깊어지는 드문 경험을 준다고 말한다.

쉽게 이해하기

수학에서는 이상해 보이던 결과가 관점을 바꾸는 순간 당연해지는 경험이 흔하다. 해설자는 비지 비버 함수만은 예외라고 말한다. 들여다볼수록 이해가 아니라 의문이 늘어나는 대상이라는 것이다. 출발점은 튜링 기계다. 튜링 기계는 임의의 계산을 표현하는 수학적 대상이고, 계산이란 입력에 유한한 단계를 적용해 출력을 만드는 절차다. 이 기계는 0과 1로 채워진 무한한 테이프를 읽고 쓰며, 상태 표가 입력 테이프를 출력 테이프로 바꾸는 방식을 결정한다.

비지 비버 함수는 n개 상태를 가진 모든 튜링 기계를 전부 0인 테이프 위에서 돌린 뒤, 멈춘 기계들이 남긴 1의 개수 중 최댓값으로 정의된다. 이 함수는 계산 자체가 닿을 수 없는 대상이다. 어떤 계산 가능한 함수 F를 가져와도 어느 지점부터는 비지 비버 함수가 더 크다. 이유는 이렇다. 계산 가능한 함수는 상태 수가 고정된 하나의 튜링 기계로 표현되지만, 비지 비버 함수는 n개 상태를 갖는 모든 기계를 놓고 최댓값을 취한다. n이 충분히 커지면 비지 비버는 그 함수의 기계를 부품처럼 끌어다 쓰고 더 큰 값을 만들 수 있다.

1962년 라도의 원 논문은 이것을 게임으로 제시했다. 게임을 잘 두기 위해 과학과 수학의 모든 도구를 쓸 수 있는데, 지금까지 밝혀진 최선의 수는 뜻밖에도 정수론에서 나온다. 5상태 챔피언 기계는 4098개의 1을 남기고 멈추며 수천만 단계를 돈다. 그 동작을 압축해 보면 테이프 위 1의 개수를 3으로 나눈 나머지에 따라 서로 다른 단순 연산을 반복하는 구조다. 2로 나눈 나머지에 따라 단순 연산을 적용하는 콜라츠 함수와 같은 계열이며, 정수만 다를 뿐 형태가 거의 같다.

왜 하필 콜라츠인가. 상태 표를 프로그램이라고 보면 n은 프로그램의 최대 길이에 해당한다. 짧은 프로그램으로 엄청나게 많은 일을 하고 멈춰야 하므로, 서술은 단순하면서 동작은 혼돈스러운 규칙이 유리하다. 콜라츠가 바로 그런 규칙이다. 6상태 영역으로 가면 아직 챔피언이 최종 답인지도 모르는 상태인데, 현재 챔피언은 콜라츠식 연산의 지수 버전을 쓴다. 곱셈 계수가 지수로 올라가며 17개의 함수 호출이 사슬처럼 이어지고, 결과는 15층짜리 지수 탑에 비유될 정도로 폭발한다.

여기서 시프트 함수 S(n)이 등장한다. 남긴 1의 개수 대신 멈추기까지의 최대 단계 수를 세는 함수다. 골드바흐 추측이 거짓일 때만 멈추는 27상태 기계가 알려져 있는데, 만약 S(27)을 안다면 그 기계를 S(27)단계까지만 돌려 보고 멈추지 않았다면 영원히 멈추지 않는다고 결론지을 수 있다. 무한에 대한 질문이 유한한 계산으로 바뀌는 것이다. 물론 S(27)은 터무니없이 큰 수라 실용적인 방법은 아니다. 중요한 것은 이런 식으로 표현할 수 있는 수학 문제가 아주 많고, 따라서 그 문제들의 핵심에 정지 문제가 놓여 있다는 사실이다.

주요 인사이트

• 비지 비버 게임과 콜라츠 추측은 완전히 독립적으로 제안됐는데도 계산의 정점에서 만난다. 해설자는 이 사실이야말로 콜라츠가 기묘한 퍼즐이 아니라 진짜로 예외적인 문제라는 증거라고 본다.
• 정지 문제를 풀 수 있다면 임의의 상태 표와 테이프를 보고 실행 전에 멈출지 판단할 수 있다는 뜻이고, 그것은 사실상 수학 전반에 답하는 신탁을 갖는 일이 된다. 해설자는 이 관점이 정지 문제의 위상을 근본적으로 끌어올린다고 말한다.
• 계산 가능하고 산술적으로 건전한 공리 체계 T에는 어떤 정수 N이 존재해서, N보다 큰 모든 n에 대해 'S(n)은 어떤 값 k다'라는 형태의 문장을 T 안에서 증명할 수 없다. 현대 수학의 토대 역시 이 조건에 해당하므로, 우리 수학은 어느 지점 너머의 비지 비버를 끝내 알 수 없다.
• 그 증명은 괴델의 두 번째 불완전성 정리에서 나온다. T의 모든 가능한 증명을 나열하다가 0=1의 증명을 찾으면 멈추는 기계 M을 생각하면, T가 건전하므로 M은 멈추지 않지만 T는 자기 무모순성을 증명할 수 없어 M이 멈추지 않는다는 사실도 증명할 수 없다.
• 결국 이 한계는 복잡하거나 해독에 오래 걸리는 기계의 문제가 아니다. 멈추는지 아닌지에 대한 답을 만들어 낼 논리적 연역 자체가 존재하지 않는 개별 기계가 있다는 뜻이라고 해설자는 강조한다.

자주 묻는 질문

관련 AI 소식