BusyBeaver(6)은 정말 큼
(scottaaronson.blog)- Busy Beaver 6번째 수(BB(6)) 의 하한이 최근 새로운 연구로 대폭 증가함
- 기존에는 BB(6) > 10↑36,534으로 알려졌으나, 2022년 BB(6) > 10↑1510으로 상향 조정됨
- 최근에는 BBchallenge에서 BB(6) > 10↑10,000,00010으로 다시 상향, 이어서 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) 까지 갱신됨
- BB(6) 의 크기는 상상을 초월하며, 이 수는 우주 전체를 수없이 채울 수 있는 정도임
- 이러한 발전은 수학적 논리와 계산 이론의 한계와 잠재성을 새롭게 인식하게 하는 계기임
BB(6) 최근 연구 성과 개요
- 최근 수년간 세상과 연구 환경이 힘들게 느껴지는 상황이 지속되었음
- 그러나 이번 Busy Beaver 연구의 발전이 다시 연구에 대한 순수한 열정을 상기시키는 계기였음
- 2022년에는 Pavel Kropitz가 BB(6) > 10↑1510임을 증명하였음
- BB(6)은 6개의 상태를 가진 튜링머신이 올-제로 테이프 위에서 정지 전까지 최대 몇 번 동작할 수 있는지를 의미함
- 여기서 ^1510은 10을 자기 자신으로 15회 반복 거듭제곱(테트레이션)한 값임
- 이전의 연구에서는 BB(5)가 47,176,870임이 밝혀졌는데(BBchallenge 팀), 이는 이 수치가 관측 가능한 현실의 범위를 넘는 영역으로 급증하는 시점임
최근 하한 갱신 과정
- BBchallenge의 "mxdys"가 BB(6) > 10↑10,000,00010임을 증명함
- 이 증명은 Coq 언어로 작성된 공식 증명에 기반함
- 이후 다시 BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9)) 로 하한이 업데이트됨
- ↑↑는 테트레이션(거듭제곱의 반복)을 의미하며, 이는 2를 2로 테트레이션, 다시 그 결과로 테트레이션을 9회 반복하는 형태임
- 이 정도의 수는 기존 어떤 직관적 이해도 초월하는 영역에 해당함
- 참고로 펜테이션은 테트레이션의 반복을 의미하며, 이런 운영은 곱셈, 거듭제곱, 테트레이션을 넘어서는 연산임
커다란 수의 크기 이해
- 기자의 요청으로 10↑10,000,00010이라는 수의 크기를 설명할 필요가 있었음
- 이 모래알 개수는 10↑10,000,00010개의 우주를 모래로 채울 수 있을 정도임
- 이처럼 BB(6) 수치는 실제 관측 세계를 아득히 넘어선다는 점을 전달함
BB알고리듬의 본질적 한계에 대한 고찰
- BB(6) 수치의 엄청난 크기는 Busy Beaver 함수의 진정한 잠재력을 보여줌
- BB(n) 값이 세트 이론(ZFC)의 공리계에서 독립적이 되는 시점이 n=20~30 정도로 추정되었으나, 아마도 n=7~9에서도 이미 독립적으로 될 수 있음을 예측하게 됨
- 현재는 n=643에서 독립임이 공식적으로 알려짐
부록: 최근 행사 및 강연 소식
- 필자는 최근 프라하에서 열린 STOC'2025 행사에 참석하여 다양한 연구자들과 교류하고 새로운 정보를 얻었음
- 자신의 양자 가속화 현황에 대한 기조 강연 슬라이드도 공유함
- 이 내용에 대한 보다 자세한 후기는 추후 공유 예정임
Hacker News 의견
- bbchallenge Discord 서버에서, 사람들이 얼마나 많은 튜링머신 상태가 있어야 Graham's Number를 초월할 수 있는지 추측하는 모습 공유함. 최근 BB(6) 우승자가 달성한 2^^2^^2^^9도 이미 엄청난 수이지만, Graham의 성장 양상이 생각보다 빨리 등장할 수 있음에 놀람. 49비트 람다 항만 있어도 충분하다는 functional busy beaver [1] 자료와, 해당 사이즈의 폐쇄 람다 항이 77519927606개[2]에 불과하다는 점, 반면 6-state 튜링머신이 무려 399910780272640개나 존재함[3]을 언급함. 펜테이션이 단 6상태로 구현된 것을 계기로 이제 상당수 관련자들이 7상태면 Graham's Number도 넘을 수 있다고 믿는 분위기라 언급. 본인은 그럼에도 여전히 의외라고 봄. 며칠 전, 향후 10년 내 BB(7)이 Graham's Number를 넘는다는 증명이 나올지 두고 큰 내기를 했다고 소개하며, 다른 이들의 의견을 묻는 질문. (1, 2, 3 링크 제공)
- 전문가인 척 하진 않지만, BB(7)가 Graham's Number보단 클 거라 예측함. BB는 임의의 계산 가능한 수열보다 빠르게 성장해야 하므로, 실제 BB(7)이 얼마나 클지는 손으로만 짚는 수준이지만, 결국 모든 계산 가능한 연산자(예: up-arrow^n 등)보다 더 빨리 커져야 하는 방향성이 있음. 47176870에서 2^^2^^2^^9까지 성장 폭이, 2^^2^^2^^9에서 Graham's Number로 가는 폭보다 연산자 강도로 훨씬 더 극적인 변화임을 예감함. Graham's Number가 g_64인데 이 또한 up-arrow^n보다 한 단계 위의 개념으로 해석될 수 있어서, BB(7)이 Graham's Number를 넘을 것이라는 직감 공유.
- BB(748)처럼 불계산적인 숫자가 ZFC(집합론 공리계)와 독립적이라는 사실이 매우 신기함을 표현함. 마치 범주 오류처럼 느껴진다는 솔직한 심경 공유.
- BB(748)이 ZFC와 독립적인 이유는 값 그 자체가 아니라, 748상태 중 하나인 TM_ZFC_INC가 ZFC에서 모순(거짓 증명) 발견 시에만 멈추는 방식 때문임. BB(748)=N임을 증명하려면 TM_ZFC_INC가 N스텝 내 멈춘다 혹은 끝없이 돌음을 보이는 것인데, 괴델의 불완전성 정리에 따르면 ZFC가 모순이 아니라면 그 어떤 것도 증명 불가인 함의.
- 적은 줄의 텍스트(즉, ZFC 공리 자체)가 인간에게 중요한 산술적 진리를 충분히 표현할 수 있다고 생각한 것 자체가 더 놀랍다고 느낌. 6상태 튜링머신의 동작조차 간단히 예측이 안 되는 현실은 당연함. 괴델의 불완전성 정리 발표 이후 수학계가 더 많은 공리를 찾으려 꽤 적극적으로 움직였어야 했는데, 실제로는 기초연구 일부에서만 다뤄진 아쉬움 토로.
- 연속체 가설의 진릿값(플라톤주의적으로 보면 1 혹은 0)이 ZFC로 독립적 증명됨은 좋은 예시임. 거대한 수가 아닌 단순히 1비트도 ZFC에서 보장불가.
- BB(n)이 불계산적인 것이고, BB(748)은 (정의상) 748상태 튜링머신이 쓴 1의 개수이므로 계산 가능한 수임을 명확히 구분함. "독립적"이란 라벨 자체는 ZFC로 이 수가 정말 우리가 원하는 값임을 증명하는 과정에서 더 강력한 이론이 필요하다는 이야기임을 설명함.
- 숫자 자체가 ZFC와 독립적인 게 아니라, BB(748)을 계산하는 과정이 독립적임을 강조함. (모든 정수는 ZFC로 표현 가능)
- BB(14)가 Graham's Number보다 크다는 것은 유명한 사실이고, 이번 연구로 BB(7)도 Graham's Number 이상일 것이라는 직감 밝힘. 직관적으로, 펜테이션에서 Graham's Number까지 가는 아이디어가 47,176,870에서 2 <pentate> 5까지 도달하는 것보다 오히려 단순하다고 느낌.
- 좋은 정보라며, 본인 글에 대한 훌륭한 답변이 될 수 있을 것이라는 반응 남김
- Scott Aaronson의 “How Much Math Is Knowable?” [Harward CMSA] 유튜브 강연 https://www.youtube.com/watch?v=VplMHWSZf5c 및 최근 HN 논의글 https://news.ycombinator.com/item?id=43776477 링크로 공유
- "좌상단 첨자"가 테트레이션, 즉 반복 거듭제곱임을 알림. 1510이면 10의 10의... 15번 반복임을 설명. 처음 보는 개념이라 오타인가 싶었다고 공유함.
- 반복 연산 테마로 이어가면서, 이번엔 ‘펜테이션’을 처음 접했다는 반응
- 테트레이션을 이전에 본 적 있지만, Knuth의 up-arrow 표기법[1]이 더 보편적이고 일반화에 좋다는 선호 밝힘 (1)
- BB(6)은 6상태 2심볼({0,1}) 튜링머신이 초기 0테이프에서 멈추기 전 최대 스텝수라는 설명이 비전문가에게 매우 유익했음. 이 분야가 수십년 연구자를 위한 고난도 밀도와 특화된 용어로 구성된 곳임을 체감했으나, 우연히 이렇게 깊이 있는 글을 접하게 돼 신기하다는 긍정적 소감 공유
- 컴퓨터공학 학부생 수준이라면 busy beaver 문제를 처음 보더라도 감은 잡을 수 있을 내용이라고 생각함. 물론 특수 용어가 많지만, 수십년 경력 전용이라고 느낄 필요는 없다는 격려식 조언 추가
- 해당 정의는 소프트웨어 엔지니어링보다는 컴퓨터공학 이론 쪽에서 표준임을 밝힘
- "10,000,000 sub10" 개의 모래알이 있으면 관측 우주를 10,000,000 sub10배만큼 채울 수 있다는 설명에 혼란을 느낌. 관측 우주 질량으로 비교하는 게 일반적인데, 이 방식은 이미 실제 물질량보다 훨씬 크다고 지적함
- 맞다고 답변. 모래알/우주로 나눠도 그 자체가 거의 같은 급의 거대한 수라, 인접한 수(이 표기법에서)는 어마어마하게 차이 남. 10↑↑10,000,000 / (모래알/우주)도 10↑↑9,999,999보단 훨씬 크다고 설명. 우리 시스템에선 (매우 큰) / (우주적으로 큰) 값도 그냥 (매우 큰)으로 정리된다고 비유
- 테트레이션에선 더 이상 단순한 자릿수 비교가 아니라, "자릿수의 자릿수" 급 성장임을 부연
- 이 수는 모래알 10^100000개 정도로도 도저히 줄지 않으니, 나눠도 본질적으로 영향 미미함을 재확인
- 10,000,000^10,000,000도 충분히 말도 안 되는 크기라서, 한 번 더 지수 꼬리를 더하면 비교 자체가 무의미해짐을 사례로 듦
- 더 흔한 예시로, 유효숫자 개념에선 10억 - 100만 = 10억이라고 해도 비약이 아님을 들어줌
- 5상태 튜링머신으로 증명 나열이 가능한 논리 체계 중 가장 "풍부한" 것은 무엇일까 궁금증 표시함
- 관측 우주가 BB(6)의 정확한 값을 적기에 충분히 클지 궁금증 제기
- 관측 우주를 닫힌 시스템으로 봤을 때, Bekenstein bound를 적용해 계산하면 정보 저장 한계는 약 10^120 비트 수준임. 현재 추정상 전체 질량-에너지가 대략 10^53kg이고, 이를 식에 대입해도 10^120 비트 내외임. 따라서 불가능함을 수치 근거와 함께 설명
- 우주에 저장 가능한 정보량이 약 10^120 비트이고, 단 억만 조 단위로 틀려도 아무 의미 없을 만큼 "당연히 부족"함을 강조
- 전체 값을 동시에 저장하는 상황을 가정한 것으로 추정됨. 동시성 조건이 없다면 무한 시간에 걸쳐 기록이 이론상 가능할 수도 있으나, 우주 열적 죽음 등 현실적 한계 고려 필요. CMB 기준 프레임에선 불가능하나, 다른 시공간 절단 개념을 생각해볼 수 있지 않을까 자문함
- 기사 내 첫 숫자부터가 이미 ¹⁵10, 즉 10^(¹⁴10)꼴이라, 자리수 자체가 ¹⁴10임을 감안하면 절대 불가능
- 불가함을 간단히 재확인
- 계산 복잡도 이론의 이런 결과들을 볼 때마다, "슈퍼 인공지능은 신이다"류의 유행 담론은 완전히 근거 없음을 실감함. 우주의 모든 원자를 슈퍼컴퓨터로 만들고 블랙홀 에너지까지 써도, BB(6)의 멈춤 상태를 계산하는 건 영원히 불가능함
- 저런 허수아비론(strawman)은 애초에 설득력이 없었다는 간결한 반응