▲

GN⁺: BB(3, 4) > Ack(14) 결과

 (sligocki.com)
1P by neo 6달전 | favorite | 댓글 1개

BB(3, 4) > Ack(14)

  • 2024년 5월 22일
    • Pavel이 3상태 4기호 튜링 기계(Turing Machine, TM)를 발견했음
    • 이 기계는 "Ackermann 수준" 함수를 계산하고 정확히 (2↑155)+14개의 비제로 기호로 종료함
    • Knuth 상향 화살표 표기법이 다소 불편해져서 이를 다음과 같이 근사할 수 있음: BB(3,4)>Ack(14)
    • 여기서 Ack(14)는 14번째 Ackermann 수로 정의됨: Ack(n)=n↑nn
    • 이 기계는 "야생에서" 발견된 최초의 Ackermann 수준 함수를 시뮬레이션할 수 있는 TM임

기계

  • 상태 전이 표

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3LB | 1RZ | 2RA |
| B   | 2LC | 3RB | 1LC | 2RA |
| C   | 3RB | 1LB | 3LC | 2RC |

  • 최종 구성

    • 0∞32g153(0)+12161 Z> 0∞
    • 정확히 σ=2g153(0)+18=(2↑155)+14개의 비제로 기호가 테이프에 남음

Attribution

  • 발견자
    • 이 TM은 Pavel Kropitz(@uni)에 의해 발견되었고, 2024년 4월 25일 Discord에서 공유됨
    • 그의 코드는 TM 점수에 대한 인간이 읽을 수 있는 경계를 지정할 수 없었고, 단순히 Halt(SuperPowers(13))로 지정됨
    • 그는 새로운 "유도 증명 검증기"를 사용하여 이 결과를 검증하기 시작함
    • 2024년 5월 20일에 정확한 gkn(m)의 정의를 추출하고 σ>2↑153의 경계를 얻음
    • Matthew House(@LegionMammal978)는 2024년 5월 22일에 gkn(0)=2↑k(n+2)2−2의 간단한 닫힌 형식을 발견함

분석

  • B(k,n,m) 정의

    B(k,n,m)=0∞32m+12k A> 1n

  • 증명

    0∞A>0∞→241B(16,3,0)20∞
B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
B(k,0,m)2→10∞32m+12k1Z>

  • gk(m) 정의

    g0(m)=m+1
gk+1(m)=gk2m+2(0)

이중 유도에 의한 증명

  • 주요 규칙

    B(k,n,m)→B(k,0,gk−1n(m))

  • Lemma 1

    For all k≥1: 32k<B→2k+12k<B1

  • Corollary 2

    For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m

  • Theorem 3

    For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))

정확한 값

  • Theorem

    For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)

  • Corollary

    For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)

  • 결론

    σ=2g153(0)+18=(2↑155)+14

Permutations

  • 상태 B에서 시작

    σB=2g63(0)+9=(2↑65)+5

  • 상태 C에서 시작

    σC=2g03(0)+3=(2↑05)−1=9 (72단계에서 종료)

  • 변환된 TNF

    | 0   | 1   | 2   | 3   |
| --- | --- | --- | --- |
| A   | 1RB | 3RB | 1LC | 2LA |
| B   | 2LA | 2RB | 1LB | 3RA |
| C   | 3LA | 1RZ | 1LC | 2RA |

Not Collatz

  • 흥미로운 점
    • 이 TM은 놀라울 정도로 단순함
    • Collatz와 같은 규칙이 없음
    • 이는 Collatz와 같은 Ackermann 수준의 TM이 존재할 가능성을 배제하지 않음

Inductive Proof Validator

  • 프로젝트 목표
    • "유도 증명" 검증기를 개발 중
    • 표준화된 증명서 형식을 개발하여 다양한 유도 증명을 검증할 수 있도록 함
    • 아직 초기 단계이지만, 여러 TM의 동작을 증명하는 데 성공함

GN⁺의 의견

  • 흥미로운 점

    • 이 기사는 튜링 기계와 Ackermann 함수의 복잡성을 이해하는 데 큰 도움이 됨
    • 간단한 규칙으로 복잡한 계산을 수행할 수 있다는 점이 매력적임

  • 비판적 시각

    • 이 기계의 복잡성을 이해하기 위해서는 수학적 배경 지식이 필요함
    • 실용적인 응용보다는 이론적인 흥미에 더 초점이 맞춰져 있음

  • 관련 기술

    • 유도 증명 검증기는 자동화된 수학 증명 시스템 개발에 큰 기여를 할 수 있음
    • 다른 복잡한 계산 문제에도 적용 가능성이 있음

  • 고려 사항

    • 이 기술을 도입할 때는 검증 과정의 정확성과 효율성을 고려해야 함
    • 복잡한 수학적 개념을 이해하고 적용하는 데 시간이 필요함
▲
neo 6달전  [-]
Hacker News 의견

해커뉴스 댓글 모음 요약

  • 간단한 튜링 머신 프로그램
    튜링 머신 프로그램이 복잡한 스파게티 코드일 것이라는 생각과 달리, 이 새로운 프로그램은 상대적으로 간단함. 세 가지 상태(A, B, C)가 있으며, 상태 B는 A와 C로 제어를 넘기지만, A와 C는 서로를 알지 못하고 B로만 제어를 넘김. 이는 모듈식 구조로, 진정한 스파게티 코드에서는 각 상태가 다른 모든 상태로 제어를 넘길 수 있음.

  • 흥미로운 특징
    이 프로그램은 빈 칸을 출력하지 않으며, 모든 명령이 상태나 색을 변경함. 새로운 BB(3,4) 기록 보유자는 약 64비트의 정보를 가짐. BBλ(49)는 49비트로 그레이엄 수를 훨씬 초과함.

  • 구현 예시
    프로그램을 직접 구현해본 결과, 상태 B는 0을 2로, 1을 1로 변경하며 C로 전환하고, 상태 C는 3을 2로 변경하며 A로 전환함. 이는 3의 연속을 지수적으로 길게 만듦.

  • 코드 골프와의 유사성
    이 모든 것이 극단적인 코드 골프처럼 보임. BitGrid라는 개인 취미 프로젝트는 셀당 4비트 상태만 가지며, 4x4 그리드는 최대 2^64까지 셀 수 있음. 작은 그리드에서는 가장자리 연결이 결과에 큰 영향을 미침.

  • 튜링 머신 해석 자료 요청
    테이블을 해석하는 방법에 대한 자료 요청. 이는 튜링 머신의 설명으로 보임.

  • 튜링 머신의 한계
    제한된 수의 기호로 설명할 수 있는 튜링 머신의 수는 한정적임. 일부 튜링 머신이 멈추기 전에 엄청난 수의 단계를 수행할 수 있다는 사실이 놀라움.

  • 특별한 점 설명 요청
    이 특정 명령 집합이 왜 인상적인지에 대한 설명 요청. Ackerman 함수 수준의 함수가 무엇인지, 실제로 무엇을 계산하는지 궁금함.

  • 수학적 진리에 대한 흥미
    쓸모없어 보이는 결과가 매우 유용한 LLM 발전보다 더 흥미로움. 이는 간단한 수학적 진리에 자연스럽게 끌리기 때문임.

  • BB(5)와 BB(3,4) 비교
    BB(5)가 BB(3,4)보다 큰지에 대한 질문. bbchallenge.org 사이트에서는 BB(5)가 약 4700만이라고 하지만, BB(3,4)는 훨씬 더 크다고 함.

  • 저자의 맥락 제공
    저자가 일부 맥락을 제공한 점이 좋음.

답변달기