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까지 도달하는 것보다 오히려 단순하다고 느낌.
"좌상단 첨자"가 테트레이션, 즉 반복 거듭제곱임을 알림. 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상태 튜링머신으로 증명 나열이 가능한 논리 체계 중 가장 "풍부한" 것은 무엇일까 궁금증 표시함
어떤 기준으로 '나열'을 정의하느냐에 따라 답이 달라질 수 있음. 관련된 질문인 '5상태 튜링머신의 멈춤 여부를 다 증명하지 못하는 가장 강력한 논리 체계는 무엇인가?'도 의미 있음. Skelet #17 [0]이 멈추지 않음을 수학적으로 증명하는 게 매우 어렵기에, 이를 증명하는 이론이 있다면 나머지 5상태 튜링머신도 모두 결정할 수 있을 것 같다는 개인적 견해 공유 (0, 1)
유한 이진 문자열을 논리 증명 나열로 해석하는 방식부터 명확히 해야 전제를 논의할 수 있음
관측 우주가 BB(6)의 정확한 값을 적기에 충분히 클지 궁금증 제기
관측 우주를 닫힌 시스템으로 봤을 때, Bekenstein bound를 적용해 계산하면 정보 저장 한계는 약 10^120 비트 수준임. 현재 추정상 전체 질량-에너지가 대략 10^53kg이고, 이를 식에 대입해도 10^120 비트 내외임. 따라서 불가능함을 수치 근거와 함께 설명
우주에 저장 가능한 정보량이 약 10^120 비트이고, 단 억만 조 단위로 틀려도 아무 의미 없을 만큼 "당연히 부족"함을 강조
전체 값을 동시에 저장하는 상황을 가정한 것으로 추정됨. 동시성 조건이 없다면 무한 시간에 걸쳐 기록이 이론상 가능할 수도 있으나, 우주 열적 죽음 등 현실적 한계 고려 필요. CMB 기준 프레임에선 불가능하나, 다른 시공간 절단 개념을 생각해볼 수 있지 않을까 자문함
기사 내 첫 숫자부터가 이미 ¹⁵10, 즉 10^(¹⁴10)꼴이라, 자리수 자체가 ¹⁴10임을 감안하면 절대 불가능
불가함을 간단히 재확인
계산 복잡도 이론의 이런 결과들을 볼 때마다, "슈퍼 인공지능은 신이다"류의 유행 담론은 완전히 근거 없음을 실감함. 우주의 모든 원자를 슈퍼컴퓨터로 만들고 블랙홀 에너지까지 써도, BB(6)의 멈춤 상태를 계산하는 건 영원히 불가능함
Hacker News 의견