최근 수정 시각 : 2022-04-23 13:59:36

바쁜 비버



수학기초론
Foundations of Mathematics
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
다루는 대상과 주요 토픽
수리논리학 논리 · 논증{ 귀납논증 · 연역논증} · 공리 및 공준 · 증명{ 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제, 아이버슨 괄호 · · · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론
범주론 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
집합론 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한
계산가능성 이론 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 · 계산
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 불완전성 정리 · 힐베르트의 호텔 · 연속체 가설
기타
예비사항( 약어 및 기호) · 벤 다이어그램 · 수학철학 }}}}}}}}}}}}


''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
{{{#!wiki style="letter-spacing: -1px"
이론
기본 대상 수학기초론( 수리논리학 · 계산 가능성 이론 · 범주론 · 집합론), 그래프 이론
다루는 대상과 주요 토픽
계산 가능성 이론 튜링 기계 · 바쁜 비버
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, PRAM, 양자, 비결정론적^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식
수학적 최적화 조합 최적화 TSP · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법
주요 알고리즘 및 자료구조
기초 정렬 알고리즘
추상적 자료형과 그 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^, 피보나치 힙^
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · RSA · AES · LLL 알고리즘 · 해시( 암호화폐)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 }}}}}}}}}}}}


1. 개요2. 바쁜 비버 게임
2.1. 세부 동작 방법
3. 파생 함수
3.1. 바쁜 비버 함수(라도 시그마 함수)3.2. 미친 개구리 함수(최대 쉬프트 함수)
3.2.1. 성질
3.3. 고차 바쁜 비버 함수3.4. 삑삑거리는 바쁜 비버 함수3.5. 차분한 오리너구리 함수3.6. 피곤한 웜뱃 함수3.7. 일반화 바쁜 비버 함수3.8. 세미 바쁜 비버 함수
4. 응용5. 외부 링크

1. 개요

바쁜 비버(Busy Beaver)는 계산 가능성 이론과 계산 복잡도 이론에서 흥미로운 부분이 있는 컴퓨터 프로그램으로 헝가리의 수학자 라도 티보르(Radó Tibor, 1895~1965)가 도입했다. 튜링 머신이 일하는 모습이 동물 비버가 일하는 모습과 비슷하다고 해서 바쁜 비버라는 이름이 붙었다.

정지 문제와 밀접한 관련이 있으며, 수학에서 알려진 함수 중 손에 꼽힐만큼 빠르게 증가하는 함수인 바쁜 비버 함수와, 수학에서 등장한 수 중 손에 꼽힐만큼 큰 수인 바쁜 비버 수로 유명하다.

2. 바쁜 비버 게임

바쁜 비버 게임은 무한히 긴 테이프에 "0"이 빼곡히 쓰여 있을 때, n개의 상태(state)를 가질 수 있는 정지하는 튜링 머신으로 테이프에 최대한 많은 수의 "1"을 쓰는 게임이다. n비트 길이의 프로그램 중 가장 복잡한 프로그램을 찾는 게임이라고 이해해도 된다.

이때 n개 상태를 가지는 정지하는 모든 튜링 머신 중 가장 많은 1을 쓴 튜링 머신을 n번째 바쁜 비버라 한다.


4번째 바쁜 비버가 동작하는 모습. 비어 있는 칸은 0이라고 생각하면 된다.

State: 현재 상태를 표시한다. 0, 1, 2, 3이 있다. 차례대로 후술할 표의 A, B, C, D에 대응된다.
Position: 현재 처음 시작한 위치에서 몇 칸 떨어져 있는지를 표시하며, 오른쪽 아래의 점은 방향을 표시한다. 점이 켜져 있으면 현재 처음 위치보다 왼쪽에 있다는 뜻이고, 꺼져 있으면 오른쪽에 있다는 뜻이다. 정지했을 때 Position이 ‘10.’이므로 정지한 위치는 시작 위치로부터 왼쪽으로 10칸 떨어져 있다는 뜻이다.
Step: 시작한 후 현재까지 이동 횟수를 표시한다. 총 107번의 스탭을 거친다.

2.1. 세부 동작 방법

튜링 머신에 무한히 긴 테이프와 행동표를 입력한다. 표에는 값(0, 1)을 읽었을 때 현재 상태(A, B, C, ...)에 따라 다음에 할 행동들이 적혀있는데, 예를 들어 0과 A에 1좌B가 적혀있다면 현재 값이 0이고 상태가 A일때 1을 적고 왼쪽으로 1칸 이동한 다음 상태를 B로 바꾸라는 말이다.

또한 모든 비버 기계에는 "정지" 상태가 반드시 하나 이상 포함되어 있어야 하는데, 정의부터가 "정지하는" 튜링 머신이므로 정지 상태가 없으면 무한히 반복하기 때문. 정의상으론 하나 이상이지만 정지 상태를 두 개 이상 넣어서 얻는 이득이 없으므로 실용적으로는 단 하나라고 봐도 무방하다.

예를 들어 2상태 바쁜 비버 기계의 예시를 들면 아래와 같다.
A B
0 1우B 1좌A
1 1좌B 1우
그러면 위 비버 기계는 아래와 같이 행동하게 된다.(처음 시작은 A상태에서 시작한다.)
  1. ...00000... A상태, 1을 기록하고 우측으로 이동한다음 상태를 B로 변경
  2. ...00100... B상태, 1을 기록하고 좌측으로 이동한다음 상태를 A로 변경
  3. ...00110... A상태, 1을 기록하고 좌측으로 이동한다음 상태를 B로 변경
  4. ...00110... B상태, 1을 기록하고 좌측으로 이동한다음 상태를 A로 변경
  5. ...01110... A상태, 1을 기록하고 우측으로 이동한다음 상태를 B로 변경
  6. ...11110... B상태, 1을 기록하고 우측으로 이동한다음 정지

여기서 상태를 늘리려면 우측으로 표를 확장하면 된다. 아래의 예시는 3번째와 4번째 가장 바쁜 비버이다.
A B C
0 1우B 0우C 1좌C
1 1우 1우B 1좌A
A B C D
0 1우B 1좌A 1우 1우D
1 1좌B 0좌C 1좌D 0우A

또한 현재까지 알려진 가장 많은 1을 쓰는 5, 6개의 상태를 가진 바쁜 비버는 다음과 같다.
A B C D E
0 1우B 1우C 1우D 1좌A 1우
1 1좌C 1우B 0좌E 1좌D 0좌A
이 튜링 머신은 4098개의 1, 8191개의 0을 47176870번의 이동을 통해 쓰고 멈춘다.
A B C D E F
0 1우B 1우C 1좌D 1우E 1좌A 1좌
1 1좌E 1우F 0우B 0좌C 0우D 1좌C
이 튜링 머신은 [math(3.5 \times 10^{18267})]개의 1을 [math(7.4 \times 10^{36534})]번의 이동을 통해 쓰고 멈춘다.

3. 파생 함수

특수함수
Special Functions
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="letter-spacing: -1px"
{{{#!wiki style="margin:-6px -1px -11px; word-break: keep-all"
적분 오차함수(error function) · 베타 함수( 불완전 베타 함수) · 감마 함수( 불완전 감마 함수 · 로그 감마 함수) · 타원 적분 · 야코비 타원 함수 · 지수 적분 함수 · 로그 적분 함수 · 삼각 적분 함수 · 쌍곡선 적분 함수 · 프레넬 적분 함수 · 구데르만 함수
미분방정식 르장드르 함수* · 구면 조화 함수 · 베셀 함수 · 에르미트 함수 · 라게르 함수 · 에어리 함수
역함수 브링 근호 · 람베르트 [math(W)] 함수 · 역삼각함수
급수 제타 함수 · 세타 함수 · 초기하함수 · 폴리로그함수 · 바이어슈트라스 타원 함수
정수론 소수 계량 함수 · 소인수 계량 함수 · 뫼비우스 함수 · 최대공약수 · 최소공배수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 바쁜 비버 함수
기타 헤비사이드 계단 함수 · 부호 함수 · 테트레이션( 무한 지수 탑 함수) · 집합 판별 함수 · 바닥함수 / 천장함수 · 허수지수함수 · 혹 함수
* 특수함수가 아니라 특정 조건을 만족시키는 다항함수이지만, 편의상 이곳에 기술했다. }}}}}}}}}}}}


바쁜 비버의 사례를 따라서 '~하는/~인 동물' 함수로 명명된다.

3.1. 바쁜 비버 함수(라도 시그마 함수)

n번째 바쁜 비버가 쓰는 1의 개수의 최대값을 대응한 함수를 바쁜 비버 함수(Busy Beaver function) [math({\rm BB}(n))] 혹은 라도 시그마 함수(Radó's sigma function) [math(\Sigma (n))] 라고 한다. 당연히 바쁜 비버 함수의 정의역과 공역은 모두 자연수 집합이다.

바쁜 비버 함수는 대표적인 계산불가능한 함수(uncomputable function)이며, 정의역과 공역이 자연수 집합인 그 어떠한 계산가능(computable)한 함수보다도 점근적으로 빠르게 증가한다. 엄청난 속도로 빠르게 증가하는 함수이기 때문에 결국에는 집합론으로 이루어진 수학 체계를 탈출해버리는데 이에 대해서는 후술한다.

알려져 있는 값으로는 [math({\rm BB}(1)=1)], [math({\rm BB}(2)=4)], [math({\rm BB}(3)=6)], [math({\rm BB}(4)=13)]이다. [math({\rm BB}(5))]는 [math(4098)] 이상으로 추정되며, [math({\rm BB}(6))] 부터는 매우 매우 약한 하한만이 알려져 있는데, [math({\rm BB}(6))]는 [math(3.5 \times 10^{18267})]이상, [math({\rm BB}(7))]은 [math(10^{10^{10^{10^{18,750,353}}}})][1] 이상, [math({\rm BB}(10))]은 [math(3 uparrow uparrow uparrow 3)] 이상, [math(\text{BB}(11))]은 [math(3\uparrow\uparrow\uparrow720618962331271)] 이상, [math({\rm BB}(12))]은 [math(3 \uparrow \uparrow \uparrow \uparrow 3)] 이상, [math({\rm BB}(17))]은 그레이엄 수보다 크다.[2]

바쁜 비버 함수를 계산하는 대수적, 해석적인 해는 커녕[3] 기계적인 절차조차 존재하지 않기 때문에[4] 함수값을 알아내는 것은 끔찍하게 어렵다. 이게 왜 어려운지 설명하자면, [math({\rm BB}(2))]를 계산하고자 하면 상태가 2개인 [math(6561)]개의 튜링 머신 중 정지하지 않고 영원히 동작하는 튜링 머신을 배제하는 작업이 필요한데 이걸 계산하는 일반화된 방법이 없음을 엘런 튜링이 증명하였다. [math(6561)]개 까지는 어찌 해볼 수 있겠지만 3 상태 튜링 머신은 [math(4826809)]개가 존재하고, 4 상태 튜링 머신은 [math(6975757441)]개가 존재하며, 5 상태 튜링 머신은 [math(16679880978201)]개가 존재한다. [math({\rm BB}(4))]를 계산하는데 성공한 Allen H. Brady는 이걸로 박사 학위를 받았다. [math(6975757441)]개의 튜링 머신을 전수조사한 것은 당연히 아니고 4 상태 튜링 머신의 특징을 분석해서 가능한 튜링 머신의 개수를 [math(5820)]개로 줄이는데 성공했기에 가능한 일이었다.

어찌 보면 무한 지수 탑 함수와 성격이 비슷해 보이지만, 무한 지수 탑 함수는 일정 정의역[5]]을 벗어나면 복소수가 된다.

3.2. 미친 개구리 함수(최대 쉬프트 함수)

n번째 바쁜 비버의 최대 스텝 이동 횟수를 대응한 함수를 최대 쉬프트 함수(Maximum shifts function) [math(S(n))][6] 혹은 미친 개구리 함수(Frantic frog function) [math({\rm FF}(n))]이라고 한다. 바쁜 비버 함수와 형제 관계인 함수로 많은 성질들을 공유한다. 바쁜 비버 함수보다 더 빠르게 증가하고, 모든 [math(n)]에 대하여 [math({\rm FF}(n) \geq {\rm BB}(n))]이므로 미친 개구리 함수 역시 계산 불가능하며, 정의역과 공역이 자연수의 집합인 그 어떠한 계산 가능한 함수보다도 점근적으로 빠르게 증가한다.

미친 개구리 함수 역시 작은 n에 대해서만 그 값이 알려져 있다. 알려져 있는 값으로는 [math({\rm FF}(1)=1)], [math({\rm FF}(2)=6)], [math({\rm FF}(3)=21)], [math({\rm FF}(4)=107)]이며, [math({\rm FF}(5))]는 [math(47176870)] 이상으로 추정되고, 그보다 큰 값에 대해서는 매우 매우 약한 하한만이 알려져 있는데, [math({\rm FF}(6))]는 [math(7.4 \times 10^{36534})] 이상, [math({\rm FF}(7))]은 [math(10^{2\times 10^{10^{10^{18750353}}}})]이상, [math({\rm FF}(17))]은 그레이엄 수 보다 크다.

미친 개구리 함수를 바쁜 비버 함수라 부르는 사람들도 있는데, 1의 개수보다 쉬프트 횟수를 기준으로 하는게 더 자연스럽다고 보는 관점 때문이다.

3.2.1. 성질

여기에 제시된 성질들은 [math({\rm FF}(n))]뿐만 아니라 [math({\rm BB}(n))]에도 그대로 적용된다.
[math(f : {\mathbb N} \mapsto {\mathbb N})]이고 [math(f(n) \geq {\rm FF}(n))]인 어떤 함수 [math(f(n))]에 대해 계산이 가능한 연산 장치는 튜링 머신에 대한 정지 문제를 해결할 수 있다. 따라서 [math({\rm FF}(n))]과 [math({\rm FF}(n))]의 상한인 [math(f(n))]은 계산 불가능하다.
n 상태 튜링 머신이 정지하는지 결정하기 위해서는 미친 개구리 함수의 정의를 이용해서 튜링 머신이 [math({\rm FF}(n))] 스텝만큼 돌렸을 때 정지했는지 확인하면 된다. 만약 정지하지 않았다면 해당 머신은 영원히 동작함을 알 수 있다. 이는 미친 개구리 함수를 계산 가능한 튜링 머신은 정지 문제를 풀 수 있다는 것을 의미한다. 즉 바쁜 비버 문제는 정지 문제와 튜링 동치이다.
[math(f : {\mathbb N} \mapsto {\mathbb N})]인 모든 계산 가능한 함수는 [math(n \geq n_{f})]에 대해 [math({\rm FF}(n) > f(n))] 이 성립하는 [math(n_{f})]가 존재한다.
[math({\rm FF}(n))]이 계산가능한 모든 함수보다 점근적으로 빠르게 증가한다는 뜻이다.
공리계 [math(T)]가 계산가능하고 산술적으로 건전하다면 [math(n \geq n_{T})]에 대해 "[math({\rm FF}(n) ≤ k)]" 형식의 문장을 [math(T)]에서 증명할 수 없는 [math(n_{T})]가 존재한다.
[math({\rm FF}(n))]은 모든 [math(n)]에 대하여 완벽히 잘 정의된 함수이지만, 불완전성 정리로 인해 [math({\rm FF}(n))]에서 [math(n)]이 커지면 그 값을 절대로 알아낼 수 없다. 더 강력한 공리계를 도입해도 [math(n_{T})]의 하한이 증가할 뿐 미지의 경계는 사라지지 않는다. 2016년에 ZF 공리계가 [math({\rm FF}(7910))]의 값을 결정할 수 없다고 증명되었으며, 2019년에 [math({\rm FF}(1919))], 2020년에 [math({\rm FF}(748))]을 결정할 수 없음이 증명되었다. 이 성질은 바쁜 비버 함수에도 그대로 적용되므로 [math({\rm BB}(748))]도 ZF 공리계와 독립이다. 계산 복잡도 이론의 권위자인 스콧 에런슨(Scott Aaronson) 교수는 ZF 공리계가 [math({\rm FF}(20))]의 값을 증명할 수 없고, 페아노 공리계는 [math({\rm FF}(10))]의 값을 증명할 수 없다고 추측하고 있다.

3.3. 고차 바쁜 비버 함수

바쁜 비버 문제에 계산 이론에서 다루는 개념인 Hypercomputation을 접목하면 재미있는 결과를 얻을 수 있다. 바쁜 비버 함수는 계산 불가능한 함수이다. 즉 튜링 머신으로 계산하는게 불가능하다. 만약 튜링 머신에 임의의 [math({\rm BB}(n))]을 구할 수 있는 장치인 오라클(Oracle)을 붙여서 바쁜 비버 함수를 계산할 수 있는 가상의 슈퍼 튜링 머신을 가정한다면, 슈퍼 튜링 머신에서의 바쁜 비버 함수인 2차 바쁜 비버 함수 [math({\rm BB}_{2}(n))]를 생각할 수 있다.

2차 바쁜 비버 함수는 바쁜 비버 함수보다 빠르게 증가하는데, 슈퍼 튜링 머신으로 계산 불가능하며, 슈퍼 튜링 머신으로 계산할 수 있는 그 어떤 함수보다도 점근적으로 빠르게 증가한다. 예를 들어 [math(({\rm BB \circ BB})(n))] 같은 괴물같은 함수보다 [math({\rm BB}_{2}(n))]가 점근적으로 빠르게 증가한다.

여기서 끝나지 않고, 2차 바쁜 비버 함수를 구할 수 있는 오라클을 슈퍼 튜링 머신에 붙여 만든 슈퍼 슈퍼 튜링 머신으로 3차 바쁜 비버 함수 [math({\rm BB}_{3}(n))]를 만들 수 있다. 또 이를 [math({\rm BB}_{4}(n))], [math({\rm BB}_{5}(n))]...[math(\rm BB_{\rm ΒΒ(n)}(n))]...으로 무한히 확장해 나가는 방법으로 더욱 빠르게 증가하는 함수를 만들 수 있다. 피쉬 수 4 또한 이 과정으로 만들어졌다.

이런 무한번의 확장을 초월하기 위해 자연수 전체 k에 대해 k차 바쁜 비버 함수를 모두 계산할 수 있는 오라클을 가진 튜링 머신을 만들고, 이를 이용해 ω차 바쁜 비버 함수 [math({\rm BB}_{ω}(n))]라는 정신나간 함수를 만들 수 있다. 여기서 ω는 가장 작은 가산 무한 서수이다.

또 [math({\rm BB}_{ω}(n))]를 오라클로 쓰는 튜링 머신으로 [math({\rm BB}_{ω+1}(n))]를 정의할 수 있고, [math({\rm BB}_{ω+2}(n))], [math({\rm BB}_{ω+3}(n))] ...로 무한히 확장하고, 이를 초월해서 아무 자연수 k에 대해 [math({\rm BB}_{ω+k}(n))]를 모조리 계산할 수 있는 오라클을 사용하는 튜링 머신으로 [math({\rm BB}_{ω2}(n))]을 만들고, 이걸 또 오라클로 써서 정의한 [math({\rm BB}_{ω3}(n))], [math({\rm BB}_{ω4}(n))] ...로 무한히 확장, 또 한단계 더 초월한 [math({\rm BB}_{ω^{2}}(n))], [math({\rm BB}_{ω^{3}}(n))], [math({\rm BB}_{ω^{4}}(n))] ... 한단계 또 초월한 [math({\rm BB}_{ω^{ω}}(n))],[7] [math({\rm BB}_{ω^{ω^{ω}}}(n))], [math({\rm BB}_{ω^{ω^{ω^{ω}}}}(n))] ... 한단계 또 초월한 [math({\rm BB}_{\epsilon_{0}}(n))], [math({\rm BB}_{\epsilon_{1}}(n))], [math({\rm BB}_{\epsilon_{2}}(n))] ... 한단계 또 초월한 [math({\rm BB}_{\zeta_{0}}(n))], [math({\rm BB}_{\zeta_{1}}(n))], [math({\rm BB}_{\zeta_{2}}(n))] ... ... ... ... ... ... [math({\rm BB}_{ω_{\sf ZF}}(n))][8] 이런 식으로 가능하다. 이 과정을 계속 이어나갈수는 없는데, 비가산 서수를 이용한 고차 바쁜 비버 함수는 잘 정의되지 않을 가능성이 있으며, 매우 큰 가산 서수가 존재함을 증명하려면 더 강력한 공리계를 필요로 하기 때문이다. 비가산 서수의 예로는 Church–Kleene 서수 [math(\omega^{\text{CK}}_1)]가 있고, 이는 모든 가산 서수의 상한이 된다. 즉 더 강력한 공리계를 들고올수록 더 빠르게 증가하는 함수와 더 큰 수를 만드는게 가능하다.

고차 바쁜 비버 함수는 또 다른 함수인 무한 시간 튜링 머신 바쁜 비버 함수(Infinite Time Turing Machine Busy Beaver function) [math({\rm BB}_{\infty}(n))]나 삑삑거리는 바쁜 비버 함수(Beeping Busy Beaver function) [math({\rm BBB}(n))]와 밀접하게 연관된다.

3.4. 삑삑거리는 바쁜 비버 함수

고차 바쁜 비버 함수에는 오라클에 값을 어떻게 질의할지에 대한 디테일이 빠져있다. 2차 바쁜 비버 함수를 작은 n에서나마 계산하기 위해서는 튜링머신이 오라클에 접근하는 수많은 절차 중 하나를 먼저 선택해줘야 하는데, 모든 사람이 인정해 줄 기준이 되는 방법이 없다는 문제가 있다. 이 문제를 회피하기 위해 나온 함수가 삑삑거리는 바쁜 비버 함수이다.

삑삑거리는 바쁜 비버(Beeping Busy Beaver)는 미리 정해둔 특정한 상태를 탈출할 때 삑 소리를 내는 기능을 추가한 튜링 머신들이 있을 때 가장 많은 삑 소리를 낸 튜링 머신을 찾는 문제이다. 이때 n 상태 튜링 머신 중 유한번의 삑 소리를 낸 튜링 머신의 최대 삑 소리 횟수를 대응한 함수를 삑삑거리는 바쁜 비버 함수(Beeping Busy Beaver function) [math({\rm BBB}(n))]라 한다. 중요한 점은 튜링 머신이 정지할 필요는 없고, 유한번의 삑 소리만 내면 된다. 즉 바쁜 비버가 정지 문제와 연결된다면, 삑삑거리는 바쁜 비버는 준정지 문제와 연결된다.

[math({\rm BBB}(n))]는 [math({\rm BB}(n))]을 초월하는 속도로 빠르게 증가하며, [math({\rm BB}_{2}(n))]와 비슷한 속도로 증가한다. 알려진 값으로는 [math({\rm BBB}(1)=1)], [math({\rm BBB}(2)=6)]이며, [math({\rm BBB}(3))]는 [math(55)] 이상, [math({\rm BBB}(4))]는 [math(32779478)] 이상이다.

[math({\rm BBB}(n))]는 [math({\rm BB}(n))]보다 더 계산 불가능한 함수이다. [math({\rm BB}(n))]에 대한 오라클을 가지고 있는 튜링 머신은 [math({\rm BBB}(n))]을 계산할 수 없으며, [math({\rm BB}_{2}(n))]에 대한 오라클을 가지고 있어야 [math({\rm BBB}(n))]을 계산할 수 있기 때문이다. 그 역도 성립하는데 [math({\rm BBB}(n))]에 대한 오라클을 가진 튜링 머신은 [math({\rm BB}_{2}(n))]을 계산할 수 있다.

삑삑거리는 바쁜 비버 함수를 비슷한 방법으로 확장해서 [math({\rm BB}_{3}(n))]과 동일한 계층에 있는 함수인 일명 [math({\rm BBBB}(n))]를 만들 수 있는지를 생각할 수 있다. 즉, 0차 산술 계층에 계산 가능한 문제가 있고, 1차 산술 계층에 정지 문제, 2차 산술 계층에 준정지 문제가 있는데, 3차 산술 계층에 대응되는 문제는 무엇이냐는 질문이다. 이것은 아직 답이 나오지 않은 미해결 문제이다.

3.5. 차분한 오리너구리 함수

차분한 오리너구리 함수(Placid platypus function) [math({\rm pp}(n))]은 튜링 머신이 n개의 1을 출력하기 위한 최소한의 상태 갯수로 정의된다. 즉 바쁜 비버 함수의 역함수이다.

[math({\rm BB}^{-1}(n) = {\rm pp}(n) \Leftrightarrow {\rm pp}^{-1}(n) = {\rm BB}(n))]


바쁜 비버 함수가 너무 빠르게 증가해서 계산 불가능하다면, 차분한 오리너구리 함수는 더럽게 느리게 증가해서 계산 불가능한 함수이다.

3.6. 피곤한 웜뱃 함수

피곤한 웜뱃 함수(Weary wombat function) [math({\rm ww}(n))]은 튜링 머신이 [math(n)]번의 쉬프트를 위해 필요한 최소한의 상태 개수로 정의된다. 즉 미친 개구리 함수의 역함수이다.

[math({\rm FF}^{-1}(n) = {\rm ww}(n) \Leftrightarrow {\rm ww}^{-1}(n) = {\rm FF}(n))]

3.7. 일반화 바쁜 비버 함수

튜링 머신이 사용할 수 있는 기호가 2가지보다 많은 경우의 바쁜 비버 함수와 미친 개구리 함수를 생각할 수 있다. 이변수함수 꼴인 [math({\rm BB}(n,\,m))]과 [math({\rm FF}(n,\,m))]은 [math(n)]개 상태와 [math(m)]개 기호를 사용하는 튜링 머신에 대한 바쁜 비버 함수와 미친 개구리 함수이며, 이를 일반화 바쁜 비버 함수와 일반화 미친 개구리 함수라 한다.
m이 커질 경우 n이 커지는 경우보다 더욱 빠르게 증가한다. [math({\rm BB}(3,\,2)=6)]이지만 [math({\rm BB}(2,\,3)=9)]이며, 이 값은 m>2인 경우의 바쁜 비버 함수들 중 유일하게 증명된 값이다. [math({\rm BB}(4,\,2)=13)]이지만 [math({\rm BB}(2,\,4))]는 하한값이 무려 2050으로 알려져 있고 아직 증명되지 않았다. 특히 [math({\rm BB}(3,\,3))]만 되도 하한값이 374686383이 된다.
미친 개구리 함수의 값 마찬가지로 [math({\rm FF}(2,\,3)=38)]만 알려져 있으며 이 이외의 값은 현재까지 증명되지 않았다. [math({\rm FF}(2,\,4))]는 최소 3932964이며 [math({\rm FF}(3,\,3))]은 하한값이 11경을 넘는다.

3.8. 세미 바쁜 비버 함수

모든 계산 가능한 함수보다 빠르게 증가하면서도, 바쁜 비버 함수보다는 한 차원 느리게 증가하는 함수 [math(f)]가 존재하는가를 생각해볼 수 있다. 그에 대한 대답은 "예"이다.

대충 설명하자면, [math({\rm BB}(n))]에 대한 오라클을 가지고 있어서 바쁜 비버 함수를 계산할 수 있는 머신은 튜링 머신에 대한 정지 문제를 해결하는게 가능하다. 그런데 모든 계산가능한 함수보다 점근적으로 빠르게 증가하는 어떤 함수 [math(f)]에 대한 오라클을 가진 머신이 튜링 머신에 대한 정지 문제를 해결할 수 없는 경우가 존재한다. 따라서 모든 계산가능한 함수보다 빠르게 증가하면서 바쁜 비버보다는 한 차원 느리게 증가하는 함수 [math(f)]가 존재한다.

4. 응용

바쁜 비버는 수학적 난제를 증명하는 새로운 접근 방법을 제시한다. 예를 들어 리만 가설에 대한 반례가 존재하면 정지하고 아니면 영원히 동작하는 744 상태를 가진 튜링 머신을 만들 수 있다. 미친 개구리 함수는 정지하는 튜링 머신의 연산 상한이므로 [math({\rm FF}(744))]번의 연산을 거쳤을 때 이 튜링 머신이 정지하였는지 여부를 관찰하면 리만 가설의 반증 가능 여부를 가릴 수 있다. 즉 컴퓨터로 유한한 연산을 해서 리만 가설의 반례가 없음을 보일 수 있다.[9] 안타깝게도 미친 개구리 함수가 정신나갈 정도로 빠르게 증가하는 함수이기 때문에 우주가 끝날 때까지 컴퓨터를 돌려도 증명 결과는 나오지 않을 것이다.

비슷한 방법으로 순차적으로 검사를 해서 골드바흐의 추측에 대한 반례를 찾으면 정지하는 프로그램은 27 상태 튜링 머신으로 만들수 있다. 이 튜링 머신이 [math({\rm FF}(27))]번의 연산을 했을 때 정지했는지를 확인함으로써 컴퓨터로 유한번의 연산을 해서 골드바흐 추측을 증명하는게 가능하다.

재미있는 예로, ZF 공리계가 모순된다면 정지하는 748 상태 튜링 머신을 만들 수 있다. 이를 이용해 [math({\rm FF}(748))]번의 연산을 거쳤을 때 해당 튜링 머신이 정지하는지를 확인하면 ZF 공리계의 무모순성을 증명할 수 있다.[10] 그러나 이는 불완전성 정리로 인해 ZF 공리계 내에서 불가능하므로, [math({\rm FF}(748))]의 값과 상한을 알아내는 것이 ZF 공리계에서 불가능하다는 결론을 낼 수 있다. 오해하면 안되는게, 모든 [math(n)]에 대하여 완벽히 잘 정의된 함수이기 때문에 [math({\rm FF}(748))]은 정확히 고정된 유일한 자연수로 존재한다.[11] 그 값이 무엇인지 증명하는게 ZF 공리계에서 불가능하다는 뜻이다.[12]

즉 이 증명법에는 치명적인 문제가 있는데 [math(n)]이 5 이상일 때의 미친 개구리 함수의 정확한 값을 현재로서는 모르며, ZF 공리계에서 값을 알아내는 것이 불가능 할 수 있다는 것과, 그 값이 초월적으로 크다는 것이다. [math({\rm FF}(6))]이 우주 전체의 계산 능력을 아득히 넘어서는 [math(7.4 \times 10^{36534})]보다 훨씬 크다는 것 부터 답이 없다. [math(n)]이 작을 때의 함수값을 ZF 공리계에서 구하는 게 가능하다면, 컴퓨터로 반례를 찾아내는 방식으로 수학 문제를 풀 때 필요한 연산의 수를 무한에서 유한으로 끌어 내렸다는 수학적 의미는 있다.[13] 또한 [math({\rm FF}(27))]을 ZF 공리계에서 구하는게 가능하다면, 골드바흐의 추측이 ZF(C) 공리계와 독립이 아니라는 근거가 될 것이다.

5. 외부 링크


[1] 테트레이션으로 [math(8.0678 \uparrow \uparrow 6)]으로 근사 가능하며 더 간단하게는 [math(8 \uparrow \uparrow 6)], 참고로 우주의 푸엥카레 회귀시간이 대략 [math(3 \uparrow \uparrow 6)]이다.(수가 너무 커서 단위가 세기 플랑크 시간이든 별로 중요하지 않다.) [2] 이보다 더 큰 함숫값은 훨씬 더 약한 하한만이 증명되었다. 예를 들어, [math(\text{BB}(38))]은 [math(f_{omega2}(167))] 이상, [math(\text{BB}(64))]는 [math(f_{\omega^2}(4098))] 이상, [math(\text{BB}(85))]는 [math(f_{\epsilon_0}(1907))] 이상이다. [math(\text{BB}(160))]은 계산 가능한 가장 큰 수들 중 하나로 알려진 로더의 수 보다도 크다. [3] 다시 말하면, 바쁜 비버 함수는 초등함수를 유한 번 사용해서 표현할 수도, 테일러 급수, 푸리에 급수 등으로 극한을 구할 수도 없다. [4] 역사적으로 수학자들의 큰 난제인 소수 판별도 기계적인 절차 정도는 있다는 것을 감안하면 얼마나 골치 아픈 문제인지 알 수 있다. [5] [math((0,\,1) \cup (1,\,\sqrt[e]{e}\;\!]) [6] 표기가 같은 프레넬 사인 적분 함수와 혼동될 수 있으므로 주의. [7] 피쉬 수 4의 성장률은 대략 [math({\rm BB}_{ω^{ω+1}63+1}(n))] 정도 된다. [8] [math(ω_{\sf ZF})]는 ZF 공리계에서 존재성을 증명할 수 있는 모든 가산 서수의 상한이다. [9] 그냥 참이라 가정하고 대놓고 써도 상관은 없는 게, 리만 가설과 ZFC가 독립일 때, 리만 가설이 거짓이라는 반례는 ZFC를 위반하며, (실용적인 관점에서) 계산할 때 언제나 실수부가 1/2가 나오기 때문이다. [10] 2016년에 나온 논문에서는 7910 상태 튜링 머신이었으나 2020년 기준으로 7910 상태 -> 1919 상태 -> 748 상태로 최적화되었다. [11] [math(n)]개 상태 튜링 머신 중 무한히 동작하지 않는 튜링 머신만 모아놓으면 그 중 가장 오래 동작하는 튜링 머신이 있다는 건 당연하기 때문이다. 정수로 이루어진 유한 집합은 최대값을 가진다는 것에서 유도된다. [12] 그래서 만약 ZF 공리계보다 더 강력한 공리계를 도입해 [math({\rm FF}(748))]의 값을 증명할 수 있다면 그것을 통해 더 강력한 공리계에서 ZF 공리계의 무모순성을 증명하는 것이 이론적으로는 가능하다. (하지만 그 강력한 공리계를 증명할 수 없다.) 물론 [math({\rm FF}(748))]이 초월적으로 크기에 우주멸망까지 컴퓨터를 돌려도 실제 증명 결과는 나오지 않을 것이다. [13] 사실 이 증명법으로 수학 난제를 증명하는 데에는 바쁜 비버 함수나 미친 개구리 함수의 정확한 함수값이 아닌 상한값만을 알아도 충분하다. 정확한 함수값을 알 때보다 더 많은 연산을 해야하는 것이 문제이고, 현재로서는 5 이상의 n에 대해서는 하한값만이 알려져 있다는 것이 문제이지만 말이다. 물론 현실적으로는 n이 6 이상만 되어도 실용적인 증명법으로는 사용할 수 없을 만큼 값이 크다.