# BB(3, 4) > Ack(14) 결과

> Clean Markdown view of GeekNews topic #14987. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=14987](https://news.hada.io/topic?id=14987)
- GeekNews Markdown: [https://news.hada.io/topic/14987.md](https://news.hada.io/topic/14987.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-05-25T09:58:24+09:00
- Updated: 2024-05-25T09:58:24+09:00
- Original source: [sligocki.com](https://www.sligocki.com//2024/05/22/bb-3-4-a14.html)
- Points: 1
- Comments: 1

## Topic Body

### 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임

#### 기계

- **상태 전이 표**
  ```markdown
  | 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) 정의**
  ```markdown
  B(k,n,m)=0∞32m+12k A> 1n
  ```

- **증명**
  ```markdown
  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) 정의**
  ```markdown
  g0(m)=m+1
  gk+1(m)=gk2m+2(0)
  ```

##### 이중 유도에 의한 증명

- **주요 규칙**
  ```markdown
  B(k,n,m)→B(k,0,gk−1n(m))
  ```

- **Lemma 1**
  ```markdown
  For all k≥1: 32k<B→2k+12k<B1
  ```

- **Corollary 2**
  ```markdown
  For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m
  ```

- **Theorem 3**
  ```markdown
  For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))
  ```

#### 정확한 값

- **Theorem**
  ```markdown
  For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)
  ```

- **Corollary**
  ```markdown
  For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)
  ```

- **결론**
  ```markdown
  σ=2g153(0)+18=(2↑155)+14
  ```

#### Permutations

- **상태 B에서 시작**
  ```markdown
  σB=2g63(0)+9=(2↑65)+5
  ```

- **상태 C에서 시작**
  ```markdown
  σC=2g03(0)+3=(2↑05)−1=9 (72단계에서 종료)
  ```

- **변환된 TNF**
  ```markdown
  | 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 함수의 복잡성을 이해하는 데 큰 도움이 됨
  - 간단한 규칙으로 복잡한 계산을 수행할 수 있다는 점이 매력적임

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

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

- **고려 사항**
  - 이 기술을 도입할 때는 검증 과정의 정확성과 효율성을 고려해야 함
  - 복잡한 수학적 개념을 이해하고 적용하는 데 시간이 필요함

## Comments



### Comment 25569

- Author: neo
- Created: 2024-05-25T09:58:24+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40453221) 
##### 해커뉴스 댓글 모음 요약

- **간단한 튜링 머신 프로그램**  
  튜링 머신 프로그램이 복잡한 스파게티 코드일 것이라는 생각과 달리, 이 새로운 프로그램은 상대적으로 간단함. 세 가지 상태(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)는 훨씬 더 크다고 함.

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