| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요2. 바쁜 비버 게임3. 파생 함수
3.1. 바쁜 비버 함수(라도 시그마 함수)3.2. 미친 개구리 함수(최대 쉬프트 함수)
4. 역사3.2.1. 성질
3.3. 고차 바쁜 비버 함수3.4. 삑삑거리는 바쁜 비버 함수3.5. 차분한 오리너구리 함수3.6. 피곤한 웜뱃 함수3.7. 일반화 바쁜 비버 함수3.8. 세미 바쁜 비버 함수4.1. BB(2, 2)~BB(4, 2)4.2. BB(5, 2)
5. 응용6. 참고문헌 및 외부 링크4.2.1. skelet list
4.3. BB(6, 2)4.4. BB(7, 2) 이상4.5. BB(2, 3)4.6. BB(3, 3)4.7. BB(2, 4)4.8. BB(2, 5) 이상4.9. BBB 함수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로 바꾸라는 말이다.또한 모든 비버 기계에는 "정지" 상태가 반드시 하나 이상 포함되어 있어야 하는데, 정의부터가 "정지하는" 튜링 머신이므로 정지 상태가 없으면 무한히 반복하기 때문.[1] 정의상으론 하나 이상이지만 정지 상태를 두 개 이상 넣어서 얻는 이득이 없으므로 실용적으로는 단 하나라고 봐도 무방하다.
예를 들어 2상태 바쁜 비버 기계의 예시를 들면 아래와 같다.
| A | B | |
| 0 | 1우B | 1좌A |
| 1 | 1좌B | 1우끝 |
그러면 위 비버 기계는 아래와 같이 행동하게 된다.(처음 시작은 A상태에서 시작한다.)
| 스텝 | 상태 | 위치 | 행동 | ||||||
| 1 | A | ... | 0 | 0 | 0 | 0 | 0 | ... | 1을 기록하고 우측으로 이동한 다음 상태를 B로 변경 |
| 2 | B | ... | 0 | 0 | 1 | 0 | 0 | ... | 1을 기록하고 좌측으로 이동한 다음 상태를 A로 변경 |
| 3 | A | ... | 0 | 0 | 1 | 1 | 0 | ... | 1을 기록하고 좌측으로 이동한 다음 상태를 B로 변경 |
| 4 | B | ... | 0 | 0 | 1 | 1 | 0 | ... | 1을 기록하고 좌측으로 이동한 다음 상태를 A로 변경 |
| 5 | A | ... | 0 | 1 | 1 | 1 | 0 | ... | 1을 기록하고 우측으로 이동한 다음 상태를 B로 변경 |
| 6 | B | ... | 1 | 1 | 1 | 1 | 0 | ... | 1을 기록하고 우측으로 이동한 다음 정지 |
2.2. 가장 바쁜 비버
여기서 상태를 늘리려면 우측으로 표를 확장하면 된다. 아래의 예시는 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 |
| 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 |
한편, 2022년 6월에 나온 연구결과에 따르면 해당 튜링 머신이 현재 6-상태 튜링 머신 중 1등인 것으로 알려져 있다.
| A | B | C | D | E | F | |
| 0 | 1우B | 1우C | 1좌C | 0좌E | 1좌F | 0우C |
| 1 | 0좌D | 0우F | 1좌A | 1우끝 | 0우B | 0우E |
3. 파생 함수
| 특수함수 Special Functions | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="letter-spacing: -1px" {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | [math(^\ast)] 특수함수가 아니라 특정 조건을 만족시키는 다항함수이지만, 편의상 이곳에 기술했다. | |
| <colbgcolor=#383B3D> 적분 | 오차함수(error function)(가우스 함수 · 가우스 적분 함수) · 베타 함수(불완전 베타 함수) · 감마 함수(불완전 감마 함수 · 로그 감마 함수) · 타원 적분 · 야코비 타원 함수 · 지수 적분 함수 · 로그 적분 함수 · 삼각 적분 함수 · 쌍곡선 적분 함수 · 프레넬 적분 함수 · 구데르만 함수 | |
| 미분방정식 | 르장드르 함수[math(^\ast)] (구면 조화 함수) · 베셀 함수 · 에르미트 함수 · 라게르 함수 · 에어리 함수 | |
| 역함수 | 브링 근호 · 람베르트 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)≥4098)][3]으로 추정되며, [math({\rm BB}(6))]에서 이미 최소 테트리이션 수준으로 일상적 수로 표현할 방법이 없으며, [math({\rm BB}(7))]부터의 값은 하한값조차 제대로 알려져 있지 않는데[4] , 7 이상의 일부 n에 대하여 매우 매우 약한 하한이 알려져 있다.
- [math({\rm BB}(6)≥10 \uparrow \uparrow 15)]
- [math({\rm BB}(10)≥)] [math(3 uparrow uparrow uparrow 3)]
- [math(\text{BB}(11)≥3\uparrow\uparrow\uparrow720618962331271)]
- [math({\rm BB}(12)≥3 \uparrow \uparrow \uparrow \uparrow 3)] [5]
- [math({\rm BB}(16))]: 그레이엄 수보다 클 것으로 추측된다.[6]
- [math(\text{BB}(38)≥)] [math(f_{omega2}(167))]
- [math(\text{BB}(64)≥f_{\omega^2}(4098))]
- [math(\text{BB}(85)≥f_{\epsilon_0}(1907))]
- [math(\text{BB}(160)≥D^{5}(99))][7]
- [math(\text{BB}(745))]: 계산 가능한 그 어떠한 수보다 크다.
바쁜 비버 함수를 계산하는 대수적, 해석적인 해는 커녕[8] 기계적인 절차조차 존재하지 않기 때문에 함수값을 알아내는 것은 끔찍하게 어렵다. [math({\rm BB}(1)=1)]임은 자명하게 알 수 있지만, 이게 왜 어려운지 설명하자면, [math({\rm BB}(2))]를 계산하고자 하면 상태가 2개인 [math(6561)]개의 튜링 머신 중 정지하지 않고 영원히 동작하는 튜링 머신을 배제하는 작업이 필요한데 이걸 계산하는 일반화된 방법이 없음을 앨런 튜링이 증명하였다.
[math(6561)]개 까지는 어찌 해볼 수 있겠지만[9] 3 상태 튜링 머신은 [math(4826809)]개가 존재하고, 4 상태 튜링 머신은 [math(6975757441)]개가 존재하며, 5 상태 튜링 머신은 [math(16679880978201)]개가 존재한다. 일반적으로, n개의 상태를 가지는 튜링 머신은 [math((4n+1)^{2n})]가지 존재한다. [10][11] 한 번에 특정 튜링 머신이 행할 수 있는 가지수는 적을 기호(0과 1의 2개)*이동 방향(왼쪽, 오른쪽의 2개)*상태(n개)가 되어 4n이며 여기에 정지까지 추가하면 4n+1이다.[12] 거기에 가능한 케이스는 2n(0 또는 1을 만났는지 여부에 현재 상태의 수를 곱한 값)이다.[13] [math({\rm BB}(4))]를 계산하는데 성공한 Allen H. Brady는 이걸로 박사 학위를 받았다. [math(6975757441)]개의 튜링 머신을 전수조사한 것은 당연히 아니고 4 상태 튜링 머신의 특징을 분석해서 가능한 튜링 머신의 개수를 [math(5820)]개로 줄이는데 성공했기에 가능한 일이었다.
어찌 보면 무한 지수 탑 함수와 성격이 비슷해 보이지만, 무한 지수 탑 함수는 일정 정의역[14]]을 벗어나면 복소수가 된다.
3.2. 미친 개구리 함수(최대 쉬프트 함수)
n번째 바쁜 비버의 최대 스텝 이동 횟수를 대응한 함수를 최대 쉬프트 함수(Maximum shifts function) [math(S(n))][15] 혹은 미친 개구리 함수(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)][16], [math({\rm FF}(4)=107)]이며, 5를 넘어가면 확 커지기 시작하는데, [math({\rm FF}(5)≥47176870)]으로 추정되고[17], 그보다 큰 값에 대해서는 매우 매우 약한 하한만이 알려져 있다.
미친 개구리 함수를 바쁜 비버 함수라 부르는 사람들도 있는데[19], 1의 개수보다 쉬프트 횟수를 기준으로 하는게 더 자연스럽다고 보는 관점 때문이다. 단지 해당 함수값을 유도하는 머신은 항상 같지는 않은데, 예컨대 n=3의 경우 바쁜 비버 함수값은 6, 미친 개구리 함수값은 21이지만 6개의 1을 찍으면서 21번 이동하는 3상태 튜링 머신은 존재하지 않는다.[20]
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))],[21] [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))][22] 이런 식으로 가능하다. 이 과정을 계속 이어나갈수는 없는데, 비가산 서수를 이용한 고차 바쁜 비버 함수는 잘 정의되지 않을 가능성이 있으며, 매우 큰 가산 서수가 존재함을 증명하려면 더 강력한 공리계를 필요로 하기 때문이다. 비가산 서수의 예로는 최초의 비가산 서수 [math(\omega_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)≥55)], [math({\rm BBB}(4)≥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))]
바쁜 비버 함수가 너무 빠르게 증가해서 계산 불가능하다면, 차분한 오리너구리 함수는 더럽게 느리게 증가해서 계산 불가능한 함수이다. sgh처럼 비교적 느린 게 아니고 진짜로 느려터졌다. [math(n)]이 무한히 커질 때 [math(f(n))]이 무한으로 발산하는 모든 계산가능한 함수 [math(f)]보다 점근적으로 느리게 증가한다. 당연하지만 이렇게 느려터진 함수임에도 [math(\displaystyle\lim_{n\to ∞}{\rm pp}(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이 1이면 자명한 값을 가지며, 기호가 1개, 즉 m=1인 경우 [math({\rm BB}(n,\,1)={\rm FF}(n,\,1)=n)]이다. 특히 상태가 1개, 즉 n=1인 경우 m의 값에 관계 없이 바쁜 비버 및 미친 개구리 함수 모두 1이다. 단, m, n 모두 2 이상인 경우 자명하지 않으며, 그 크기가 커짐에 따라 값 또한 계산할 수 없을 정도로 빠르게 커지며, 어느 정도 큰 크기에서는 계산 불가능해진다.
현재까지 결과에 따르면 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경을 넘는다.
삑삑거리는 바쁜 비버 함수도 같은 방법으로 일반화할 수 있으며, m개의 상태, n개의 기호에 대해 BBB(m, n)과 같은 식으로 나타낸다.
3.8. 세미 바쁜 비버 함수
모든 계산 가능한 함수보다 점근적으로 빠르게 증가하면서도, 바쁜 비버 함수보다는 한 차원 느리게 증가하는 함수[23] [math(f)]가 존재하는가를 생각해볼 수 있다. 그에 대한 대답은 "예"이다.대충 설명하자면, [math({\rm BB}(n))]에 대한 오라클을 가지고 있어서 바쁜 비버 함수를 계산할 수 있는 머신은 튜링 머신에 대한 정지 문제를 해결하는게 가능하다. 그런데 모든 계산가능한 함수보다 점근적으로 빠르게 증가하는 어떤 함수 [math(f)]에 대한 오라클을 가진 머신이 튜링 머신에 대한 정지 문제를 해결할 수 없는 경우가 존재한다. 따라서 모든 계산가능한 함수보다 빠르게 증가하면서 바쁜 비버보다는 한 차원 느리게 증가하는 함수 [math(f)]가 존재한다.
더 나아가 생각해보면 [math({\rm BB}(n))]에 대한 오라클을 가지고 있는 튜링 머신이 계산할 수 있는 모든 함수보다 점근적으로 빠르게 증가하면서도, [math({\rm BB}_{2}(n))]보다는 한 차원 느리게 증가하는 함수가 존재하는가를 생각해볼 수 있다. 이를 일반화하면 임의의 서수 [math(k)]에 대해 [math({\rm BB}_{k}(n))]에 대한 오라클을 가진 머신이 계산할 수 있는 모든 함수보다 점근적으로 빠르게 증가하면서도 [math({\rm BB}_{k+1}(n))]보다는 한 차원 느리게 증가하는 함수가 존재하는가를 생각해볼 수 있다.
4. 역사
m, n이 비교적 작은 값일 때 바쁜 비버 함수의 참값을 구하기 위해 1960년대부터 여러 수학자가 공헌하였다.4.1. BB(2, 2)~BB(4, 2)
- BB(2, 2)=4, FF(2, 2)=6인 것은 약간의 시간과 종이만 있다면 사람이 손으로 직접 계산할 수 있는 수준이다.
- BB(3, 2)=6, FF(3, 2)=21임은 1963년에 Rado에 의해 증명되었다.
- Brady는 1964년 BB(4, 2)=13, FF(4, 2)=107로 추측했으며, 1974년에 같은 사람이 완전히 증명하였다.
4.2. BB(5, 2)
- 1964년에 처음 제기된 BB(5, 2)의 값은 17이다.
- 8년 후 BB(5, 2)=22, FF(5, 2)=435로 커졌다가, 다시 1년 후에 각각 40, 556으로 갱신되었다
- 1980년대에는 BB(5, 2)의 값은 112, 501, 1915로 갱신되었고, FF(5, 2)의 값은 7707, 134467, 2133492로 갱신되었다. 이후 더 적은(1471개)의 1을 쓰면서 더 많이 움직이는(2358064회) 튜링 머신이 발견되었다.
- Marxen과 Buntrock이 1989년 4098개의 11,798,826번 이동하는 5-상태 튜링 머신을 발견했으며, 이후 23,554,764번 이동하고 4097개의 1을 쓰는 튜링 머신을 발견했다.
- 이듬해인 1990년, 4098개의 1을 쓰며, 47,176,870번 이동하는 튜링 머신이 발견되었으며, 이를 넘어서는 튜링 머신은 33년째 발견되고 있지 않다. 이후에도 4096~4098개의 1을 쓰는 튜링 머신이 몇 가지 발견되었으나, 그 어떤 것도 4099개 이상의 1을 쓰면서 멈추는 튜링 머신은 나오지 않았다.
- 2009년에는 70,740,810번 이동하는 튜링 머신이 발견되었다는 결과가 나왔으나 오류로 밝혀졌다.
- Skelet은 아직까지 정지 여부를 증명 못한 튜링 머신은 총 164개가 존재함을 밝혔고, 그 중 42개만이 일명 "hardly non-regular, HNR", 즉 어렵고 불규칙한 튜링 머신이라고 밝혔다. 이후 이를 목록화 하였는데, BL-2(Binary linear-2) 클래스에 해당하는 튜링 머신 1개(27번)가 추가되어 총 43개의 리스트가 있다. 이 리스트를 skelet list라 부른다.
- 현재 BB(6, 2)와 함께 가장 활발하게 연구되고 있는 튜링 머신이며, 이 남아있는 튜링머신들이 모두 정지하지 않음이 증명되면 BB(5, 2)=4098, FF(5, 2)=47,176,870로 확정된다.
- 스콧 애런슨 교수는 2020년 논문을 통해 BB(5, 2)=4098, FF(5, 2)=47,176,870이 정확한 값이라고 추측하고 있다. 또한 정지 여부가 증명되지 않은 튜링 머신들은 최소 1011번 이상 이동했으며, 만약 FF(5, 2)≠47,176,870이면 FF(5, 2)>1011이다.
4.2.1. skelet list
- 우선 이 단락을 보기 전에 알아두어야 할 것은, 리스트에 BL-2 튜링 머신을 포함시키느냐 포함시키지 않느냐에 따라 번호가 달라지는데, 1~26번까지는 동일하지만 27번을 BL-2로 놓는다면 나머지 HNR은 28-43으로 밀린다. BL-2가 제외된 리스트에서는 27-42가 HNR이며, BL-2를 43번으로 포함시키는 경우도 있다. 이 문서에서는 27번을 BL-2로 놓고, 나머지를 28-43으로 놓는다.
- skelet의 list에서는 시작 상태를 A상태로 정의하며, A상태에서 1을 보고 정지하지 않는 경우 B상태에 정지 상태를 놓는다.
- 1~13번은 B상태에서 0을 만나면 정지한다.
- 14~20번은 A상태에서 1을 만나면 정지한다.
- 21~43번은 B상태에서 1을 만나면 정지하며, 특히 39~43번은 A상태에서 B상태로 바꾼다.
- 2013년까지 이 중 2, 5, 6, 8, 11, 14, 18, 20~22, 25, 28, 31, 39번까지 총 14개의 튜링 머신이 정지함이 증명되었다.
- Daniel Briggs의 논문에 따르면 다음과 같이 묶인 튜링 머신 쌍들은 충분한 스텝 이후에는 서로 동일해지는 것들이다. (2, 5, 6), (12, 13), (23, 29), (21, 28, 39), (30, 41). 또한, (16, 24, 38)이 동일하고, (19, 42)가 동일하다고 추측되고 있다.[24]
- 추가로, 9, 10, 12, 13, 32번이 증명되었으며, 사실상 19개의 구분된 튜링 머신이 남게 되었다.
- 1번 튜링 머신의 정지 여부를 증명하는 것은 매우 빡센 듯하다. 스켈렛 리스트 가운데에서도 활발하게 연구되어 왔지만 이렇다 할 결과가 나오지 않는 상황이다.
- 3, 7번은 유사하게 움직이는 경향을 보인다.
- 15번은 최소 3.56*1029회 움직인다고 증명되었다. 26번과 동일한 경향을 가짐이 2023년 증명되었고, 아래의 34번에서 얻은 결과를 비추어 보면 무한하다고 추측된다.
- 34번은 2023년에 Ligocki에 의해 정지하지 않는다고 증명되었다. 35번 또한 34번과 거의 같은 튜링 머신인데, 34번과 같은 형태로 행동하고, 정지하지 않음이 2023년 증명되었다. 33번도 34, 35와 유사한 점이 있지만 미묘한 차이가 있는데, 2023년 12월 coq를 이용한 자동증명을 통해 33번이 멈추지 않음이 증명되었다.
- 36, 37번은 정지하지 않는다.
- 이 외에도 4, 23, 27(BL-2), 29번은 상당한 진전이 있었으며, 조금만 보완하면 쉽게 정지하지 않음이 증명될 수 있다고 여겨진다.
- 5-상태 튜링 머신이 워낙 방대한 양이라 여러 사람이 연구하고 있고, 이러한 점으로 인해 정보 교환이 잘 되지 않은 부분이 존재한다. Ligocki는 이러한 데이터를 최대한 낙관적으로 모두 종합하면[25], 사실상 1번의 정지 여부만 증명하면 BB(5)의 값을 완벽히 증명할 수 있다고 보고 있다. 문제는 1번 튜링 머신의 난이도가 상상 이상으로 높다는 것인데, 재설정 과정이 다른 멈추지 않는 튜링 머신들과 달리 상당히 이상하기 때문에 증명에 애를 먹고 있다. 심지어 멈출 수도 있는데[26], 101000 이상의 과정 끝에 멈추거나, 무한 루프에 빠지거나, 정지 혹은 비정지의 단서를 찾게 될 가능성 또한 열려 있다. 다만 현재는 translated cycler 방식을 이용하면 1번 튜링머신 또한 무한하다고 추측된다. bbchallenge 상에서는 skelet의 연구 결과와는 별개로 2023년 5월 기준 널리 검증되지 않은 32632개의 튜링 머신이 남아 있다.
4.3. BB(6, 2)
- 1964년에 처음 제기된 BB(6, 2)의 값은 35이다.
- 8년 후 BB(6, 2)=42, FF(6, 2)=522로 하한값이 올라갔다가, 이후 1980년대 BB(6, 2)의 값은 117, 2075로, FF(6, 2)의 값은 13488, 4208824로 갱신되었다.
- 1990년에, BB(5, 2)의 현 하한값을 발견한 동일한 수학자 Marxen, Buntrock이 BB(6, 2)>=95,524,079임을, FF(6, 2)>=8,690,333,381,690,951임을 보였다.
- 이후 갱신되지 않고 있는 BB(5, 2)와 달리 BB(6, 2)는 지금도 하한값이 계속 올라가고 있는데, 2000년 7월에는 BB(6, 2)>2.5×1021, 8월에는 BB(6, 2)>6.4×10462가 되었다. 이듬해 2월에는 1.2×10865까지 상승하면서, BB(5, 2)와 격차를 엄청나게 크게 벌리고 있다.
- 2007년 Terry와 Ligocki는 BB(6, 2)>4.6×101439, FF(6, 2)>2.5×102879임을 보였고, 2010년 Kropitz는 BB(6, 2)>3.5×1018267, 7.4×1036534임을 보였다.
- 이후 12년 뒤인 2022년에 이전에 상한값을 발견했던 Ligocki와 Kropitz가 [math({\rm BB}(6)≥10 \uparrow \uparrow 5)]임을 찾아냈고, 바로 얼마 후에는 [math({\rm BB}(6)≥10 \uparrow \uparrow 15)]인 튜링 머신을 찾아냄으로서 하한값이 테트레이션 단계를 돌파하게 되었다.
4.4. BB(7, 2) 이상
- 1964년에 제기된 BB(7, 2)의 하한값은 22961이다.
- 특히 BB(6, 2)가 빠르게 커지다 보니 7개 이상의 상태를 가지는 튜링 머신은 연구하기 힘든 관계로 상대적으로 주목을 못 받는 상황이었고, 1990년 BB(6, 2)가 BB(7, 2)의 하한값을 돌파하고 나서도 따로 갱신되지 않고 있었다.
- 그러다 2014년 googology wiki의 한 유저인 wythagoras가 2014년 BB(7, 2)가 [math(10^{10^{10^{10^{18,705,352}}}})]보다 크다는 사실을 증명했다. 테트레이션으로 나타내면 [math(8 \uparrow \uparrow 6)]에 근사한다. 그러나 이 값도 2022년 BB(6, 2)에 의해 다시 역전되었으며, 새로운 하한값이 따로 제시되지는 않았다.
- 8개 이상의 상태를 갖는 튜링 머신은 1964년 Green[27]이 제시한 Green machine을 이용해 3 이상의 n에 대해 [math({\rm BB}(2n)≥3 \uparrow^{n-2} 3)]임을 제시했는데, 이로 인해 [math({\rm BB}(8)≥7,625,597,484,987)], [math({\rm BB}(10)≥3 \uparrow \uparrow \uparrow 3)], [math({\rm BB}(12)≥3 \uparrow \uparrow \uparrow \uparrow 3)]인 채로 60년 가까이 남아있다. 그나마 10~12의 경우 아직 역전되지 않았으나 BB(8, 2)의 경우 2000년 BB(6, 2)에 역전당한 이후 아직도 더 나은 하한값을 찾지 못하고 있는 상황이다.
4.5. BB(2, 3)
- Brady는 1988년 BB(2, 3)=9, FF(2, 3)=38로 추측했다.
- 2007년 2개의 상태, 3개의 기호를 갖는 모든 튜링 머신들의 정지 여부를 증명하면서 BB(2, 3)=9, FF(2, 3)=38임이 확정되었다.
4.6. BB(3, 3)
- 1963년 Lee는 12개의 기호를 쓰면서 44회 움직이는 튜링 머신과 9개의 기호를 쓰면서 57회 움직이는 3상태, 3기호 튜링 머신을 찾았다.
- 2004년 BB(3, 3)은 각각 208, 5600, 13949로, FF(3, 3)은 각각 40737, 29,403,894, 92,649,163으로 갱신되었다.
- 이후 2007년까지 이어진 지속적인 연구로 나온 최신 하한값은 BB(3, 3)=374,676,383이고 FF(3, 3)=119,112,334,170,342,540이다. 그러나 이후 16년동안 갱신되고 있지 않다.
4.7. BB(2, 4)
- Brady는 1988년 BB(2, 4)=90, FF(2, 4)=7195인 튜링 머신을 발견했다.
- 2005년 Terry와 Ligocki는 BB(2, 4)=2050, FF(2, 4)=3,932,964인 튜링 머신을 찾았다.
- 이후 18년째 증명도 되지 않고 있고, 갱신 소식 역시 감감무소식이다. 단, 2개의 상태와 4개의 기호를 갖는 튜링 머신들 중 증명되지 않은 것들은 최소 2억 회 이상 이동한다. 즉 FF(2, 4)≠3,932,964이면 FF(2, 4)>2×108이다.
4.8. BB(2, 5) 이상
- 2005년 BB(2, 5)=4099, FF(2, 5)=16,268,767로 제시되었다.
- 갱신되고 있지 않은 BB(5, 2)와 달리 BB(2, 5)는 2007년까지 계속 갱신되어 왔으며, 현재는 BB(2, 5)>1.7×10352, FF(2, 5)>1.9×10704이다. 다만 BB(2, 5)가 [math(7.3\times10^{19016})]을 넘는다는 결과가 있으나 아직 검증되지 않았다. 동시에 FF(2, 5)는 [math(6.5\times10^{38033})]이다.
- BB(2, 6)의 최신값은 1.9×104933, FF(2, 6)>2.4×109866이다. 최근 유의미한 연구결과가 나오고 있지는 않으나, BB(6, 2)가 테트레이션 단계에 들어선 만큼 이 또한 테트레이션 단계를 넘어설 것으로 보인다. 실제로 2023년 4월에 나온 연구 결과에 따르면 10↑↑70을 넘어선다. 그리고 5월에 다시 갱신되었는데 10↑↑91개의 기호를 쓰는 튜링 머신이 발견되었다가 이번에는 아예 10↑↑10↑↑101000긍갈라개(!)의 기호를 쓰는 튜링 머신까지 나왔으며, 이 값은 10↑↑↑3을 한참 넘어선다.[28]
- BB(4, 3)>1.3×107036, FF(4, 3)>1.0×1014072이고, BB(3, 4)>3.7×106518, FF(3, 4)>5.2×1013036이다. 다만 이들 역시 테트레이션 단계를 넘어설 가능성이 높다. 실제로 BB(3, 4)>10↑↑2048임이 밝혀졌다. 다만 BB(4, 3)의 경우 2023년 6월 기준 갱신되지 않고 있다.[29]
- 7개 이상의 기호를 가지는 바쁜 비버 함수 및 상태 수와 기호 수의 곱이 15 이상인 바쁜 비버 함수에 대해에서는 논의된 바 없다. 당장 mn=12인 튜링 머신만 해도 테트레이션, 심지어 펜테이션을 넘보고 있는 마당에 이들은 연구하기 매우 힘들 것이다.
- 현재 나온 최신 연구결과들은 대부분 2008년에 나온 것이며, 2개의 기호를 갖는 튜링 머신에 비해 연구 진전이 느린 편이라 2023년 BB(2, 6)의 값이 업데이트 되기 전까지 참값이 증명되거나 갱신되지 않고 있었다.
4.9. BBB 함수
- 삑삑거리는 바쁜 비버 함수는 2020년 스콧 애런슨 교수에 의해 제시된 개념으로, 2차 바쁜 비버 함수에 대한 오라클 질의 과정의 대안으로 나온 최신 함수이다. 이 함수의 계층이 2차 바쁜 비버 함수와 동일함이 해당 논문에 증명되어 있다.
- BBB(1)=1, BBB(2)=6임은 해당 개념을 만든 애런슨 교수가 직접 보였으며, BBB(3)=55로 추측하고 있으나, 현재까지 완벽히 증명되지는 않았다.
- BBB(4)는 처음 제시된 값은 66349였지만 2021년 Drozd가 32,779,478로 갱신시켰다.
- BBB(5)의 경우 처음 제시된 값은 2.1×1018이지만, 현재는 ligocki가 [math(10^{10^{286574}})]까지 갱신했다.
- Drozd가 BBB(2, 3)의 값을 59로 제시했으며, 이를 넘어서는 준정지하는 튜링 머신은 없다고 밝혔으나, 아직 정확하게 검증되지는 않았다. 또한 BBB(3, 2)=55 또한 정확한 값이라고 주장하고 있다.
- 현재까지 연구된 바에 의하면 BBB(2, 4)>2.0×1023이고, BBB(3, 3)>7.2×1062이다.
5. 응용
바쁜 비버는 수학적 난제를 증명하는 새로운 접근 방법을 제시한다. 예를 들어 리만 가설에 대한 반례가 존재하면 정지하고 아니면 영원히 동작하는 744 상태를 가진 튜링 머신을 만들 수 있다. 미친 개구리 함수는 정지하는 튜링 머신의 연산 상한이므로 [math({\rm FF}(744))]번의 연산을 거쳤을 때 이 튜링 머신이 정지하였는지 여부를 관찰하면 리만 가설의 반증 가능 여부를 가릴 수 있다. 즉 컴퓨터로 유한한 연산을 해서 리만 가설의 반례가 없음을 보일 수 있다. 아래 ZF 상에서 증명될 수 없는 상태 개수와 겨우 1개밖에 차이나지 않는다(...) 물론 745에서 상한이 더 내려온다 해도 리만 가설이 증명 불가능해지는건 아니다.비슷한 방법으로 순차적으로 검사를 해서 골드바흐 추측에 대한 반례를 찾으면 정지하는 프로그램은 27 상태 튜링 머신으로 만들수 있다. 이 튜링 머신이 [math({\rm FF}(27))]번의 연산을 했을 때 정지했는지를 확인함으로써 컴퓨터로 유한번의 연산을 해서 골드바흐 추측을 증명하는 것이 가능하다.
2021년에 나온 논문에 따르면 에르되시 추측[30]은 FF(15) 및 FF(5, 4)의 값을 구하는 것보다 어려울 수 없다. 만약 15상태의 바쁜 비버 함수값을 구할 수 있다면 FF(15)+1번의 연산을 거쳐 정지하지 않을 경우 참이 된다.
재미있는 예로, ZF 공리계가 모순된다면 정지하는 748 상태 튜링 머신을 만들 수 있다. 이를 이용해 [math({\rm FF}(748))]번의 연산을 거쳤을 때 해당 튜링 머신이 정지하는지를 확인하면 ZF 공리계의 무모순성을 증명할 수 있다.[31]
2023년에는 선택공리가 적용된 ZFC 상에서 745상태로 필요한 상태수를 3개 더 줄이는데 성공하였다. 그러나 이는 불완전성 정리로 인해 ZFC 공리계 내에서 불가능하므로, [math({\rm FF}(745))]의 값과 상한을 알아내는 것이 ZFC 공리계에서 불가능하다는 결론을 낼 수 있다. 오해하면 안되는게, 모든 [math(n)]에 대하여 완벽히 잘 정의된 함수이기 때문에 [math({\rm FF}(745))]은 정확히 고정된 유일한 자연수로 존재한다.[32] 그 값이 무엇인지 증명하는게 ZF(C) 공리계에서 불가능하다는 뜻이다. 그래서 만약 ZF(C) 공리계보다 더 강력한 공리계를 도입해 [math({\rm FF}(745))]의 값을 증명할 수 있다면 그것을 통해 더 강력한 공리계에서 ZF(C) 공리계의 무모순성을 증명하는 것이 이론적으로는 가능하다. (하지만 그 강력한 공리계를 증명할 수 없다.) 또한 [math({\rm FF}(27))]을 ZF(C) 공리계에서 구하는 것이 가능하다면, 골드바흐의 추측이 ZF(C) 공리계와 독립이 아니라는 근거가 될 것이다.
하지만 이 방법은 현실성이 없다. 위에서도 수차례 언급했듯이 미친 개구리 함수는 정신나갈 정도로 빠르게 증가하기 때문에 상태가 조금만 커져도 우주가 끝날 때까지 컴퓨터를 돌려도 증명 결과는 나오지 않을 것이다
즉 이 증명법에는 치명적인 문제가 있는데 [math(n)]이 5 이상일 때의 미친 개구리 함수의 정확한 값을 현재로서는 모르며, ZF 공리계에서 값을 알아내는 것이 불가능 할 수 있다는 것과, 그 값이 초월적으로 크다는 것이다. [math({\rm FF}(6))]이 우주 전체의 계산 능력을 아득히 넘어서는 [math(10\uparrow \uparrow 15)]보다 훨씬 크다는 것부터 답이 없다. 컴퓨터로 반례를 찾아내는 방식으로 수학 문제를 풀 때 필요한 연산의 수를 무한에서 유한으로 끌어 내렸다는 수학적 의미만 있을 뿐 실용적인 증명법으로는 사용할 수 없다. 사실 리만 가설, 골드바흐 추측, 에르되시 추측을 증명하겠다고 바쁜 비버 함수를 활용하는것 자체가 닭 잡는데 소잡는 칼을 활용하는 격으로, 가설을 풀기 위해서는 해당 가설과 동치인 튜링 머신만 확인해도 되지만 바쁜 비버 함수값을 구하기 위해서는 그 상태 개수에서 가능한 모든 튜링 머신을 전수조사해야 하며 그 과정에서 해당 가설과 동치인 문제들에 대한 해답도 자연스레 나오게 된다.
6. 참고문헌 및 외부 링크
- Scott Aaronson 교수의 글 "큰 수들"
- 위키피디아 문서 Busy beaver
- googology 위키 문서 Busy beaver
- BB(5)의 값을 구하는 온라인 프로젝트
- 스콧 애런슨 교수가 2020년에 쓴 논문. 이 문서의 내용 상당수는 이 글을 출처로 삼고 있다.
- 최근 바쁜 비버 함수의 값들을 연구해온 사람인 ligocki의 홈페이지.
[1] 반드시 정지한다는 조건이 없다면 그냥 처음부터 계속 1만 찍어내면서 이동하면 그만이다.[2] 이는 3상태 머신의 최대 이동값은 아니다. 아래 미친 개구리 함수 참조.[3] 약 4100.[4] BB(7)은 2014~2022년 이전에는 10^^6 정도의 매우 약한 하한이 알려져 있었으나, 이미 BB(6)에서 이 값을 아득하게 초과하였다. BB(6)이 테트레이션 레벨임에 따라 비록 현재 펜테이션 레벨의 하한값은 10이지만 BB(7)부터 최소 펜테이션 레벨일 가능성이 매우 높다.[5] 사실 바쁜 비버함수 10,11,12의 값은 [math({\rm BB}(6))]의 값이 27보다 크다는 사실에서 하한을 정한 것이다. 아래에도 언급되어 있지만 1964년 Green이 특정 종류의 튜링 머신을 이용해 밝혀낸 것으로, 최근 연구결과에서 [math({\rm BB}(6))]의 값이 [math(10\uparrow\uparrow15)] 이상이라는 사실이 밝혀졌으므로 10~12에 해당하는 값들은 현재 제시되어있는 하한값보다 비교도 안되게 클 것이다. 어쩌면 모우저처럼 화살표 갯수 조차 물리적으로 표현하기 불가능할 정도로 많아 화살표를 윗첨자로 나타내야 표현이 가능한 수치일 수도 있다. 당장 상태 4개만 더 추가된 BB(16)부터 그레이엄 수를 아득히 초과한다고 추측되는 마당에...[6] 그레이엄 수 뿐만 아니라 [math(G(G(1)))], [math(G(2\uparrow \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow \uparrow 9))]보다도 크다.[7] 로더의 수 라고 불리는 이 수는 fgh로 측정 불가능한 계산 가능한 수다.[8] 다시 말하면, 바쁜 비버 함수는 초등함수를 유한 번 사용해서 표현할 수도, 테일러 급수, 푸리에 급수 등으로 극한을 구할 수도 없다.[9] 실제로 튜링 머신 중 사실상 같은 튜링 머신으로 볼 수 있는 것도 많고, 자명하게 제외되는 경우도 많아서 실제 계산해야 하는 수는 이보다 훨씬 적으며, BB(2)의 값은 튜링 머신의 작동 원리만 파악하면 수기로 계산할 수 있다. 물론 상태가 3개 이상이어도 자명한 튜링 머신들을 제거할 수 있지만, 2개 상태를 가지는 경우 자명한 튜링 머신을 제거하면 남는 것은 얼마 없지만, 3~4개의 경우 제거하고도 많이 남기 위해 참값을 구하는 것 하나로 논문 한 편을 써야 할 정도이고, 5개 이상인 경우 아직까지 완벽하게 증명하지 못했다.[10] 윗 문단에서 설명한 대로 정지 상태가 딱 하나라는 조건을 추가하면 실제 고려해야 할 튜링 머신은 [math((4n)^{2n}/2)]가지로 줄일 수 있다.[11] 팩토리얼보다 빠른 성장률이다.[12] 정지시에는 당연히 1을 적어야 하며, 왼쪽 오른쪽 이동을 따지는 것도 무의미하기 때문에 4(n+1)이 아니다.[13] 아래의 일반화 바쁜 비버 함수와 관련해서 n개의 상태와 m개의 기호를 가지는 튜링 머신은 [math((2mn+1)^{mn})]가지 존재한다. 여기서도 정지 상태가 딱 하나라는 조건을 추가하면 [math((2mn)^{mn}/2)]가지로 줄일 수 있다.[14] [math((0,\,1) \cup (1,\,\sqrt[e]{e}\;\!])[15] 표기가 같은 프레넬 사인 적분 함수와 혼동될 수 있으므로 주의.[16] 단, 21번 움직이는 튜링 머신은 1을 5개밖에 쓰지 못한다. 1을 6개 쓰는 튜링 머신은 상술되어 있는 최대 14회 움직이는 튜링 머신이다.[17] 만약 튜링 머신이 1초에 한번씩 움직인다면 4 상태 비버가 멈추는 데는 2분이 채 걸리지 않지만, 5 상태 비버가 멈추려면 546일이 걸린다. 546일이면 육군 기준 입대할 때 튜링 머신이 움직이기 시작했다면 전역할 때가 되어야 멈춘다. 물론 6 상태 이상인 비버는 우주가 멸망할 때까지 멈추지 않을 것이다.[18] 다만 [math({\rm BB}(6))]보다 크고 이 값도 지수탑을 15개 쌓아야 하지만 현재 1등인 6 상태 기계 또한 10↑↑16보다는 작다.[19] 이 경우 주로 BB(n)은 최대 쉬프트 함수로 간주하고, 대신 라도 시그마 함수를 Σ(n)으로 종종 표시한다. 아래의 스콧 애런슨 교수도 이렇게 표기했다.[20] 21번 이동하는 3상태 튜링 머신은 1을 최대 5개밖에 쓰지 못한다[21] 피쉬 수 4의 성장률은 대략 [math({\rm BB}_{ω^{ω+1}63+1}(n))] 정도 된다.[22] [math(ω_{\sf ZF})]는 ZF 공리계에서 존재성을 증명할 수 있는 모든 가산 서수의 상한이다.[23] 여기서 '한 차원 느리게'의 의미는 이 함수에 대한 오라클을 가진 머신이 바쁜 비버 함수를 계산할 수 없음을 의미한다. 단순히 '점근적으로' 모든 계산 가능한 함수보다 빠르게 증가하면서도, 바쁜 비버 함수보다는 느리게 증가하는 함수는 바쁜 비버 함수에 로그를 취하는 등의 쉬운 방법만으로 만들어낼 수 있으므로 자명하게 존재한다.[24] 다만 이 논문에서는 20, 22번이 미증명된 것으로 간주되었다.[25] Skelet list 외에 남아 있는 튜링 머신이 없고, 목록의 증명에 모두 오류가 없는 경우[26] 34번을 증명한 Ligocki의 말에 따르면 약 10% 확률로 멈출 수도 있다고 보고 있다[27] 앞선 BB(5, 2)~BB(7, 2)를 제시한 사람이다[28] 비록 60년 전 결과긴 하나 펜테이션에 이른다고 증명된 값이 BB(10, 2)는 되어야 했음을 감안하면 필요한 기호 혹은 상태의 개수가 엄청나게 줄어든 거다[29] 아예 결과가 없었던 것은 아닌데 [math({\rm BB}(4, 3)≥10 \uparrow \uparrow \uparrow 5)]이라는 펜테이션 레벨의 결과를 내놓은 적이 있는데 실제로 맞는지는 아직 확실하지 않다.[30] 9 이상의 n에 대해 2n을 3진법으로 나타내면 반드시 2가 1개 이상 나타난다는 가설[31] 2016년에 나온 논문에서는 7910 상태 튜링 머신이었으나 2020년까지 7910 상태 -> 1919 상태 -> 748 상태로 최적화되었다.[32] [math(n)]개 상태 튜링 머신 중 무한히 동작하지 않는 튜링 머신만 모아놓으면 그 중 가장 오래 동작하는 튜링 머신이 있다는 건 당연하기 때문이다. 정수로 이루어진 유한 집합은 최대값을 가진다는 것에서 유도된다.