'바쁜 비버'와 무한의 경계를 넘나드는 계산 게임

[한국정보기술신문] 한 장의 끝없는 종이 테이프와 단순한 명령 여럿으로 짜인 작은 기계가 있다고 가정해 보자. 이 기계가 "멈출 때까지 가장 오래 돌거나, 가장 많은 '1'을 찍고 세상에 남긴 뒤 멈추기" 대회를 연다면 어떨까? '비지 비버(Busy Beaver)' 게임은 바로 이런 가상의 경주다. 여기서 기계는 컴퓨터 과학에서 가장 간단한 모델인 '튜링 머신'을 쓰며, 주어진 상태 개수 안에서 누가 가장 "바쁘게" 일하다 멈추는지가 승패를 가른다. 점수판에는 두 수가 올라간다. 얼마나 많이 달렸는지를 뜻하는 '단계 수' S(n)과, 얼마나 흔적을 남겼는지를 보는 '1의 개수' Σ(n). 이 둘의 최댓값을 찾는 함수가 바로 BB(n)이다. 놀라운 사실은 n이 조금만 커져도 BB(n)을 완전히 계산해 줄 방식이 아예 존재하지 않는다는 것이다.

새로운 기록: 다섯 번째 비버 확정

지난해 국제 협업 'BBChallenge'는 5 상태 튜링 머신이 멈추기 전에 뛸 수 있는 최대 단계가 47,176,870임을 공식 증명했다. 이는 1989년 발견된 기계가 진짜 챔피언인지 35 년 만에 검증한 결과다. 같은 기계가 남길 수 있는 '1'의 최대치는 4,098로 확정됐다. 단순해 보이는 숫자지만 전 세계 연구자들이 살핀 63 조 여 대의 기계 중 압도적 1위다. 이번 결과는 약 4 년간 40여 개국 3,000여 명의 자원자가 분류한 31 조 개의 후보 기계를 Coq 증명 보조기로 자동 검증해 얻었다. 프로젝트 페이지는 "인간 직관과 형식 증명의 최대 합작품"이라 평가했다. 컴퓨터 과학자 스콧 애런슨은 "이번 업적은 수학과 크라우드소싱이 만든 새 연구 방식의 청사진"이라며 향후 대규모 문제에 적용될 가능성을 언급했다.

작동 원리와 역사

'바쁜 비버' 개념은 헝가리 출신 수학자 티보르 라도가 1962년 논문 「On Non-Computable Functions」에서 제안했다. 규칙은 간단하다. 빈 테이프, 두 기호(0, 1), n 개의 상태, 그리고 한 개의 '정지 상태'만 주어진다. 기계는 오른쪽·왼쪽으로 한 칸씩 움직이며 기호를 읽고 바꾸고, 상태를 전환하다가 언젠가 멈춘다. 그 동안 걸린 단계와 찍힌 1의 개수를 겨룬다. 1960년대 후반부터 과학자·동호인들이 '비버 경쟁'을 벌이며 더 좋은 기계를 찾았다. 아카이브 연구에 따르면 컴퓨터 성능 증가와 함께 기록 사냥도 진화했다. 4 상태까지는 1970년대 이미 정답이 나왔지만, 5 상태부터는 기계 수가 은하계 규모로 폭발해 분류조차 난제였다.

계산 가능성의 벽과 철학적 함의

BB(n)은 증명된 '계산 불능 함수'다. n이 커질수록 값이 모든 컴퓨터 가능 함수보다 더 빠르게 커지기에, 통상적 알고리즘으로는 어느 시점에 도달하지 못한다. 이는 튜링이 보인 '정지 문제'와 직결된다. 어떤 프로그램이 멈출지 알아내는 일은 일반적으로 불가능하며, BB(n)을 완전히 알 수 없다는 사실이 이를 구체적으로 드러낸다. 라도는 "BB(n)을 전부 계산할 수 있다면 골드바흐 추측처럼 멈춤 여부로 표현되는 모든 미해결 문제도 판정할 수 있다"고 시사했다. 다시 말해 '바쁜 비버'는 '알 수 없음'을 눈앞에 소환해 계산 이론의 경계를 체험하게 하는 거울이다.

크라우드소싱과 증명 보조기의 등판

2019년 출범한 'BBChallenge'는 누구나 참여할 수 있는 오픈 연구 플랫폼을 구축했다. 자원자들은 시뮬레이터로 5 상태 기계를 무차별 생성·실행했고, 결과를 증명 보조기가 자동 검증했다. Coq 같은 형식 증명 도구가 "기계 하나마다 수학적으로 틀림없음"을 보증하며, 인간의 휴리스틱 필터와 AI 탐색이 합쳐져 거대한 검색 공간을 뚫었다. 연구진은 완료된 증명을 리언(Lean)·아카이브 형태로 배포해 추후 검증과 재사용이 가능하도록 했다. 전문가들은 "인간·컴퓨터 협업이 수학적 발견의 새 패러다임을 연다"는 점에서 이번 성과를 튜링상급 의미로 평가한다.

다음 도전: 6 상태 비버와 그 너머

6 상태 기계 하나가 멈추기 전 뛰는 단계 하한은 이미 10↑↑15, 즉 '15층 탑'의 거듭제곱 수보다 크다. 2022년 체코 프로그래머 파벨 크로피츠는 단 한 대의 6 상태 기계가 10^36 밀리언 단계(10 뒤에 0이 3,600만 개) 이상 달리고 멈추는 사례를 발표해 하한을 끌어올렸다. 연구자들은 "6 상태 정복엔 수십 년, 어쩌면 영원히 걸릴 수 있다"고 토로한다. 데이터와 증명 복잡도가 기하급수로 뛰기 때문이다. 그럼에도 양자컴퓨터·AI 자동 탐색 기술이 새 돌파구를 열 것이란 낙관론도 존재한다. '비버 사냥'은 계산 이론의 리미터 테스트이자, 무한에 도전하는 인간 호기심의 증거로 남아 있다.

한국정보기술신문 정보기술분과 전호재 기자 news@kitpa.org