BusyBeaver(6)은 정말 큼

• 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 행사에 참석하여 다양한 연구자들과 교류하고 새로운 정보를 얻었음
• 자신의 양자 가속화 현황에 대한 기조 강연 슬라이드도 공유함
• 이 내용에 대한 보다 자세한 후기는 추후 공유 예정임