바쁜 비버

바쁜 비버(Busy beaver) 게임이란 이론 컴퓨터 과학에서 가능한 가장 많은 출력을 생성하거나 가장 긴 시간동안 실행되는 (정의에 따라 주어진) 특정한 크기의 종료되는 컴퓨터 프로그램을 찾는 것을 말한다.^[2] 여기서 무한히 많은 출력을 생성하거나 무한한 시간동안 실행되는 무한 루프 프로그램은 쉽게 상상할 수 있기 때문에 바쁜 비버 게임에서 제외한다.^[2] 게임에서 사용되는 프로그램은 전통적인 프로그래밍 언어가 아닌 최초의 컴퓨터 수학 모델^[3]중 하나인 n상태 튜링 기계를 이용한다.^[2]

이 "시공간 다이어그램"^[1]에서는 최대 5개 상태를 가진 바쁜 비버가 첫 10만번째 움직임에서 메모리 테이프의 상태를 위에서 아래로 쭉 보여준다. 여기서 주황은 1, 흰색은 0을 의미한다.(세로로 압축된 그림)

튜링 기계는 무한히 긴 테이프와 프로그램의 "소스 코드" 역할을 하는 유한한 상태 집합 둘로 구성되어 있다. 여기서 가장 많은 출력을 생성한다는 말은 테이프에 가장 많은 수의 1을 기록하는 것으로 정의하며 이를 "최대 점수를 달성"하는 것이라고도 말한다. 가장 긴 시간동안 실행된다는 말은 가장 오랫동안 기계가 움직이다 정지한다는 것으로 정의한다.^[4] n상태 바쁜 비버 게임은 n개의 상태를 가진 가장 오랫동안 실행되거나 최대 점수를 달성하는 정지하는 튜링 기계를 찾는 게임이다.^[2] 이런 튜링 기계는 빈 테이프에서 시작하며, 테이프에는 오직 0과 1만 써 넣을 수 있다(이진 튜링 기계)라고 가정한다.^[2] 게임의 목적은 기계가 최종적으로는 멈추게 하면서 최고 점수, 혹은 최장 실행 시간을 목표로 상태를 계속 전환하게 프로그래밍 하는 것이다.

n번째 바쁜 비버, 또는 간단하게 BB-n이나 "바쁜 비버"란 n상태 바쁜 비버 게임에서 이기는 튜링 기계를 뜻한다.^[5] 이 기계는 정의에 따라 다른 모든 가능한 n상태의 경쟁 튜링 기계 중에서 가장 높은 점수를 얻거나 가장 오랜 시간 동안 실행된다. 각각의 정의에 따라 n상태 바쁜 비버의 최고 점수 또는 최장 실행 시간을 결정하는 함수를 각각 Σ(n)과 S(n)라고 부른다.^[4]

n번째 바쁜 비버의 실행 시간이나 점수를 결정하는 것은 계산 불가능하다.^[4] 실제로 Σ(n)과 S(n) 두 함수 모두 계산 가능한 함수보다 더 커진다.^[4] 이는 계산 가능성 이론, 정지 문제, 계산 복잡도 이론에 영향을 미친다.^[6] 바쁜 비버라는 개념은 1962년 티보르 러도가 자신의 논문 《계산 불가능한 함수에 대하여》에서 처음으로 제시했다.^[4] 바쁜 비버에서 가장 흥미로운 점은 모든 n에 대해 함수 Σ(n)과 S(n)을 구할 수 있다면 "(이 튜링 머신은) 정지하는가"라는 형식으로 인코딩할 수 있는 모든 수학적 추측을 해결할 수 있다는 것이다.^[5] 예를 들어, 각 수 하나하나마다 골트바흐의 추측이 맞는지 확인하고 반례를 발견하면 정지하는 27상태 튜링 기계를 만들 수 있는데, 이 튜링 기계가 S(27)회의 작동 후에도 멈추지 않았다면 무한히 실행된다는 의미로 추측이 맞음을 증명할 수 있다.^[5] 그 외에도 리만 가설(744상태), ZF 집합론의 완전성(745상태^[7][8])을 포함한 여러 수학 문제도 비슷한 형태로 표현할 수 있지만 거의 셀 수 있는 가산 집합의 무한에 가까운 수의 경우를 확인해야 한다.^[5]

기술적 설명

티보르 러도의 1962년 논문에서 소개된 n상태 바쁜 비버 게임(BB-n game)은 튜링 기계 중에서 뽑는 게임으로, 각 기계는 다음과 같은 설계 사양을 만족해야 한다.

• 각 기계는 n개의 "작동" 상태와 정지 상태를 가지는데 여기서 n은 양의 정수이며 n개의 상태 중 하나가 시작 상태로 구분된다.(보통 상태1을 시작 상태로 놓고 상태 1, 2, 3, ... n으로 붙이거나 상태A를 시작 상태로 놓고 상태 A, B, C, ... 순으로 이름붙인다.)
• 기계는 하나의 양방향 무한(또는 경계가 없는) 테이프를 사용한다.
• 테이프에 새겨지는 기호는 {0, 1}로 0은 보통 빈 기호로 사용한다.
• 기계의 '전환함수'는 두 가지 입력을 받는다.

1. 정지가 아닌 현재의 상태
2. 현재 위치한 테이프 셀의 기호

또한 세 가지 출력을 생성한다.

1. 현제 위치한 테이프 셀에 있는 기호에 덮어쓸 기호(기존의 기호와 같을 수 있음)
2. 이동할 방향(왼쪽 또는 오른쪽 한 칸 이동)
3. 전환할 상태(정지 상태가 될 수 있음)

기계를 "실행"한다는 것은 현재 테이프 셀이 빈(모두 0) 테이프의 임의의 셀에서 시작 상태에서 시작한 후 (가능하다면) 정지 상태가 될 때까지 전환함수를 반복하는 작업을 가리킨다. 기계가 언젠가 멈출 경우에만 테이프에 최종적으로 남아 있는 1의 갯수를 기계의 점수라고 한다. 따라서 n상태 바쁜 비버 게임은 정의에 따라 가장 가능한 큰 점수 혹은 긴 실행 시간을 가진 n상태 튜링 기계를 찾는 게임이다.

예시

1상태 튜링 기계 중 하나의 규칙은 다음과 같다.

• 상태 1에서 현재 기호가 0이면 1을 쓰고 한 칸 오른쪽으로 이동한 후 상태 1로 전환한다.
• 상태 1에서 현재 기호가 1이면 0을 쓰고 한 칸 오른쪽으로 이동한 후 정지 상태로 전환한다.

이 튜링 기계는 오른쪽으로 이동하면서 통과하는 모든 셀의 값을 바꾼다. 시작 상태에서 테이프는 전부 0만 있으므로 이 기계는 끝없이 계속 1만을 써내려가며 멈추지 않을 것이다. 이 기계는 빈 테이프에서 영원히 실행되기 때문에 바쁜 비버 후보가 될 수 없다.

함수

1962년 원 논문에서 러도는 바쁜 비버 게임과 관련된 두 가지 함수를 정의했다. 바로 점수 함수 Σ(n)와 이동 함수 S(n)이다.^[4] 이 둘은 튜링 기계의 상태 수 ${\displaystyle n}$을 받아들이고, 그 상태 수의 튜링 기계가 어떤 기준에 따라 도달할 수 있는 최대 점수를 출력한다. 점수 함수 Σ(n)는 ${\displaystyle n}$ 상태 튜링 기계가 정지하기 전에 출력할 수 있는 최대 1의 개수를 나타내는 반면, 이동 함수 S(n)은 ${\displaystyle n}$ 상태 튜링 기계가 정지하기 전까지 수행할 수 있는 최대 이동(또는 각 단계에 이동이 포함되므로 단계와 동등함) 횟수를 나타낸다.^[4] 그는 이 두 함수가 어떤 계산 가능 함수보다도 더 빠르게 증가하기 때문에 계산 불가능 함수임을 증명했다.^[4] 함수 BB(n)은 이 두 함수 중 어느 하나를 지칭하기 위해 정의되었으므로 이 문서에서는 해당 표기법을 사용하지 않는다.

시간 또는 최대 1의 개수 외에 다른 방식으로 튜링 기계의 성능을 측정하여 정의할 수 있는 여러 가지 계산 불가능 함수가 있다.^[9] 예를 들면 다음과 같다.^[9]

• 함수 ${\displaystyle {\text{num}}(n)}$은 정지하는 튜링 기계가 빈 테이프에 쓸 수 있는 최대 연속된 1의 개수로 정의된다. 즉, 이는 n 상태의 튜링 기계가 테이프에 쓸 수 있는 가장 큰 일진법 수이다.
• 함수 ${\displaystyle {\text{space}}(n)}$은 정지하는 튜링 기계가 정지하기 전까지 읽을 수 있는(즉, 방문하는) 최대 테이프 칸 수로 정의된다. 여기에는 시작 칸이 포함되지만, 정지 전환 후에만 도달하는 칸은 포함되지 않는다(만약 정지 전환에 이동 방향이 명시되어 있다면). 왜냐하면 해당 칸은 기계의 동작에 영향을 주지 않기 때문이다. 이는 n 상태 튜링 기계의 최대 공간 복잡도이다.

이 네 가지 함수는 함께 ${\displaystyle {\text{num}}(n)\leq \Sigma (n)\leq {\text{space}}(n)\leq S(n)}$의 관계를 갖는다.^[9] 또한 3-기호 튜링 기계와 같은 다른 계산 기계,^[10] 비결정론적 튜링 기계,^[11] 람다 대수 (OEIS의 수열 A333479) 또는 심지어 임의의 프로그래밍 언어에서 게임을 작동시켜 더 많은 함수를 정의할 수 있다.^[10]

점수 함수 Σ

점수 함수는 바쁜 비버가 주어진 측정 기준에 따라 달성할 수 있는 최대 점수를 정량화한다. 이는 계산 불가능 함수인데, 어떤 계산 가능 함수보다 점근적으로 빠르게 증가하기 때문이다.^[12]

점수 함수 ${\displaystyle \Sigma$ :\mathbb {N} \to \mathbb {N} } 는 위에서 설명한 유형의 모든 정지하는 2개 기호 n상태 튜링 기계 중에서 빈 테이프에서 시작했을 때 도달할 수 있는 최대 점수(테이프에 최종적으로 남는 1의 최대 개수)로 정의된다.

Σ가 잘 정의된 함수임은 명확하다. 모든 n에 대해 동형사상에 대해 위의 조건을 만족하는 n상태 튜링 기계는 유한개이므로 가능한 실행 시간도 유한개이다.

점수 기반 정의에 따르면 σ(M) = Σ(n)을 만족하는(즉, 최대 점수를 달성하는) 모든 n상태 2개 기호 튜링 기계 M을 바쁜 비버라고 한다. 각 n에 대해 적어도 4(n − 1)! 개의 n상태 바쁜 비버가 존재한다. (어떤 n상태 바쁜 비버가 주어지면, 정지 전환 상황에서 이동 방향만 바꾸어 다른 바쁜 비버를 얻을 수 있고, 모든 이동 방향을 균일하게 반전시켜 세 번째 바쁜 비버를 얻을 수 있으며, 모든 방향을 교환한 바쁜 비버의 정지 방향을 반전시켜 네 번째 바쁜 비버를 얻을 수 있다. 또한 시작 상태와 정지 상태를 제외한 모든 상태의 순열은 동일한 점수를 달성하는 기계를 생성한다. 이론적으로는 정지 상태로 이어지는 전환 유형이 하나 이상 있을 수 있지만, 실제로는 낭비일 것이다. 왜냐하면 원하는 결과를 생성하는 상태 전환 시퀀스는 하나뿐이기 때문이다.)

계산 불가능성

라도의 1962년 논문은 ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$가 어떤 계산 가능 함수라도 충분히 큰 n에 대해 Σ(n) > f(n)이 성립하며, 따라서 Σ가 계산 가능 함수가 아님을 증명했다.^[4]

더 나아가, 이는 임의의 튜링 기계가 바쁜 비버인지 여부를 판단하는 일반적인 알고리즘이 존재하지 않음을 의미한다. (이러한 알고리즘은 존재할 수 없다. 만약 존재한다면 Σ를 계산할 수 있게 되는데, 이는 이미 불가능함이 증명되었다. 특히, 이러한 알고리즘은 다음과 같이 Σ를 계산하는 다른 알고리즘을 구성하는 데 사용될 수 있다. 주어진 n에 대해 유한한 개수의 n개 상태 2개 기호 튜링 기계 각각을 테스트하여 n개 상태 바쁜 비버를 찾을 때까지 진행한다. 이 바쁜 비버 기계를 시뮬레이션하여 그 점수를 결정하는데, 이것이 정의에 따른 Σ(n)이다.)

Σ(n)이 계산 불가능 함수임에도 불구하고 그 값을 얻을 수 있고 그 정확성을 증명할 수 있는 작은 n 값이 있다. Σ(0) = 0, Σ(1) = 1, Σ(2) = 4임을 쉽게 보일 수 있으며, 점진적으로 더 어려워지면서 Σ(3) = 6, Σ(4) = 13, Σ(5) = 4098임을 보일 수 있다. (OEIS의 수열 A028444). Σ(n)의 값은 5보다 큰 어떤 n에 대해서도 아직 결정되지 않았지만, 하한은 계산되었다 (아래 알려진 결과 섹션 참조).

Σ의 복잡도와 증명 불가능성

콜모고로프 복잡도의 한 변형은 다음과 같이 정의된다.^[13] 숫자 n의 복잡도는 처음에 빈 테이프에서 n개의 연속된 1로 구성된 단일 블록을 쓰고 정지하는 BB급 튜링 기계에 필요한 최소 상태의 수이다. 해당 차이틴의 불완전성 정리 변형은 주어진 공리계 내에서 어떤 특정 숫자도 복잡도가 자연수 k보다 크다는 것을 증명할 수 없는 숫자 k가 존재하며, 따라서 Σ(k)의 어떤 특정한 상한도 증명할 수 없음을 명시한다 (후자는 "n > Σ(k)"이 증명된다면 "n의 복잡도가 k보다 크다"는 것이 증명될 것이기 때문이다). 인용된 참고 문헌에서 언급했듯이, "일상적인 수학"의 어떤 공리계에 대해서도 이것이 참이 되는 최소값 k는 10⇈10보다 훨씬 작다. 결과적으로, 일상적인 수학의 맥락에서 Σ(10⇈10)의 값이나 어떤 상한도 증명할 수 없다. (괴델의 제1 불완전성 정리는 이 결과로 설명된다. 일상적인 수학의 공리계에서 Σ(10⇈10) = n 형식의 참이지만 증명 불가능한 문장이 존재하며, Σ(10⇈10) < n 형식의 참이지만 증명 불가능한 문장은 무한히 많다.)

최대 이동 함수 S

Σ 함수 외에도 1962년 러도는 튜링 기계를 위한 또 다른 극단적인 함수인 최대 이동 함수 S를 다음과 같이 정의했다.^[4]

• s(M) = 정지하기 전에 M이 수행하는 이동 횟수이며, 임의의 M ∈ E_n에 대해 정의된다.
• S(n) = maxs(M) | M ∈ E_n} = 어떤 정지하는 n개 상태 2개 기호 튜링 기계가 수행하는 최대 이동 횟수이다.

일반적인 튜링 기계는 모든 상태 전환 또는 "단계"에(정지 상태로의 전환을 포함하여) 이동이 필요하기 때문에, 최대 이동 함수는 동시에 최대 단계 함수이다.

러도는 Σ가 계산 불가능한 것과 같은 이유로 S가 계산 불가능함을 보였다. 어떤 계산 가능 함수보다 빠르게 증가하기 때문이다. 그는 각 n에 대해 S(n) ≥ Σ(n)임을 간단히 언급하여 이를 증명했다. 각각의 이동은 테이프에 0 또는 1을 쓸 수 있지만 Σ는 1을 쓴 이동의 부분 집합, 즉 튜링 기계가 정지할 때까지 덮어쓰이지 않은 1들을 센다. 결과적으로 S는 Σ보다 최소한 빠르게 증가하며, Σ는 이미 어떤 계산 가능 함수보다도 빠르게 증가함이 증명되었다.^[4]

Σ와 S 사이의 다음 연결은 린과 러도(Lin & Radó, Computer Studies of Turing Machine Problems, 1965)가 Σ(3) = 6 및 S(3) = 21임을 증명하는 데 사용되었다. 주어진 n에 대해 S(n)이 알려져 있다면 모든 n개 상태 튜링 기계를 (이론적으로) S(n) 단계까지 실행할 수 있으며, 이 시점에서 아직 정지하지 않은 기계는 앞으로도 결코 정지하지 않을 것이다. 그 시점에서 테이프에 가장 많은 1을 남기고 정지한 기계(즉, 바쁜 비버)를 관찰해 이 테이프에서 Σ(n)의 값을 얻는다. n = 3의 경우에 린과 러도가 사용한 접근 방식은 S(3) = 21이라고 추측한 다음(18이라고 추측한 후 실패함), 본질적으로 다른 모든 3개 상태 기계(82,944대, 2¹⁰3⁴와 같음)를 총 21단계까지 시뮬레이션하는 것이었다. 그들은 정지한 26,073대의 기계를 발견했으며 이 중 하나는 21단계 후에야 정지했다. 21단계 내에 정지하지 않은 기계의 동작을 분석하여 그들은 정지하지 않은 기계 중 어느 것도 결코 정지하지 않을 것임을 보이는 데 성공했으며, 대부분은 특정한 패턴을 따랐다. 이것은 S(3) = 21이라는 추측을 증명했고, 또한 Σ(3) = 6임을 결정했다. 이는 여러 기계를 통해 달성했으며 모두 11에서 14단계 후에 정지했다.^[14]

2016년, 아담 예디디아(Adam Yedidia)와 스캇 아론슨(Scott Aaronson)은 ZFC에서 S(n)이 증명 불가능해지는 최소 n의 첫 번째 (명시적) 상한을 계산했다. 이를 위해 그들은 일반적인 집합론 공리 및 선택공리에 기반하여 그 동작을 증명할 수 없는 7910개 상태^[15] 합리적인 일관성 가설 하에(고정 램지 속성) 튜링 기계를 구성했다.^[16][17] 스테판 오리어(Stefan O'Rear)는 이를 1919개 상태로 줄였고, 특정 가설에 대한 의존성은 제거했다.^[18][19] 이후 748개 상태로 줄였다.^[6] 2023년 7월 리벨(Riebel)은 이를 745개 상태로 줄였다.^[7][8]

space(n)과 num(n)의 계산 불가능성

함수 ${\displaystyle {\text{space}}(n)}$와 ${\displaystyle {\text{num}}(n)}$는 모두 계산 불가능하다.^[9] 이는 ${\displaystyle {\text{space}}(n)}$의 경우, 튜링 기계가 1을 쓰는 모든 테이프 칸을 반드시 방문해야 함을 주목함으로써 보일 수 있다. 즉, ${\displaystyle \Sigma (n)\leq {\text{space}}(n)}$이다.^[9] 함수 ${\displaystyle {\text{num}}(n)}$은 예를 들어 ${\displaystyle {\text{space}}(n)<{\text{num}}(3n+3)}$임을 증명함으로써 계산 불가능함을 보일 수 있다. 이는 n개 상태 공간을 가장 많이 채운 기계를 시뮬레이션하고 이를 사용하여 테이프에 적어도 ${\displaystyle {\text{space}}(n)}$개의 연속된 1을 쓰도록 (3n+3)개 상태 튜링 기계를 설계함으로써 가능하다.^[9]

일반화

주어진 크기의 프로그램이 생성하는 최대 출력 길이를 정의할 수 있다면 어떤 프로그래밍 언어에서도 이동 함수의 유사체를 간단히 정의할 수 있다.^[10] 예를 들어, 바쁜 비버 게임은 2차원 테이프의 튜링 기계를 사용하거나, 왼쪽과 오른쪽으로 이동하는 것 외에 같은 자리에 머무는 것을 허용하는 튜링 기계를 사용하여 2차원으로 일반화될 수 있다.^[10] 또는 콜모고로프 복잡도를 사용하여 다양한 계산 모델에 대한 "바쁜 비버 함수"를 정의할 수 있다.^[10] 이는 ${\displaystyle K_{L}(m)\leq n}$를 만족하는 가장 큰 정수 ${\displaystyle m}$을 ${\displaystyle {BB}(n)}$로 정의하여 가능하며, 여기서 ${\displaystyle K_{L}(m)}$은 ${\displaystyle m}$을 출력하는 ${\displaystyle L}$의 가장 짧은 프로그램 길이이다: ${\displaystyle {BB}(n)}$은 이로써 길이 ${\displaystyle n}$ 이하의 프로그램이 ${\displaystyle L}$에서 출력할 수 있는 가장 큰 정수가 된다.^[10]

6개 상태, 2개 기호 기계 중 가장 오래 실행되고 각 단계에서 테이프 값을 반전시키는 추가 속성을 가진 기계는 47339970 단계 후에 6147개의 1을 생성한다. 따라서 반전 튜링 기계 (RTM) 클래스의 경우,^[20] S_RTM(6) ≥ 47339970이고 Σ_RTM(6) ≥ 6147이다. 마찬가지로 레지스터 머신에 대한 Σ 함수의 유사체를 주어진 명령어 수에 대해 정지 시 레지스터에 존재할 수 있는 가장 큰 숫자로 정의할 수 있다.

다른 기호 수

간단한 일반화로 2개(0과 1) 대신 m개의 기호를 가진 튜링 기계로의 확장을 둘 수 있다.^[10] 예를 들어 m=3개의 기호를 가진 삼진 튜링 기계는 기호 0, 1, 2를 가질 것이다. n 상태와 m 기호를 가진 튜링 기계로의 일반화는 다음 일반화된 바쁜 비버 함수를 정의한다:

1. Σ(n, m): 처음에 빈 테이프에서 시작하여 정지하기 전에 n 상태, m 기호 기계가 인쇄할 수 있는 가장 큰 0이 아닌 수
2. S(n, m): 처음에 빈 테이프에서 시작하여 정지하기 전에 n 상태, m 기호 기계가 걸린 가장 큰 단계 수^[10]

예를 들어, 지금까지 발견된 가장 오래 실행되는 3개 상태 3개 기호 기계는 정지하기 전까지 119112334170342540 단계를 실행한다.^[21][22]

비결정론적 튜링 기계

p개 경우, 2개 상태, 2개 색상 NDTM의 최대 정지 시간 및 상태^[11]

p	단계	상태
1	2	2
2	4	4
3	6	7
4	7	11
5	8	15
6	7	18
7	6	18

이 문제는 모든 분기의 상태 수가 가장 많거나 가장 긴 단계 수를 가진 분기를 찾는 방식으로 비결정론적 튜링 기계(NDTM)의 문제로 확장할 수 있다.^[11] 주어진 NDTM이 정지할지 여부 문제는 여전히 계산적으로 축약 불가능하며, NDTM의 바쁜 비버를 찾는 데 필요한 계산은 결정론적 경우보다 상당히 크다. 여러 분기를 고려해야 하기 때문이다. p개 경우 또는 규칙을 가진 2개 상태, 2개 색상 체계의 경우 오른쪽 표에서 정지하기 전 최대 단계 수와 NDTM에 의해 생성된 고유 상태의 최대 수를 볼 수 있다.

응용

미해결 수학 문제

다소 도전적인 수학 게임을 만든다는 목적 외에도, 바쁜 비버 함수 Σ(n)과 S(n)는 순수 수학 문제를 해결하는 완전히 새로운 접근 방식을 제공한다. 이론적으로는 충분히 큰 n에 대한 S(n)의 값이 주어진다면 실제로는 거의 불가능하지만 많은 미해결 수학 문제를 계산하는 방식으로 해결할 수 있다.^[5][23] 이론적으로 말하자면, S(n)의 값은 n 상태 이하의 튜링 기계에서 무한한 시간 내에 확인할 수 있는 모든 수학적 추측에 대한 답을 인코딩한다.^[6]

어떤 ${\displaystyle \Pi _{1}^{0}}$ 가산 가능한 수의 사례 중 반례를 통해 반증될 수 있는 어떤 추측(예: 골트바흐의 추측)을 고려해 보자. 값이 증가하면서 이 추측을 순차적으로 테스트하는 컴퓨터 프로그램을 작성하자. 골트바흐의 추측의 경우, 우리는 x≥4인 모든 짝수를 순차적으로 고려하고 그것이 두 소수의 합인지 아닌지를 테스트할 것이다. 이 프로그램을 n개 상태 튜링 기계에서 시뮬레이션한다고 가정하자. 만약 반례를 발견하면(예에서는 두 소수의 합이 아닌 x≥4인 짝수), 그것은 정지하고 그 값을 내보낸다. 그러나 추측이 참이라면 이 프로그램은 절대로 정지하지 않을 것이다.(이 프로그램은 반례를 발견할 때만 정지한다.)^[6]

이제 이 프로그램은 n개 상태 튜링 기계로 시뮬레이션되므로, S(n)를 알고 있다면 기계를 S(n) 단계까지만 실행해서 기계가 정지할지 여부를 (유한한 시간 내에) 결정할 수 있다. 그리고 만약 S(n) 단계 후에 기계가 정지하지 않는다면, 우리는 그것이 절대로 정지하지 않을 것이며 따라서 주어진 추측에 대한 반례가 없음을 알게 된다 (즉, 두 소수의 합이 아닌 짝수가 없다). 이는 추측이 참임을 증명할 것이다.^[6] 따라서 S(n)의 특정 값 (또는 상한)은 이론적으로 많은 미해결 수학 문제를 체계적으로 해결하는 데 사용될 수 있다.^[6]

하지만 바쁜 비버 문제에 대한 현재 결과는 두 가지 이유로 이것이 실용적이지 않음을 보여준다.

• 바쁜 비버 함수 (및 최대 이동 함수)의 값을 증명하는 것은 극도로 어렵다. 알려진 모든 정확한 S(n) 값은 모든 n 상태 튜링 기계를 열거하고 각 기계가 정지할지 여부를 하나하나 증명해야 완벽한 증명이 가능하다. 실제로 유용하게 사용하려면 S(n)을 이보단 덜 직접적인 방법으로 계산할 수 있어야 한다.
• S(n) 및 다른 바쁜 비버 함수의 값은 매우 빠르게, 매우 커진다. S(5)의 값은 약 4,700만 정도이지만, S(6)의 값은 10⇈15보다 크며, 이는 15개의 10이 쌓인 ${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$과 같다.^[10][24] 이 숫자는 10⇈14개의 자릿수를 가지며, 관측 가능한 우주에서 쓰거나 기계를 실행하기에는 터무니없이 크다. 골트바흐의 추측에 대한 현재 프로그램이 결정적인 답을 얻기 위해 실행해야 하는 단계 수인 S(27)의 값은 이해할 수 없을 정도로 거대하며, 작성하거나 기계를 실행하기는커녕 상상조차 할 수 없다.^[5]

이론의 일관성

S(n)의 또 다른 속성은 산술적으로 건전하고 계산 가능하게 공리화된 이론은 함수의 모든 값을 증명할 수 없다는 것이다. 구체적으로는 계산 가능하고 산술적으로 건전한 이론 ${\displaystyle T}$가 주어지면, 모든 ${\displaystyle n\geq n_{T}}$에 대해 ${\displaystyle T}$에서 ${\displaystyle S(n)=k}$ 형태의 어떤 명제도 증명할 수 없는 숫자 ${\displaystyle n_{T}}$가 존재한다.^[6] 이는 각 이론에 대해 증명할 수 있는 S(n)의 특정한 최대값이 있다는 것을 의미한다. 모든 그러한 ${\displaystyle T}$에 대해 ${\displaystyle T}$의 모든 가능한 증명을 열거하도록 ${\displaystyle n_{T}}$ 상태를 가진 튜링 기계를 설계할 수 있기 때문에 이것은 사실이다.^[6] 이론이 비일관적이라면 모든 거짓인 명제가 증명 가능하며, 튜링 기계는 예를 들어 ${\displaystyle 0=1}$의 증명을 발견할 때만 정지하도록 조건을 지정할 수 있다.^[6] ${\displaystyle S(n_{T})}$의 값을 증명하는 어떤 이론도 그 자신의 일관성을 증명하는 것이므로, 이는 괴델의 두 번째 불완전성 정리를 위반한다.^[6] 이는 다양한 이론, 예를 들어 ZFC의 다양한 큰 기수 공리를 척도로 사용할 수 있다. 각 이론 ${\displaystyle T}$에 그 숫자 ${\displaystyle n_{T}}$가 할당되면, 더 큰 ${\displaystyle n_{T}}$ 값을 가진 이론은 그 아래 이론의 일관성을 증명하여 모든 그러한 이론을 가산 무한 척도에 배치한다.^[6]

주목할 만한 예시

• ZFC가 비일관적인 것과 동치일 경우에만 정지하는 745개 상태 이진 튜링 기계가 있다.^[7][8]
• 리만 가설이 거짓인 경우에만 정지하는 744개 상태 튜링 기계가 있다.^[18][5]
• 골트바흐의 추측이 거짓인 경우에만 정지하는 43개 상태 튜링 기계가 있다. 이는 25개 상태 기계로 더 축소되었으며,^[18][5] 나중에 Lean 4 증명 보조 언어를 통해 공식적으로 증명 및 검증되었다.^[25]
• 에르되시 팔이 1979년에 공식화한 모든 n > 8에 대해 2ⁿ의 3진법 표현에 적어도 하나의 숫자 2가 있다는 추측이 거짓인 경우에만 정지하는 15개 상태 튜링 기계가 있다.^[26][27]

보편 튜링 기계

계산적 보편성과 바쁜 비버 튜링 기계의 동적 행동 사이의 관계를 탐구하며, 2012년에 바쁜 비버 기계가 보편 튜링 기계의 자연스러운 후보라고 제안하는 추측이 제기되었다.^[28] 이는 바쁜 비버 기계가 (1) 크기 제약 내에서 최대 계산 복잡성을 가지고, (2) 정지하기 전에 비자명한 계산을 수행하는 능력, 그리고 (3) 이러한 기계를 찾고 증명하는 어려움으로 알려져 있으며, 이러한 특징들은 바쁜 비버 기계가 보편성에 필요한 복잡성을 소유하고 있음을 시사한다.

물리적 처치-튜링 논제

바쁜 비버 함수의 성장 특성은 물리적 처치-튜링 논제의 진실성을 가정할 때 물리 시스템의 행동에 영향을 미친다. 물리적 처치-튜링 논제가 참이고 모든 물리적으로 계산 가능한 함수가 튜링 계산 가능하다면, 직접 측정 가능한 어떤 물리량도 바쁜 비버 함수보다 빠르게 성장할 수 없다. 어떤 튜링 계산 가능한 함수도 바쁜 비버 함수보다 빠르게 성장할 수 없기 때문이다.^[29] ${\displaystyle BB(n)}$의 간단한 함수는 성장 속도의 하한뿐만 아니라 수렴 속도의 상한 및 하한도 부과할 것이다.^[30][29]

알려진 결과

하한

그린 기계

1964년 밀턴 그린은 1을 세는 바쁜 비버 함수의 변형에 대한 하한을 구상하여 1964년 IEEE 스위칭 회로 이론 및 논리 설계 심포지엄 회보에 발표했다. 헤이너 마센과 쥐르겐 분트로크는 이를 "비자명한(원시적으로 재귀적이지 않은) 하한"이라고 설명했다.^[31] 이 하한은 계산할 수 있지만 n의 단일한 표현으로 나타내기에는 너무 복잡하다.^[32] 이는 각 n에 대한 하한을 보여주는 일련의 튜링 기계로 수행했다.^[32] n=8일 때 그린 기계는 다음과 같이 계산할 수 있다.

${\displaystyle \Sigma (8)\geq 3\times (7\times 3^{92}-1)/2\approx 8.248\times 10^{44}}$.

대조적으로, 현재 (2024년 기준) ${\displaystyle \Sigma (6)}$에 대한 최상의 하한은 ${\displaystyle 10\uparrow \uparrow 15}$이며, 여기서 각 ${\displaystyle \uparrow }$는 커누스 윗화살표 표기법이다.^[10] 이는 ${\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}}$를 나타내며, 15개의 10으로 구성된 지수 탑으로 ${\displaystyle 10^{10\uparrow \uparrow 14}}$와 같다. ${\displaystyle \Sigma (8)}$의 값은 아마도 이보다 훨씬 클 것이다.

구체적으로 하한은 재귀적인 튜링 기계 무리로 볼 수 있는데 각 기계는 더 작은 기계와 두 개의 추가 상태로 구성되어 더 작은 기계를 입력 테이프에 반복적으로 적용했다.^[32] ${\displaystyle m}$개의 1을 포함하는 테이프에 대한 N 상태 바쁜 비버 경쟁자의 값을 ${\displaystyle B_{N}(m)}$으로 정의하면 (각 기계의 최종 출력은 ${\displaystyle m=0}$에 대한 값인데, 빈 테이프는 0개의 1을 가지고 있기 때문), 재귀 관계는 다음과 같다.^[32]

${\displaystyle B_{N}(0)=1}$

${\displaystyle B_{1}(m)=m+1}$

${\displaystyle B_{N}(m)=1+B_{N-2}(1+B_{N}(m-1))}$

이는 N번째 기계 ${\displaystyle G(N)}$에 의해 주어진 하한을 계산하기 위한 홀수 및 짝수 번호에 대한 두 가지 공식을 유도할 수 있다.

홀수 N에 대해 ${\displaystyle G(N)=B_{N-2}(B_{N-2}(1))}$

짝수 N에 대해 ${\displaystyle G(N)=1+B_{N-3}(1+B_{N-3}(1))}$

하한 BB(N)은 아커만 함수와도 연관지을 수 있다. 이 때 다음이 성립함이 밝혀졌다.^[33]

${\displaystyle A(n,n)>G(4N+3)>A(4,2N+1)}$

바쁜 비버 함수 간의 관계

자명하게, S(n) ≥ Σ(n)이다. 왜냐하면 Σ(n)개의 1을 쓰는 기계는 그렇게 하기 위해 적어도 Σ(n) 단계를 거쳐야 하기 때문이다.^[33] S(n)의 시간에 대한 상한을 Σ(n)의 개수로 여러 공식으로 쓸 수 있다.

• ${\displaystyle S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}}$   (러도^[33])
• ${\displaystyle S(n)\leq \Sigma (9n)}$   (부로^[33])
• ${\displaystyle S(n)\leq (2n-1)\times \Sigma (3n+3)}$   (벤-알람, 줄스톰-즈윅^[33])

n개 상태 튜링 기계가 어떤 위치에 있든 상관없이 연속적으로 출력할 수 있는 최대 1의 개수를 num(n)으로 정의하여(출력할 수 있는 가장 큰 일진법 숫자) 다음을 보일 수 있다.^[33]

${\displaystyle {\text{num}}(n)<\Sigma (n)}$

${\displaystyle S(n)<{\text{num}}(n+o(n))}$

${\displaystyle S(n)<{\text{num}}(3n+6)}$   (Ben-Amram, et al., 1996^[9])

또한 Ben-Amram과 Petersen, 2002는 S(n)에 대한 점근적으로 개선된 상한을 제시한다. 모든 n ≥ 2에 대해 상수 c가 존재하며 다음과 같다.^[33]

${\displaystyle S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).}$

정확한 값과 하한 및 상한

다음 표는 S(n), Σ(n) 및 다른 여러 바쁜 비버 함수의 정확한 값과 알려진 일부 하한을 나열한다. 이 표에서는 2개 기호 튜링 기계가 사용된다. "?"로 나열된 항목은 왼쪽의 다른 항목보다 적어도 크거나 같으며 (모든 n 상태 기계는 (n+1) 상태 기계이기도 하므로), 위의 항목보다 크지 않다(S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)이므로). 따라서 space(6)은 space(n) ≥ Σ(n)이고 Σ(6) > 10⇈15이므로 10⇈15보다 큰 것으로 알려져 있다. 47176870은 space(5)에 대한 상한이다. 왜냐하면 S(5) = 47176870(^[3])이고 S(n) ≥ space(n)이기 때문이다. 4,098은 num(5)에 대한 상한이다. 왜냐하면 Σ(5) = 4098(^[33])이고 Σ(n) ≥ num(n)이기 때문이다. 마지막 "?"로 나열된 항목은 num(6)이다. 왜냐하면 Σ(6) > 10⇈15이지만 Σ(n) ≥ num(n)이기 때문이다.

바쁜 비버 함수의 값

함수	2개 상태		3개 상태		4개 상태		5개 상태		6개 상태
S(n)	6	[6]	21	[6]	107	[6]	47176870	[3]	> 10⇈15	[10]
space(n)	4	[33]	7	[33]	16	[33]	≥ 12289 ≤ 47176870 S(n) ≥ space(n)	[33]	> 10⇈15 space(n) ≥ Σ(n)
Σ(n)	4	[33]	6	[33]	13	[33]	4098	[33]	> 10⇈15	[34]
num(n)	4	[33]	6	[33]	12	[33]	≤ 4098 Σ(n) ≥ num(n)		?

5개 상태 바쁜 비버는 1989년 헤이너 마센과 쥐르겐 분트로크이 발견했지만, Coq 증명을 사용하여 2024년에야 승리한 다섯 번째 바쁜 비버인 BB(5)이 완전히 증명되었다.^[35][36]

바쁜 비버 목록

5개 상태 바쁜 비버 기계(S(n), 이후 Σ(n)에 해당)의 축소된 시공간 다이어그램. 이 기계는 47,176,870 단계를 실행하여 최대 12,288개의 1을 생성하고 정지 시 4,098개의 1을 남긴다.
다이어그램은 테이프를 변경하는 단계만 보이도록 압축되었다. 녹색과 노란색 삼각형은 튜링 기계가 앞뒤로 이동하는 영역을 나타내며, 소요된 시간은 이 색칠된 삼각형의 면적에 비례한다. 아래 행은 정지 시의 테이프와 읽기/쓰기 헤드의 발췌 부분이다.

다음은 Σ(1) 및 S(1), Σ(2) 및 S(2), Σ(3) (단 S(3)는 아님), Σ(4) 및 S(4), Σ(5) 및 S(5)를 생성하는 튜링 기계의 규칙과 Σ(6) 및 S(6)에 대한 알려진 최상의 하한 표이다.

표에서 열은 현재 상태를 나타내고 행은 테이프에서 읽은 현재 기호를 나타낸다. 각 표 항목은 순서대로 테이프에 쓸 기호, 이동 방향 및 새 상태를 나타내는 세 문자 문자열이다. 정지 상태는 H로 표시된다.

각 기계는 무한한 테이프가 모두 0을 포함하는 상태에서 A 상태로 시작한다. 따라서 테이프에서 읽은 초기 기호는 0이다.

결과 설명: (오버라인된 위치에서 시작하여 밑줄된 위치에서 정지)

1개 상태, 2개 기호 바쁜 비버

	A
0	1RH
1	(사용되지 않음)

결과: 0 0 1 0 0 (1단계, 총 "1" 1개)

2개 상태, 2개 기호 바쁜 비버

	A	B
0	1RB	1LA
1	1LB	1RH

결과: 0 0 1 1 1 1 0 0 (6단계, 총 "1" 4개)

3개 상태, 2개 기호 바쁜 비버의 동작 애니메이션

3개 상태, 2개 기호 바쁜 비버^[37][14]

	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

결과: 0 0 1 1 1 1 1 1 0 0 (14단계, 총 "1" 6개).

이는 여섯 개의 1을 제공하는 몇 가지 서로 다른 기계 중 하나이다. 이전 기계와 달리 이 기계는 Σ에 대한 바쁜 비버이지만 S에 대한 바쁜 비버는 아니다. (S(3) = 21이고, 기계는 다섯 개의 1만 얻는다.^[14])

4개 상태, 2개 기호 바쁜 비버의 동작 애니메이션

4개 상태, 2개 기호 바쁜 비버

	A	B	C	D
0	1RB	1LA	1RH	1RD
1	1LB	0LC	1LD	0RA

결과: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107단계, 총 "1" 13개)

5개 상태, 2개 기호 바쁜 비버

	A	B	C	D	E
0	1RB	1RC	1RD	1LA	1RH
1	1LC	1RB	0LE	1LD	0LA

결과: 47,176,870 단계에서 8,191개의 "0"이 섞인 4,098개의 "1".

현재 6개 상태, 2개 기호 최고 경쟁자^[21][34]

	A	B	C	D	E	F
0	1RB	1RC	1LC	0LE	1LF	0RC
1	0LD	0RF	1LA	1RH	0RB	0RE

결과: 1 0 1 1 1 ... 1 1 1 ("10" 다음에 15개의 10으로 구성된 지수 탑인 10↑↑15=10^10..10보다 많은 연속된 "1"이 10↑↑15 단계 이상에서 나타난다).

시각화

다음 표에서는 각 바쁜 비버(Σ를 최대화하는) 규칙이 시각적으로 표현되어 있다. 주황색 사각형은 테이프의 "1"에 해당하고, 흰색은 "0"에 해당한다. 헤드의 위치는 검은색 타원형으로 표시되어 있으며, 헤드의 방향은 상태를 나타낸다. 개별 테이프는 가로로 배치되며, 시간은 위에서 아래로 진행된다. 정지 상태는 한 상태를 자체로 매핑하는 규칙(헤드가 움직이지 않음)으로 표현된다.

1~4개 상태 바쁜 비버의 진화

1개 상태 바쁜 비버 규칙

2개 상태 바쁜 비버 규칙

3개 상태 바쁜 비버 규칙

4개 상태 바쁜 비버 규칙

정지까지의 1개 상태 바쁜 비버의 진화. 초기 상태에서 정지로 바로 향하며, 종료 전에 하나의 "1"이 쓰여진다.

정지까지의 2개 상태 바쁜 비버 진화

정지까지의 3개 상태 바쁜 비버 진화

정지까지의 4개 상태 바쁜 비버 진화. 왼쪽 이미지의 맨 아래 줄은 오른쪽 이미지의 맨 위 줄로 이어진다. 마지막 단계에서 정지 전에 "1"을 쓴다 (표시되지 않음).

같이 보기

• 라요 수
• 튜르마이트 (Turmite)