그레이엄 수보다 큰 수 만드는 10상태 튜링 머신 등장... Coq 검증 완료

요약 수학 및 컴퓨터 과학 분야의 대표적인 난제이자 극도로 거대한 수를 탐구하는 '바쁜 비버(Busy Beaver)' 문제에서 새로운 기록이 나왔습니다. 개발자 jeff87654가 공개한 10상태 튜링 머신 'n1'이 기존 챔피언 기록을 제치고, 수학계에서 상상할 수 없을 만큼 거대한 수로 꼽히는 '그레이엄 수(Graham's number)'를 아득히 뛰어넘는 크기를 기록한 것으로 확인되었습니다. 이번에 설계된 10상태 머신 n1은 빈 테이프(blank tape)에서 시작해 유한한 단계를 거친 뒤 반드시 멈추는(halt) 성질을 지니고 있으며, 머신이 정지할 때 테이프에 남기는 1의 개수를 계산하는 방식으로 점수가 매겨집니다. 특히 이 기계의 정지 여부와 점수 하한선, 그리고 그레이엄 수보다 크다는 사실은 수학적 정리 증명 보조 도구인 Coq을 통해 기계적으로 완벽히 교차 검증(machine-checked)되었습니다. 기존 BB(10) 챔피언은 급속 성장 계층(Fast-Growing Hierarchy) 기준으로 f_ω 단계(f_ω(f_ω(25)))에 머물러 있었으나, 이번 n1 머신은 f_(ω+1) 레벨에 진입하면서 바쁜 비버 10상태 연구를 한 단계 더 높은 차원으로 끌어올렸습니다. n1은 기존 BB(8) 기록의 기저 머신(8상태)을 바탕으로 정지 전이(E0)를 새로운 상태 I와 J로 확장하여 수치 카운트다운과 클리어링을 반복하도록 설계되었습니다. 그 결과 테이프에 찍히는 1의 개수는 2↑^37 3이라는 거대한 수 T를 기반으로 한 재귀 연산을 거치며 상상을 초월하는 크기에 도달하게 됩니다. 이번 발견은 기계 검증을 통해 수학적으로 엄밀히 입증되었다는 점에서 컴퓨터 이론 및 큰 수 연구 커뮤니티에서 큰 주목을 받고 있습니다.