BB(3, 3)는 왜 어려운가: Bigfoot

 (sligocki.com)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 3상태 3기호 튜링 머신 Bigfoot은 빈 테이프에서 정지 여부를 증명하려면 Collatz 유사 문제를 풀어야 하는 사례로, (BB(3, 3))도 그만큼 어려울 수 있음을 보여줌
  • 이 기계는 bbchallenge.org의 (BB(3, 3)) 미해결 후보 160개 중 하나이며, 전이표 1RB2RA1LC_2LC1RB2RB_---2LA1LA로 정의됨
  • 동작은 (A(a,b,c)) 구성의 반복 규칙으로 환원되며, (b \bmod 6)에 따라 a가 증가·감소하고 (a)가 0 아래로 내려가려 할 때만 정지함
  • 빈 테이프에서 69단계 후 (A(2,1,2))에 도달하고, 2,400만 번 반복한 뒤 (a = 3,999,888)까지 커져 정지 가능성이 실험적으로 매우 낮아 보임
  • (b \bmod 6) 수열은 결정적이지만 큰 흐름에서는 오른쪽 2/3, 왼쪽 1/3의 편향 랜덤 워크처럼 보이며, 영원히 실행됨을 증명하려면 이 Collatz 유사 함수가 정지 전이에 도달하지 않음을 보여야 함

Bigfoot이 (BB(3, 3))를 어렵게 만드는 이유

  • 3상태 3기호 튜링 머신 하나의 정지 여부를 증명하려면 Collatz 유사 문제를 해결해야 함
  • 따라서 (BB(3, 3)) 문제를 푸는 일은 이 Collatz 유사 문제를 푸는 것만큼 어려울 수 있음
  • Paul Erdős는 Collatz류 문제에 대해 “Mathematics may not be ready for such problems”라고 말한 바 있음
  • 이전 글 Mother of Giants에서는 “Beeping” Busy Beaver 탐색에서 발견된 튜링 머신 계열을 다뤘음
    • 해당 계열은 정지 유사 상태(quasihalt) 여부를 증명하려면 Collatz 유사 문제를 효율적으로 시뮬레이션하거나 완전히 풀어야 함
  • Bigfoot은 변형 게임이 아니라 일반 Busy Beaver 게임 안에서 발견된 사례임

기존 Busy Beaver 난해성 사례

  • 사람이 직접 만든 여러 튜링 머신은 특정 Busy Beaver 값을 증명하려면 다른 어려운 수학 명제를 증명해야 하는 사례를 제공함
    • (BB(745)): ZFC의 일관성 증명이 필요함
    • (BB(27)): Goldbach Conjecture 증명이 필요함
    • (BB(15))와 (BB(5,4)): (n > 8)일 때 (2^n)의 3진 표현에 적어도 하나의 숫자 2가 있다는 Erdős 추측 증명이 필요함
  • 다만 이런 Busy Beaver 값들은 현재 접근 가능한 범위 밖에 있음
  • 지난 60년 동안 증명된 값은 (BB(2), BB(3), BB(4), BB(2,3))뿐이며, (BB(6) > 10 \uparrow\uparrow 15)임이 알려져 있음
  • Bigfoot을 분석하기 전에는 (BB(3, 3))를 증명할 가능성이 있다고 여겨졌음

Bigfoot의 정의와 출처

  • 이 튜링 머신의 이름은 Bigfoot이며, 전이표는 다음 문자열로 정의됨
    • 1RB2RA1LC_2LC1RB2RB_---2LA1LA
  • bbchallenge에 등록된 기계임
  • 전이표는 다음과 같음
상태 0 1 2
A 1RB 2RA 1LC
B 2LC 1RB 2RB
C — 2LA 1LA
  • Bigfoot은 bbchallenge.org Discord 채널에서 공유된 (BB(3,3))의 남은 비공식 holdout 160개 중 하나임
  • 이 특정 튜링 머신은 2023년 10월 14일 같은 Discord 채널에서 @savask가 낮은 수준의 동작 설명과 함께 처음 공유함
  • 이후 분석에서 Collatz 유사 구조와 편향 랜덤 워크 성격이 드러남

(A(a,b,c)) 구성으로 환원되는 동작

  • 일반 구성을 다음과 같이 둠

[ A(a, b, c) = 0^\infty ; 12^a ; 11^b ; \text{ <A } ; 11^c ; 0^\infty ]

  • Bigfoot이 (c \ge 1)인 (A(a,b,c)) 구성에 들어가면, 아래 규칙들이 이후 동작을 정지할 때까지 또는 영원히 정확히 설명함

[ \begin{array}{l} A(a, 6k, c) \to A(a, 8k+c-1, 2) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+1, c) \to A(a+1, 8k+c-1, 3) \quad \text{if } 8k+c \ge 1 \ A(a, 6k+2, c) \to A(a-1, 8k+c+3, 2) \quad \text{if } a \ge 1 \ A(a, 6k+3, c) \to A(a, 8k+c+1, 5) \ A(a, 6k+4, c) \to A(a+1, 8k+c+3, 2) \ A(a, 6k+5, c) \to A(a, 8k+c+5, 3) \end{array} ]

[ A(0, 6k+2, c) \to \text{Halt}(16k+2c+7) ]

  • 이 규칙들은 (b)와 (c) 매개변수에 대한 Collatz 유사 함수를 반복함
  • (a)는 누적값처럼 움직임
    • (b \equiv 1 \pmod{6}) 또는 (b \equiv 4 \pmod{6})이면 (a)가 증가함
    • (b \equiv 2 \pmod{6})이면 (a)가 감소함
    • (a)가 0 아래로 감소하려는 경우에만 Bigfoot이 정지함

빈 테이프에서 관측된 궤적

  • 빈 테이프에서 시작하면 Bigfoot은 69단계 후 (A(2,1,2)) 구성에 도달함
  • 이후 시뮬레이션에서 (a)는 꾸준히 증가하는 것처럼 보이며, 2,400만 번 반복 후 (a = 3,999,888)이 됨
  • (b \bmod 6)의 나머지 수열이 균등 무작위라고 가정하면, 이 과정은 수직선 위의 편향 랜덤 워크와 같음
    • 각 단계에서 오른쪽으로 갈 확률은 (\frac{2}{3})
    • 왼쪽으로 갈 확률은 (\frac{1}{3})
  • Markov chain 이론에서는 현재 위치가 (a=n)일 때 미래에 (a=-1)에 도달할 확률이 ((\frac{1}{2})^{n+1})임을 증명할 수 있음
  • 실제 (b \bmod 6) 수열은 무작위가 아니라 완전히 결정적이며, 홀수·홀수·짝수·짝수 패턴을 일관되게 따름
  • 그럼에도 큰 규모에서는 랜덤 Markov chain과 비슷한 궤적을 보임
    • 2,400만 단계 후 Markov chain은 오른쪽으로 800만 번, 왼쪽으로 400만 번 이동할 것으로 기대됨
    • 이는 실제 (a) 값 약 400만과 매우 가까움

“Probviously” 정지하지 않는다는 휴리스틱

  • (a \approx 4,000,000)인 시점에서 랜덤 Markov chain이 (a=-1)에 도달할 확률은 대략 ((\frac{1}{2})^{4,000,000})임
  • 이 수치는 과학적으로는 실패가 보장된 것처럼 취급할 만큼 작음
  • Bigfoot이 Markov chain과 비슷하게 동작한다면 정지하지 않을 것으로 보임
  • 하지만 이는 엄밀한 수학 명제가 아니라 실험적 휴리스틱임
  • Bigfoot이 googolplex 번 반복한 뒤 정지할 가능성도 배제하지 못함
  • John Conway는 Collatz 추측이 “probviously” 참일 것이라는 휴리스틱을 설명하기 위해 이 표현을 만들었지만, Collatz 증명은 아직 보이지 않음

Bigfoot이 가질 수 있는 두 결말

  • Bigfoot은 둘 중 하나임
    • 정지함
    • 영원히 실행됨
  • 정지한다면 Collatz 유사 함수의 반복을 충분히 가속해 끝까지 시뮬레이션함으로써 증명할 수 있음
  • 영원히 실행된다면, 이 Collatz 유사 함수가 (a=0)의 정지 전이에 절대 도달하지 않는다는 사실을 증명해야 함
  • Markov chain 휴리스틱에 따르면 두 번째 경우가 더 그럴듯해 보이며, 이쪽이 훨씬 증명하기 어려워 보임

Cryptids라는 이름

  • 이런 종류의 기계는 비교적 단순한 수학 규칙으로 동작을 환원할 수 있지만, 그 규칙이 열린 수학 문제의 부류에 들어감
  • 정지하거나 정지하지 않는다는 소문만 있고 어느 쪽도 구체적 증거를 제시하지 못한 전설적 생물과 비슷함
  • 이런 기계들을 Cryptids라고 부르자는 이름이 제안됨
  • Loch Ness Monster나 Chupacabra 같은 전설적 생물과의 비유임
  • 이 튜링 머신은 무작위로 걷는 것처럼 보이기 때문에 Bigfoot이라는 이름이 붙음

이 Collatz 유사 동작은 정말 어려운가

  • 이 특정 Collatz 유사 함수의 동역학은 이전에 거의 분석된 적이 없는 문제로 보임
  • 약간의 정수론과 계산으로 이 문제에만 적용되는 영리한 수학적 성질을 찾을 가능성은 남아 있음
  • 그런 성질이 발견된다면 (BB(3,3)) 증명이 아직 접근 가능한 범위에 있음을 알 수 있음
  • Collatz 유사 문제에서 물을 수 있는 질문은 경험적으로 두 종류로 나뉨
    • 비교적 사소하게 증명되는 질문
    • 어떤 수학자도 증명법을 모르는 질문
  • Bigfoot에서 (b)가 홀수·홀수·짝수·짝수 패턴을 반복한다는 사실이나, 전통적 (3n+1) Collatz 규칙 적용 뒤 항상 짝수가 되어 다음 단계에서 2로 나뉜다는 사실은 첫 번째 범주에 속함
  • Collatz 시스템 동작에 관한 거의 모든 다른 질문은 두 번째 범주에 속하는 예로 볼 수 있음

81개 경우로 된 대안 표현

  • 2023년 10월 18일 추가된 대안 표현은 기존 (A(a,b,c)) 설명의 불편함을 줄임
  • 기존 설명에는 세 가지 불편함이 있음
    • (b)와 (c) 매개변수가 얽혀 있음
    • 입력 모듈로 6과 출력 모듈로 8이 공통 인수 2를 가짐
    • (b)가 홀수·홀수·짝수·짝수의 반복 패턴을 따름
  • Matthew House는 새 구성을 다음처럼 정의하면 이 문제들을 피할 수 있음을 지적함

[ B(a,b)=A(a,2b+1,2) ]

  • (b=81k+r)로 두고 원래 전이 4개를 하나의 전이로 묶으면, Bigfoot의 Collatz 유사 동작을 81개 경우의 규칙으로 표현할 수 있음
  • 이 표현은 기존 (A) 표현의 세 가지 특징을 해결하고 고전적 Collatz 문제와 더 비슷해 보임
  • 다만 81개 경우를 모두 다뤄야 하므로 다소 다루기 어려움
  • 일부 규칙은 (a \ge 2) 조건에 의존함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • BB(3, 3) 자체가 어렵다기보다, Collatz류 문제를 인코딩하고 있고 그런 문제들이 대체로 매우 어렵다고 보는 편이 더 정확해 보임
    다만 이 특정 인스턴스가 꼭 어려운지는 별개임. 동작이 꽤 한쪽으로 치우쳐 보이고, 고전적인 Collatz 문제처럼 모든 정수의 궤적을 다 봐야 하는 게 아니라 단일 궤적만 보면 되기 때문임

    • 제목에서 조금 단순화한 건 맞음. 글 첫 문단의 “BB(3, 3) 문제를 푸는 것은 적어도 이 Collatz 유사 문제를 푸는 것만큼 어렵다”가 더 정확한 표현임
      단일 궤적 대 여러 궤적이라는 점도 어느 정도 동의함. 다만 이 튜링 머신이 멈추지 않는 세계라고 가정하면, 이 시스템의 단일 궤적을 증명하는 일은 고전 Collatz 추측의 단일 궤적보다 “더 어렵다”고 볼 수 있음. Collatz 추측이 참이라면 임의의 단일 궤적 증명은 결국 유한 계산이면 되지만, 글의 단일 궤적은 영원히 멈추지 않음을 보여야 해서 더 세련된 수학이 필요함
      과장하고 싶지는 않음. 이것이 BB(3, 3)을 풀려면 Collatz 추측이나 이미 잘 연구된 수학의 열린 문제를 반드시 증명해야 한다는 뜻은 아님. 그래도 잘 연구된 문제와 닮은 어려운 문제라는 “차선의” 결과 정도로는 의미 있다고 봄. 이 Collatz 유사 문제가 얼마나 어려운지는 누가 풀 수 있는지 보면 될 듯함

  • 여기서 이해를 돕고 싶음. 748개 상태의 튜링 머신이 있고 [0], 이 머신은 ZFC가 모순일 때만 멈춘다는 것으로 이해함
    이 머신은 컴퓨터에서 구현해 실행할 수 있는 “물리적” 대상임. 현재 계산 능력은 부족하지만 원리적으로는 이 머신을 BB(748) 단계 동안 실행하는 걸 막는 것은 없음. 멈추면 정리 1에 의해 ZFC가 모순임을 증명한 것이고, 멈추지 않으면 ZFC가 일관적임을 증명한 것처럼 보임
    이게 혼란의 핵심임. 추상적인 결과가 아니라 실제로 수행하고 값을 얻을 수 있는 계산처럼 보임
    물론 Gödel의 제2 불완전성 정리에 따르면 ZFC 안에서는 ZFC의 일관성을 증명할 수 없음. 그런데 위 튜링 머신이 멈추면 ZFC가 일관적임을 증명한 것이 되어 모순처럼 보임
    어디가 틀렸을까? 현재 추측은 정리 1의 증명에서 748상태 튜링 머신이 ZFC가 모순일 때만 멈춘다는 것을 보이기 위해 ZFC보다 강한 메타이론을 썼다는 것임. 그렇다면 모순은 아님. BB(748) 단계 동안 돌릴 수는 있어도, 그건 ZFC+가 ZFC의 일관성을 증명한다는 것만 보여주며 이는 이미 알려져 있음. 예컨대 ZFC + “도달 불가능한 기수가 존재한다”가 그런 역할을 함
    논문을 자세히 보지는 않아서 실제로 그런지는 모르겠음. 이 문제를 깊게 생각해 본 사람이 통찰을 줄 수 있을까?
    [0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

    • 문제는 “튜링 머신을 BB(748) 단계 동안 실행한다”는 부분임. 우리는 BB(748)이 무엇인지 모름
      바쁜 비버의 신이 그 값을 알려준다면 이론적으로 그만큼 튜링 머신을 돌릴 수 있고, 말한 대로 ZFC의 일관성 여부를 증명할 수 있음. 하지만 인간이 BB(748)을 계산하려면 사실상 이 특정 748상태 튜링 머신이 언젠가 멈추는지, 그리고 다른 모든 748상태 튜링 머신이 멈추는지도 알아내야 함
    • 이건 우리가 수행할 수 있는 계산이 아님. 관측 가능한 우주에서 엔트로피를 증가시키는 데 쓸 수 있는 에너지를 다 써도 이 계산을 돌리기에 충분하지 않음
      우주의 모든 물질과 에너지를 써서 컴퓨터를 만들고, 그 컴퓨터가 이 작업 하나만 물리적으로 가능한 최고 효율로 수행해도 계산을 끝내지 못함
      그래서 수학이 물리와 현실에서 분리되는 지점이 생김. 그런 대상에 대해 말하고 추론할 수는 있지만, 더 이상 물리적 의미를 갖지는 않음
    • 위에서는 정확히 말했듯이 그 머신은 ZFC가 모순일 때만 멈춤. 중간에 방향을 반대로 뒤집은 듯하고, 그게 문제임
    • 멈춘다는 걸 증명하는 건 “쉬움”. 프로그램을 돌리고 몇백만 년 기다렸더니 멈추면 끝임
      하지만 멈추지 않는다는 걸 증명하는 건 훨씬 어려움. TREE(3) 단계만큼 실행해도 TREE(3)+1 단계에서 멈추지 않는다는 증명은 아님
      그래서 슬프게도 “그냥 돌리면 된다”고 할 수 없음
    • 그렇다면 BB(748)이 계산 불가능하면 어떻게 됨? 아니, 방금 그걸 증명한 셈 아닌가?

  • 글쓴이의 문체가 좋았음. 장황해 보이지 않으면서 주제를 이해하는 데 도움이 됐고, 그 균형점을 잡기는 쉽지 않음

  • 관련 자료: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... 및 https://googology.fandom.com/wiki/Googology_Wiki

  • BB가 계산 불가능하다는 말이 이런 뜻인가? BB가 커질수록 수학 전체를 품게 되고, 결국 모든 것을 증명해야 한다는 의미인지 궁금함

    • 어느 정도는 맞음. 계산 불가능한 함수는 정지 문제가 있기 때문에 존재함. 그래서 정의에 멈춤 여부가 포함되는 함수는 계산 불가능해짐. 예컨대 BB는 주어진 n과 m에 대해 어떤 튜링 머신들이 멈추는지 모두 판정해야 하므로 계산 불가능함
      나머지 수학 전체는 정지 문제를 통해 BB 안으로 밀반입됨. 임의의 수학 추측이 참이거나 거짓일 때만 멈추는 프로그램을 작성할 수 있으므로, 정지 문제나 BB를 풀려는 것은 모든 수학을 알아야 함[0]. 이는 튜링 완전성이 계산 가능성의 경계이기 때문에 가능함. 컴퓨터를 품을 수 있는 것은 그 자체로 컴퓨터임
      [0] 사실 이것 자체가 정지를 결정 불가능하게 만드는 이유는 아님. 결정 불가능성은 가상의 정지 판정기가 자신이 멈추지 않는다고 말할 때만 멈추는 식으로, 프로그램이 “자기 자신을 정지 문제 안으로 끌어들이는” 데서 나옴
    • 어느 정도 맞음
      우리가 증명도 반증도 할 수 없다고 “아는” 수학 문제가 있음. 모든 명제를 참이면서 거짓으로 증명할 수 있는 경우가 아니라면 그렇다는 것이 Gödel의 제1 불완전성 정리임. 모든 명제를 참과 거짓으로 모두 증명할 수 있다면 그 증명 체계는 쓸모없고, 증명한다는 것이 아무 의미가 없으므로 그런 일이 없는 다른 증명 체계를 골라야 함. 그래서 보통은 첫 번째 경우, 즉 증명도 반증도 못 하는 문제가 있다고 가정함. 덧붙이면 Gödel의 제2 불완전성 정리는 우리가 첫 번째 경우에 있다는 것 자체를 결코 증명할 수 없다는 내용임
      그리고 BB가 계산 불가능하다는 것은 BB가 커지면 언젠가 증명도 반증도 못 하는 문제가 참일 때만 멈추는 프로그램을 인코딩할 수 있다는 뜻임. 그래서 그 프로그램이 멈추는지 멈추지 않는지 증명할 수 없음
      엄밀히 말하면 증명도 반증도 못 하는 것을 증명하거나 반증하는 일은 거짓을 증명하는 셈이고, 이는 결국 모든 명제를 “증명”하는 데 쓰일 수 있으므로 “수학 전체를 포괄한다”는 말은 어떤 의미에서는 맞음. 다만 이는 임계 조건이고, “모든” 수학 문제를 인코딩할 만큼 큰 튜링 머신이 나오기 훨씬 전에 작동함. 실제로 모든 수학 문제를 인코딩하기에 충분한 유한한 상태 수는 없음. 산술 문자열을 계속 더 길게 만들 수 있기 때문임
    • 크게 단순화하면, 계산 가능성에서 가장 중요한 결과는 정지 문제임. 어떤 프로그램이 어떤 입력에서 멈출지 영원히 실행될지 일반적으로 판정할 방법이 없다는 뜻임
      그 다음에는 우리가 풀 수 없는 BB가 존재한다는 게 놀랍지 않고, 어떤 BB는 풀 수 있고 어떤 BB는 풀 수 없는지 조사하는 일이 흥미로워짐
    • BB가 계산 가능한 함수라면, n개 상태를 가진 모든 튜링 머신을 BB(n) 단계만큼 실행해서 정지 문제를 풀 수 있음. 그때까지 멈추지 않은 것들은 전혀 멈추지 않는 것임

  • “따라서 BB(3, 3) 문제를 푸는 것은 적어도 이 Collatz 유사 문제를 푸는 것만큼 어렵다”는 부분이 왜 놀라운지 모르겠음. 사실 거의 자명하게 증명되는 것처럼 보임. 모든 BB(x, y) 문제가 Collatz류 문제로 환원되는 것 아닌가?
    BB(x, y)는 정지 문제로 쉽게 바꿀 수 있음. x개 상태와 y개 기호를 가진 모든 머신 중 멈추는 것들을 찾고, 멈추지 않는 것들은 따로 둠. 그다음 멈추는 머신들을 모두 한 단계씩 함께 실행해서 전부 멈출 때까지 돌리면, 실행한 단계 수가 BB(x, y) 값이 됨
    Conway가 정지 문제를 Collatz류 문제로 환원하는 방법을 제시한 것으로 알고 있음. 그렇다면 BB에서 정지 문제로, 다시 Collatz 문제로 가는 두 단계 환원으로 임의의 x, y에 대한 BB(x, y)를 Collatz류 문제로 줄일 수 있어 보임

    • 방향을 반대로 잡은 것 같음. 여기서는 B(x,y)를 정지 문제로 환원했으므로, 정지 문제의 일부가 B(x,y)만큼 어렵다는 것만 보임
      필요한 것은 Collatz에서 정지 문제로, 다시 B(x,y)로 가는 환원임. Collatz에서 정지 문제로 가는 건 자명하지만, 정지 문제에서 B(x,y)로 가는 건 덜 자명함. Collatz에서 환원될 수 있으면서도 B(3,3)보다 어렵지 않은 정지 문제의 부분집합이 무엇인지 정확히 정의해야 함

  • 정지 문제는 계산 가능한 프로그램에 기반한 알고리즘 정보 이론과 귀납의 많은 접근을 자주 “막는” 것처럼 보임. 그런데 정지 문제가 실제 세계의 귀납 능력에 물질적인 영향을 주는지에 대한 연구가 있는지 궁금함
    예를 들어 어떤 오라클이 임의의 단조 보편 튜링 머신이 실행 중 더 이상 출력 테이프에 아무것도 쓰지 않을 지점에 도달했는지 알려준다고 하자. 이 오라클을 써서 하는 귀납 결과가, 프로그램 공간을 완전 탐색하다가 어떤 프로그램이 충분히 큰 n단계 동안 출력을 내지 않으면 그냥 다음 프로그램으로 “넘어가는” 방식과 크게 달라질까?
    BB(3,3)처럼 일부러 만든 경계 사례나 적대적 예시가 아니라, “평범한” 압축 가능한 데이터에 대한 귀납을 말하는 것임

    • 수학 교육을 제대로 받은 사람은 아니라서 이 답이 질문과 정말 관련 있는지는 확신할 수 없지만, 그래도 적어봄
      보안 연구자로서 직접 퍼저(fuzzer) 를 작성함. 퍼저는 테스트 대상 프로그램에 보안상 의미 있는 입력을 자동으로 찾는 도구임. 입력을 알고리즘적으로 생성하고 변형해서 프로그램에 넣고, 초당 수십·수백·수천 번씩 무슨 일이 벌어지는지 관찰함
      어떤 입력이 프로그램을 크래시시키면 이를 프로그램을 “멈추게” 한 것으로 볼 수 있음. 어떤 프로그램에 대해서든 모든 버그를 현실적인 시간 안에 찾는 퍼저를 만들려면 정지 문제를 풀어야 할 것 같음. 실제로 수십억 번 테스트해도 이미지 디코더에서 여전히 버그를 찾아내는 사람이 있으니, 우리가 가진 퍼저가 완벽하지 않은 건 맞음
      동시에 현실에서는 퍼저가 충분한 시간을 주면 복잡한 프로그램 내부로 예상보다 깊이 침투하는 것도 봤음. 테스트 대상이 수행하는 입력 검증, 현대 PC의 제한된 메모리와 저장공간이 퍼저를 어느 정도 궤도 위에 올려줌. 단 암호학이 끼면 예외인데, 퍼저에게는 계산적 타르 구덩이와 같음. 잘 방어되고 잘 명세된 프로그램은 퍼저가 정지 문제를 풀 필요가 없도록 자체적인 가드레일 역할을 함
      그래서 프로그램의 보안 버그 탐지에 관해서는 이렇게 보게 됨. 암호학을 제외하면 퍼저는 엄격한 입력 검증을 하는 프로그램을 겨냥하는 데 강함. 반대로 엄격한 입력 검증을 하지 않는 프로그램에는 퍼저가 굳이 필요하지 않으며, 그런 곳에서는 퍼저가 반드시 잘 작동하지도 않음
    • 의도한 뜻이 맞는지는 모르겠지만, 실제로는 계산 불가능한 문제와 이론적으로는 완전히 계산 가능하지만 현실적으로 너무 느려 계산할 수 없는 문제 사이에 차이가 없음

  • BBB, 즉 삐 소리 내는 바쁜 비버가 왜 준정지 전에 훨씬 더 오래 실행될 수 있는지 직관이 있을까?
    보이는 한 가지는 사실상 정지 상태를 쓸 필요가 없다는 점임. 그런 의미에서 3상태 BBB는 4상태 BB와 비슷할 수도 있음. 그 외에 더 있는지 궁금함

    • 프로그램은 한 번만 멈출 수 있지만, 삐 소리는 몇 번이든 낼 수 있음
      그래서 크기 X인 프로그램이나 튜링 머신이 크기 Y, 단 Y >> X인 모든 프로그램을 실행하는 것을 시뮬레이션하게 만들 수 있음. 그 프로그램들 중 하나가 멈출 때마다 삐 소리를 내게 하면, 마지막 삐 소리는 BB(Y)가 BB(Y)보다 더 많은 단계 뒤에 멈추는 것을 시뮬레이션할 때 발생함. 따라서 BBB(X) > BB(Y) >> BB(X)가 됨
      기억이 맞다면 기본적으로 같은 구성 때문에, BB(N)을 알면 크기 N 이하 프로그램의 정지 문제를 매우 느리게 계산할 수 있는 반면, BBB(N)을 알면 그 크기 이하의 정지 오라클이 주어진 튜링 머신에 대한 정지 문제를 훨씬 더 느리게 계산할 수 있음

  • 이건 나한테 너무 너드한 내용임
    이런 걸 이해하려면 어떤 사전 지식이 필요한지 궁금함. 기본 미적분만 알아도 충분한가? 어떤 구체적인 주제나 과목이 좋은 기초가 될까?

    • 바쁜 비버 수에 대한 정말 접근성 좋은 소개는 이 글임
      [1] https://www.scottaaronson.com/writings/bignumbers.html
    • 이 주제는 정확히 이론 컴퓨터 과학에 속함
      입문 이론 컴퓨터 과학 교재를 따라가면 대부분 이해하는 데 도움이 됨. 컴퓨터 과학 전공 학생들은 보통 1~2학년에 배우고, 쉽지는 않음. 우리 학교에서는 가장 두려운 시험 중 하나였음
    • 미적분보다는 이산수학과 자동자 이론 https://en.m.wikipedia.org/wiki/Automata_theory 또는 계산 이론에 가까움
      Hopcroft & Ullmann의 입문서가 좋음. 다만 관련된 내용이 워낙 많아서 출발점에 가깝다고 보면 됨
    • 미적분은 이런 종류의 문제와 거의 관련이 없음. 글을 이해하려면 이론 컴퓨터 과학, 특히 계산 가능성 이론을 공부하는 게 좋음
      많은 컴퓨터 과학 학부 과정에 공개 자료가 있는 강의가 있을 것임
    • 계산 이론, 정수론, 확률론이 좋은 출발점임

  • 1RB2RA1LC_2LC1RB2RB_---2LA1LA는 어떻게 읽어야 하나?

    • 상태 전이표임. 글 바로 아래에 펼친 형태가 나오고, 여기에서도 볼 수 있음
      https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
      예를 들어 상태 B이고 현재 머리 위치의 테이프 값이 0이면, 2를 쓰고 머리를 왼쪽으로 한 칸 이동한 뒤 상태 C로 감
    • 더 읽기 쉬운 상태표가 따로 있지만, 각 밑줄은 한 기호에 대한 전이 묶음을 구분하고, 각 전이는 3글자씩 묶여 있음
      3글자는 쓸 기호, 새 상태, 이동 방향을 뜻함. --- 상태는 정지임
    • 글의 링크 [0]를 누르면 사람이 읽기 쉬운 표로 펼쳐진 페이지가 나옴. 현재의 (상태, 테이프 값) 쌍마다 (새 테이프 값, 테이프 머리 이동 방향, 새 상태) 삼중항으로 매핑됨
      [0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
답변달기