BusyBeaver(6)은 정말 큼

• BB(6) 의 알려진 하한이 다시 크게 올라가며, 6상태 튜링 머신의 최대 정지 시간이 관측 가능한 현실의 규모를 훨씬 넘어서는 수임이 확인됨
• BB(6)은 0으로 채워진 테이프에서 시작하는 6상태·2기호 튜링 머신이 정지 전까지 실행할 수 있는 최대 단계 수를 뜻함
• 2022년 Pavel Kropitz의 개선 이후, mxdys가 하한을 10을 1,000만 번 반복 거듭제곱한 수보다 큰 수준으로 다시 끌어올림
• 최신 결과는 BB(6)이 2 pentated to 5 이상임을 보이며, 반복 거듭제곱보다 한 단계 더 높은 연산까지 등장함
• BB(5)는 47,176,870으로 결정됐지만 BB(6)은 압도적으로 커져, BB(n)이 ZFC 공리계와 독립이 되는 지점이 n=7, 8, 9일 수 있다는 추정으로 이어짐

---

BB(6)의 하한이 다시 커짐

• 2022년 전에는 BB(6)에 대해 BB(6) > 10^36,534 정도만 알려져 있었고, Pavel Kropitz가 이를 10을 15번 반복 거듭제곱한 수보다 큰 수준으로 개선함
• 테트레이션(tetration) 은 반복 거듭제곱을 뜻함
  • 예를 들어 10을 15번 쌓은 수는 10의 10의 10의 … 형태가 15번 이어지는 수임
• BBchallenge 조직자 Tristan Sterin은 팀 멤버 mxdys가 BB(6) 하한을 다시 높였다고 알림
  • 첫 개선: BB(6) > 10을 1,000만 번 반복 거듭제곱한 수
  • 이 결과에는 Coq 정확성 증명이 있음
• mxdys의 이후 개선은 BB(6)이 2 tetrated to 2 tetrated to 2 tetrated to 9 이상임을 보임
  • 특히 BB(6)은 2 pentated to 5 이상임
  • 펜테이션(pentation)은 반복 테트레이션으로, 테트레이션이 거듭제곱을 반복하는 것보다 한 단계 더 높은 연산임

BB(5)와 BB(6)의 극단적 차이

• BB(6)은 6번째 Busy Beaver 수임
  • 6상태 튜링 머신을 대상으로 함
  • 알파벳은 {0,1}
  • 입력 테이프는 처음에 모두 0
  • 정지하기 전까지 가능한 최대 실행 단계 수를 뜻함
• 국제 BBchallenge 팀은 지난해 BB(5)를 47,176,870으로 결정함
• BB(5)에서 BB(6)으로 넘어가는 사이 Busy Beaver 함수는 수천만 단위에서 관측 가능한 현실의 범위를 넘어서는 크기로 도약함

크기 감각이 거의 통하지 않는 수

• BB(6) > 10을 1,000만 번 반복 거듭제곱한 수였던 시점에도 직관적 설명은 거의 불가능했음
• 예컨대 그만큼의 모래알이 있다면, 관측 가능한 우주의 복사본을 대략 같은 수만큼 채울 수 있다고 비유함
• 이 비유는 해당 수가 10^100 같은 우주적 규모의 수보다도 압도적으로 크기 때문에, 나눗셈을 해도 원래 수와 거의 같은 규모로 남는다는 점을 보여줌

ZFC 독립성 추정이 낮아질 가능성

• BB(6)이 이렇게 커졌다고 해서 Busy Beaver 함수에 대한 모든 생각이 바뀐 것은 아님
• BB(6)이 10^36,534 같은 상대적으로 작은 수준이 아니라 반복 연산의 영역에 있을 가능성은 원래도 열려 있었음
• 실제 하한이 그런 규모로 확인되면서, BB(n)의 값이 ZFC 집합론 공리계와 독립이 되는 지점에 대한 추정이 낮아질 수 있음
  • 이전에는 n=20이나 30 근처를 생각할 수도 있었음
  • 이제는 n=7, 8, 9일 수도 있다고 봄
• 현재 알려진 ZFC 독립성 결과는 BB(n)이 n=643에서 ZFC와 독립이 된다는 수준임

별도 업데이트: STOC 2025

• STOC 2025가 열린 Prague에서 여러 연구자들을 만나고 새로운 내용을 접함
• STOC plenary lecture 제목은 The Status of Quantum Speedups임
• 관심 있는 독자는 해당 강연의 PowerPoint slides를 확인할 수 있음

[GN⁺]

Hacker News 의견들

• bbchallenge Discord 서버에서는 최신 BB(6) 챔피언이 달성한 2^^2^^2^^9보다 훨씬 큰 Graham's Number를 넘기려면 튜링 머신 상태가 몇 개나 필요할지 활발히 추측 중임
  functional busy beaver https://oeis.org/A333479를 보면 Graham 수준의 동작이 의외로 빨리 나타날 수 있음. 49비트 람다 항이면 충분함
  그 크기 이하의 닫힌 람다 항은 77,519,927,606개뿐인데 https://oeis.org/A114852, 고유한 6상태 튜링 머신은 4^12*23836540=399910780272640개임 https://oeis.org/A107668
  6상태만으로 펜테이션을 달성했으니, 이제는 7상태면 Graham's Number를 넘길 수 있다고 보는 사람이 여럿 있음. 그래도 나는 여전히 꽤 놀라운 일이라고 봄. 며칠 전 그중 한 명과 향후 10년 안에 BB(7)>Graham's 증명이 나올지에 대해 큰 내기를 했는데, 다들 어떻게 보는지 궁금함

  • 전문가인 척할 수는 없지만, BB(7) 은 아마 Graham's Number보다 클 것 같음
    BB는 어떤 계산 가능한 수열보다도 빠르게 커져야 함. 이것이 BB(7)에 대해 구체적으로 뭘 뜻하는지는 결국 손짓 설명에 가깝지만, 연산자 강도의 사다리를 아주 빠르게 올라야 한다는 느낌임. 결국 우리가 정의하는 어떤 계산 가능한 연산자보다도 빨리 커져야 하며, 예컨대 up-arrow^n이나 계산 가능한 함수 f에 대한 up-arrow^f(n)도 포함됨
    직감적으로는 47 million에서 2^^2^^2^^9로 가는 성장이, 2^^2^^2^^9에서 Graham's Number로 가는 성장보다 필요한 연산자 강도 면에서 질적으로 더 커 보임. Graham's Number는 g_64이고 여기서 g는 대략 up_arrow^n보다 한 단계 위에 있는 것이라, 아마 BB(7)>Graham's Number일 가능성이 큼

• BB(748) 같은 수, 그것도 계산 불가능한 수가 “ZFC와 독립”일 수 있다는 게 머리를 어지럽게 함. 뭔가 범주 오류처럼 느껴짐

  • BB(748) 을 ZFC와 독립적으로 만드는 것은 그 값 자체가 아니라, 748상태 기계 중 하나인 TM_ZFC_INC가 ZFC 안의 모순, 즉 FALSE의 증명을 찾고 그것을 발견했을 때만 정지하도록 되어 있기 때문임
    따라서 BB(748)=N이라는 증명은 TM_ZF_INC가 N단계 안에 정지함을 보이거나, 절대 정지하지 않음을 보여야 함. ZFC가 일관적이라고 가정하면, 괴델의 유명한 결과 때문에 둘 다 불가능함
  • 계산 불가능한 것은 BB(n) 임. 즉 임의의 n에 대해 BB(n) 값을 출력하는 알고리즘이 없다는 뜻임
    BB(748)은 계산 가능함. 정의상 748개 상태를 가진 어떤 튜링 머신이 적어내는 1의 개수이고, 그 기계가 BB(748)을 계산함
    수 자체는 말 그대로 상상할 수 없을 만큼 큰 정수일 뿐임. ZFC 독립성은 이 수가 우리가 찾는 그 수임을 증명하려 할 때 들어옴. 그러려면 748상태 튜링 머신의 성질을 포착할 수 있는, ZFC보다 강한 이론이 필요함
  • 오히려 ZFC 공리처럼 냅킨에 넉넉히 들어갈 정도의 짧은 텍스트가 산술적 진리나, 인류의 활동과 주로 관련된 물리적 현실의 측면을 포착하기에 “충분”할 거라고 생각했다는 점이 더 놀라움
    6상태 튜링 머신의 동작이 몇 줄짜리 텍스트로는 예측 불가능할 수 있다는 건 전혀 놀랍지 않음
    괴델이 첫 번째 불완전성 정리를 발표하자마자 수학계 전체가 더 많은 공리를 찾는 데 전속력으로 달렸을 줄 알았음. 그런데 거의 한 세기 동안 괴델의 작업은 주류 프로그램이라기보다 기초론의 좁은 영역에 머무는 기묘한 사실처럼 취급된 편임. Feferman, Friedman 등을 알고는 있지만, 이 분야 연구는 수학의 대부분 다른 주제에 비해 훨씬 적음
  • 수 자체가 ZFC와 독립인 것은 아님. 모든 정수는 ZFC에서 표현 가능함. ZFC와 독립인 것은 BB(748)을 계산하는 과정임
  • 개별 숫자 자체는 계산 불가능하지 않음. 어떤 숫자와 ZFC 안의 증명 쌍으로, 그 숫자가 BB(748)의 값이라고 입증되는 것은 없음
    따라서 ZFC가 BB(748) 값을 출력한다고 증명할 수 있는 프로그램도 없음. 하지만 다른 모든 수와 마찬가지로 BB(748)을 출력하는 프로그램 자체는 존재함

• BB(14) 가 Graham's Number보다 크다는 것은 알려져 있지만, 이번 결과를 보면 BB(7)도 아마 Graham's Number보다 클 것 같음
  직관적으로는 펜테이션에서 Graham's Number로 가는 데 필요한 기술이, 47,176,870에서 2 5로 가는 데 필요한 기술보다 더 단순하게 느껴짐

• 왼쪽 위첨자가 테트레이션, 즉 반복 거듭제곱을 뜻한다는 설명을 보고 처음엔 오타인 줄 알았음. 테트레이션을 처음 접함

  • 예전에도 본 적은 있는데, 그때는 쉽게 일반화되는 점이 마음에 드는 Knuth의 위화살표 표기법을 썼음 https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
  • 반복이라는 흐름을 이어가면, 나는 이번에 펜테이션을 처음 접함

• “10,000,000sub10개의 모래알이 있다고 상상해보라. 그러면 관측 가능한 우주 10,000,000sub10개 정도를 그 모래로 채울 수 있다”는 부분이 이해가 안 됨
  정말 관측 가능한 우주의 부피를 평균 모래알 부피로 나눈 값을 반올림해 없애는 건가? 그건 보통 비교에 쓰는 우주의 총 질량보다도 훨씬 많은 자릿수 차이임

  • 맞음. 그 비율로 나누는 것은, 이 표기법에서 ‘인접한’ 수들이 훨씬 더 큰 변화를 만들기 때문에 사실상 거의 영향을 주지 않음
    10↑↑10,000,000 / (우주 하나당 모래알 수)는 예컨대 10↑↑9,999,999보다도 압도적으로 큼
    이런 수를 쓰는 체계에서는 (아주 큰 수)/(우주적 규모에 불과한 수)를 정확히 그렇게 쓰는 것 말고 더 나은 표현이 거의 없고, 아주 큰 수 쪽 표기에서는 결국 거의 (아주 큰 수)로 반올림됨
  • 테트레이션에서는 더 이상 자릿수의 규모를 다루는 게 아니라, 자릿수 규모의 자릿수 규모를 다루게 됨
  • 이런 비교의 더 흔한 예로, 유효숫자로 보면 10억에서 100만을 빼도 10억임
  • 정확함. 이 수는 10^100000이나 모래알이 몇 개 들어가느냐 같은 양보다 너무나도 커서, 그만큼 나누더라도 사실상 변하지 않음. 적어도 9,999,999sub10에 가까워질 만큼 내려가지는 않음
  • 맞음. 그건 평범한 수만큼의 자릿수 차이에 불과함. 10,000,000^10,000,000만 해도 이미 그 정도는 중요하지 않을 만큼 큰데, 하물며 지수 자체를 아홉 번 더 거듭제곱한 뒤라면 더더욱 그렇음

• Scott Aaronson의 How Much Math Is Knowable? [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
  몇 달 전 HN에도 올라왔음: https://news.ycombinator.com/item?id=43776477

• 5상태 튜링 머신만으로 증명을 열거할 수 있는 가장 풍부한 논리는 무엇일까?

  • 그 질문은 무엇을 열거로 볼지에 따라 달라지지만, 관련된 질문으로 “모든 5상태 튜링 머신의 정지 여부를 증명하지 못하는 가장 풍부한 논리는 무엇인가?”가 있음. 즉 어떤 5상태 튜링 머신의 정지 여부가 독립인 가장 풍부한 논리가 무엇인지 묻는 것임
    이 버전은 좀 생각해봤지만, 1차 논리에 대한 전문성이 부족해서 멀리 가지 못했음. 내가 아는 바로는 Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA이 수학적으로 비정지를 증명하기 가장 어려운 기계 중 하나라서 https://arxiv.org/abs/2407.02426, Skelet #17이 정지하지 않음을 증명할 수 있는 이론이라면 나머지 5상태 기계들도 판정할 가능성이 큼
  • 유한한 이진 문자열을 논리 증명의 열거로 어떻게 해석할지에 전적으로 달려 있음

• “BB(6)는 여섯 번째 Busy Beaver 수, 즉 {0,1} 알파벳을 가진 6상태 튜링 머신이 처음에 전부 0인 테이프에서 실행될 때 정지하기 전까지 취할 수 있는 최대 단계 수”라는 설명을 보고, 비전문가인 나에게는 오히려 너무 잘 이해됐다는 식으로 느껴짐
  이건 수십 년 동안 이런 연구를 해온 사람들을 위한 하드코어 블로그가 분명함. 특정 독자를 위해 거리낌 없이 밀도 높고 전문용어 가득하게 쓰인 글을 우연히 만나는 게 꽤 멋짐

  • 학부 컴퓨터과학 교육을 받은 사람이라면 Busy Beaver 문제를 처음 접했더라도 대략 무슨 일인지 감은 잡을 수 있을 정도의 설명임
    틈새 전문용어인 건 맞지만, 수십 년을 투자한 사람만 접근 가능하다고 보는 건 스스로를 과소평가하는 것임
  • 저 정의는 표준적인 학부 컴퓨터과학 이론 내용임. 다만 소프트웨어 엔지니어링에서는 표준이 아닐 수 있음

• 그렇게 큰 수는 사람이 시각화할 수 없음. 수를 표현하는 방식은 단순히 세는 것만 있는 게 아님
  예를 들어 모래알 하나도 가능한 상태가 무한히 많다고 볼 수 있음. 실수는 무한히 많으니, 모래알 하나가 BB(6)을 표현할 수 있다고 말할 수도 있음. 조합은 지수적으로 커질 수 있으니, 그런 방식이 표현에 유용할지도 모름

  • 어느 순간부터 큰 수는 “큰 양”이라기보다 형식 체계의 일관성 강도에 훨씬 가까워짐
    즉 어떤 체계가 들키기 전까지 얼마나 잘 모순적이지 않은 척할 수 있느냐의 문제임. BB(3)을 통해 일관성을 가장하는 모순적 체계는 BB(6)을 통해 일관성을 가장하는 체계보다 훨씬 빨리 “들통남”. 여기서 일관성을 가장한다는 건 어떤 n에 대해 BB(n)단계보다 오래 실행되는 모든 프로그램은 정지하지 않는다고 주장하는 것을 뜻함
  • 우주가 가장 가까운 플랑크 단위로 반올림된다면, 모래알 하나가 가질 수 있는 상태는 갑자기 그리 많지 않게 됨
    무한 정밀도를 끌어와 다루기 쉬워 보이게 만드는 건 내 기준에서는 손기술에 가까움. 규모를 설명할 때는 정수를 쓰는 편이 좋음
  • 이 예시는 헷갈림. 모래알 수와 관측 가능한 우주 수가 같다면, 우주 하나당 모래알 하나라는 뜻 아닌가?

• 관측 가능한 우주가 BB(6) 의 정확한 값을 적을 만큼 충분히 큰지 궁금함

  • 관측 가능한 우주를 닫힌계로 보면 Bekenstein 한계를 적용해볼 수 있음
    R ≈ 46.5 billion light-years, 즉 관측 가능한 우주의 반지름을 쓰고, E ≈ 관측 가능한 우주의 총 질량-에너지 함량을 사용함
    질량-에너지에는 보통 물질, 암흑 물질, 암흑 에너지가 포함됨. 현재 추정으로 관측 가능한 우주는 대략 10^53 kg의 질량-에너지 등가량을 가짐
    이를 S ≤ 2πER/ℏc에 넣으면 최대 정보량이 대략 10^120 bits 수준으로 나옴
    S ≤ 2πER/ℏc
S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
S ≤ 2.654135e+124
S ≤ 10^120
    그래서 불가능함
  • 확실히 충분하지 않음. 우주에 저장할 수 있는 정보량은 대략 10^120비트 정도임. 설령 내가 1조 자릿수만큼 틀렸더라도 결과는 달라지지 않음
  • 글에서 시작 숫자만 해도 ¹⁵10임. 이는 10^(¹⁴10)이라는 뜻이고, 따라서 자릿수가 ¹⁴10개임. 그러니 적을 수 없음
  • 아마 완전한 표현의 모든 부분이 동시에 존재하는 상태를 말하는 것 같음. 동시에 존재할 필요가 없다면, 우주의 지속 시간이 무한할 경우 “적어내는” 것이 가능할지도 모름. 열죽음이 여기에 어떻게 작용하는지는 모르니 “가능할지도”임
    하지만 상대론적 시공간에서는 “동시에”라는 말이 잘 정의되지 않음. 형제 댓글들은 우주 마이크로파 배경복사가 암시하는 기준계에서는 확실히 맞음. 다만 어떤 기준계에서는 “동시에” 표현이 가능해지도록 시공간을 자르는 방식이 있을 수 있지 않을까 궁금함