바쁜 비버
1. 개요
바쁜 비버(Busy Beaver)는 계산 가능성 이론과 계산 복잡도 이론에서 흥미로운 부분이 있는 컴퓨터 프로그램으로 헝가리의 수학자 라도 티보르(Radó Tibor, 1895~1965)가 도입했다. 동물 비버가 일하는 모습과 튜링머신이 일하는 모습이 비슷하다고 해서 바쁜 비버라는 이름이 붙었다.
정지 문제와 밀접한 관련이 있으며, 수학에서 알려진 함수 중 손에 꼽힐만큼 빠르게 증가하는 함수인 바쁜 비버 함수와, 수학적 증명에서 등장한 수 중 가장 큰 수 중 하나인 바쁜 비버 수로 유명하다.
2. 바쁜 비버 게임
바쁜 비버 게임은 무한히 긴 테이프에 "0"이 빼곡히 씌어 있을 때, n개의 상태(state)를 가질 수 있는 정지하는 튜링 머신을 가지고 테이프에 최대한 많은 수의 "1"을 쓰는 게임이다. n비트 길이의 프로그램 중 가장 복잡한 프로그램을 찾는 게임이라고 이해해도 된다.
이때 n개 상태를 가지는 정지하는 모든 튜링 머신 중 가장 많은 1을 쓴 튜링 머신을 n번째 바쁜 비버라 한다.
4번째 바쁜 비버가 동작하는 모습.
3. 파생 함수
바쁜 비버의 사례를 따라서 '~ㄴ 동물' 함수로 명명된다.
3.1. 바쁜 비버 함수(라도 시그마 함수)
n번째 바쁜 비버가 쓰는 최대 1의 갯수를 대응한 함수를 바쁜 비버 함수(Busy Beaver function) $${\rm BB}(n)$$ 혹은 라도 시그마 함수(Radó's sigma function) $$\Sigma (n)$$ 이라고 한다. 당연히 바쁜 비버 함수의 정의역과 공역은 모두 자연수의 집합이다.
바쁜 비버 함수는 대표적인 계산불가능한 함수(uncomputable function)이며, 정의역과 공역이 자연수의 집합인 그 어떠한 계산가능(computable)한 함수보다도 점근적으로 빠르게 증가한다.
바쁜 비버 함수를 계산하는 대수적, 해석적인 해는커녕 기계적인 절차조차 존재하지 않기 때문에 함수값을 알아내는 것은 끔찍하게 어렵고, 작은 n에 대해서만 그 값이 알려져 있다. 알려져 있는 값으로는 $${\rm BB}(1)=1$$, $${\rm BB}(2)=4$$, $${\rm BB}(3)=6$$, $${\rm BB}(4)=13$$이며, $${\rm BB}(5)$$는 $$4098$$으로 추정되고, 그보다 큰 값에 대해서는 매우 매우 약한 하한만이 알려져 있는데, $${\rm BB}(6)$$는 $$3.5 \times 10^{18267}$$이상, $${\rm BB}(7)$$은 $$10^{10^{10^{10^{18,750,353}}}}$$이상, $${\rm BB}(10)$$은 [math(3 \uparrow \uparrow \uparrow 3)] 이상, $${\rm BB}(12)$$은 $$3 \uparrow \uparrow \uparrow \uparrow 3$$ 이상, $${\rm BB}(17)$$은 그레이엄 수 보다 크다.
어찌 보면 무한 지수 탑 함수와 성격이 비슷해 보이지만, 무한 지수 탑 함수는 일정 정의역[1]]을 벗어나면 복소수로 함숫값이 줄줄 새나가버리기에(...) 생각보다는(?) 함숫값이 작다.
3.1.1. 최강의 함수(?)
가장 빠르게 증가하는 함수를 만들기 위한 준비 작업으로 다음과 같은 수를 생각해보자.
그러나 위의 문장은 아래와 같은 모순을 만들 수 있다.1000 어절로 구성된 문장으로 표현 가능한 수 중 가장 큰 수.
이를 베리의 역설이라고 하는데 모순이 발생하는 근본 원인인 '모호성'을 해소하기 위해 다음과 같이 바꿀 수 있다.1000 어절로 구성된 문장으로 표현 가능한 수 중 가장 큰 수의 두배.
여기서 프로그램을 명확하게 정의하기 위해 튜링 머신을 사용하고, 이 수를 이용해 대응 관계를 만들어 함수를 만들면 바쁜 비버 함수가 된다.1000비트로 표현 가능한 프로그램이 결정할 수 있는 수 중 가장 큰 수.
계산이 가능하고 빠르게 증가하는 그 어떤 함수를 들고 와도 바쁜 비버 함수와 붙으면 깨지는 이유가 여기에 있다. 정의부터가 계산 가능한 함수보다는 빠르게 증가하는 함수라고 명시적으로 못박아놓은 것과 마찬가지이기 때문이다.
3.2. 미친 개구리 함수(최대 쉬프트 함수)
n번째 바쁜 비버의 최대 스탭 이동 횟수를 대응한 함수를 최대 쉬프트 함수(Maximum shifts function) $$S(n)$$[2] 혹은 미친 개구리 함수(Frantic frog function) $${\rm FF}(n)$$이라고 한다. 바쁜 비버 함수와 형제 관계인 함수로 많은 성질들을 공유한다. 미친 개구리 함수 역시 계산 불가능하며, 정의역과 공역이 자연수의 집합인 그 어떠한 계산 가능한 함수보다도 점근적으로 빠르게 증가한다. 바쁜 비버 함수보다 더 빠르게 증가하는데, 모든 $$n$$에 대하여 $${\rm FF}(n) \geq {\rm BB}(n)$$이다.
미친 개구리 함수 역시 작은 n에 대해서만 그 값이 알려져 있다. 알려져 있는 값으로는 $${\rm FF}(1)=1$$, $${\rm FF}(2)=6$$, $${\rm FF}(3)=21$$, $${\rm FF}(4)=107$$이며, $${\rm FF}(5)$$는 $$47176870$$ 이상으로 추정되고, 그보다 큰 값에 대해서는 매우 매우 약한 하한만이 알려져 있는데, $${\rm FF}(6)$$는 $$7.4 \times 10^{36534}$$ 이상, $${\rm FF}(7)$$은 $$10^{2\times 10^{10^{10^{18750353}}}}$$이상, $${\rm FF}(17)$$은 그레이엄 수 보다 크다.
미친 개구리 함수를 바쁜 비버 함수라 부르는 사람들도 있는데, 1의 개수보다 쉬프트 횟수를 기준으로 하는게 더 자연스럽다고 보는 관점 때문이다.
3.2.1. 성질
여기에 제시된 성질은 $${\rm FF}(n)$$뿐만 아니라 $${\rm BB}(n)$$에도 그대로 적용된다.
n 상태 튜링 머신이 정지하는지 결정하기 위해서는 미친 개구리 함수의 정의를 이용해서 튜링 머신이 $${\rm FF}(n)$$ 스탭만큼 돌렸을 때 정지했는지 확인하면 된다. 만약 정지하지 않았다면 해당 머신은 영원히 동작한다. 이는 미친 개구리 함수를 계산 가능한 튜링 머신은 정지 문제를 풀 수 있다는 것을 의미한다. 즉 바쁜 비버는 정지 문제와 튜링 동치이다.$$f : {\mathbb N} \mapsto {\mathbb N}$$이고 $$f(n) \geq {\rm FF}(n)$$인 어떤 함수 $$f(n)$$에 대해 계산이 가능한 연산 장치는 자기 자신에 대한 정지 문제를 해결할 수 있다. 따라서 $${\rm FF}(n)$$과 $${\rm FF}(n)$$의 상한인 $$f(n)$$은 계산 불가능하다.
$${\rm FF}(n)$$이 계산가능한 모든 함수보다 점근적으로 빠르게 증가한다는 뜻이다.$$f : {\mathbb N} \mapsto {\mathbb N}$$인 모든 계산 가능한 함수는 $$n \geq n_{f}$$에 대해 $${\rm FF}(n) > f(n)$$ 이 성립하는 $$n_{f}$$가 존재한다.
$${\rm FF}(n)$$은 모든 $$n$$에 대하여 완벽히 잘 정의된 함수이지만, 불완전성 정리로 인해 $${\rm FF}(n)$$에서 $$n$$이 커지게 되면 그 값을 절대로 알아낼 수 없다. 더 강력한 공리계를 도입해도 $$n_{T}$$의 하한이 증가할 뿐 미지의 경계는 사라지지 않는다. 2020년 기준으로 ZF 공리계가 $${\rm FF}(748)$$을 결정할 수 없다고 증명되었으며, 계산 복잡도 이론의 권위자인 Scott Aaronson 교수는 ZF 공리계가 $${\rm FF}(20)$$의 값을 증명할 수 없고, 페아노 공리계는 $${\rm FF}(10)$$의 값을 증명할 수 없다고 추측하고 있다.공리계 $$T$$가 계산가능하고 산술적으로 건전하다면 $$n \geq n_{T}$$에 대해 "$${\rm FF}(n) = k$$" 형식의 문장을 $$T$$에서 증명할 수 없는 $$n_{T}$$가 존재한다.
3.3. 고차 바쁜 비버 함수
바쁜 비버 함수는 계산 불가능한 함수이다. 즉 튜링 머신으로 계산하는게 불가능하다. 만약 튜링 머신에 임의의 $${\rm BB}(n)$$을 구할 수 있는 장치인 오라클(Oracle)을 붙여서 바쁜 비버 함수를 계산할 수 있는 가상의 슈퍼 튜링 머신을 가정한다면, 슈퍼 튜링 머신에서의 바쁜 비버 함수인 2차 바쁜 비버 함수 $${\rm BB}_{2}(n)$$를 생각할 수 있다.
2차 바쁜 비버 함수는 바쁜 비버 함수를 초월하는 속도로 빠르게 증가하며, 슈퍼 튜링 머신으로 계산 불가능하며, 슈퍼 튜링 머신으로 계산할 수 있는 그 어떤 함수보다도 빠르게 증가한다. 예를 들어 $$({\rm BB \circ BB})(n)$$ 같은 괴물같은 함수라도 $${\rm BB}_{2}(n)$$가 증가하는 속도를 조금도 쫓아가지 못한다.
여기서 끝나지 않고, 2차 바쁜 비버 함수를 구할 수 있는 오라클을 슈퍼 튜링 머신에 붙여 만든 슈퍼 슈퍼 튜링 머신으로 3차 바쁜 비버 함수 $${\rm BB}_{3}(n)$$를 만들 수 있다. 또 이를 $${\rm BB}_{4}(n)$$, $${\rm BB}_{5}(n)$$ ...로 무한히 확장해 나가는 방법으로 더욱 빠르게 증가하는 함수를 만들 수 있다.
이런 무한번의 확장을 초월하기 위해 자연수 전체 k에 대해 k차 바쁜 비버 함수를 모조리 계산할 수 있는 오라클을 가진 튜링 머신을 만들고, 이를 이용해 ω차 바쁜 비버 함수 $${\rm BB}_{ω}(n)$$라는 정신나간 함수를 만들 수 있다. 여기서 ω는 가장 작은 가산 무한 서수이다.
또 $${\rm BB}_{ω}(n)$$를 오라클로 쓰는 튜링 머신으로 $${\rm BB}_{ω+1}(n)$$를 정의할 수 있고, $${\rm BB}_{ω+2}(n)$$, $${\rm BB}_{ω+3}(n)$$ ...로 무한히 확장하고, 이를 초월해서 아무 자연수 k에 대해 $${\rm BB}_{ω+k}(n)$$를 모조리 계산할 수 있는 오라클을 사용하는 튜링 머신으로 $${\rm BB}_{ω2}(n)$$을 만들고, 이걸 또 오라클로 써서 정의한 $${\rm BB}_{ω3}(n)$$, $${\rm BB}_{ω4}(n)$$ ...로 무한히 확장, 또 한단계 더 초월한 $${\rm BB}_{ω^{2}}(n)$$, $${\rm BB}_{ω^{3}}(n)$$, $${\rm BB}_{ω^{4}}(n)$$ ... 한단계 또 초월한 $${\rm BB}_{ω^{ω}}(n)$$, $${\rm BB}_{ω^{ω^{ω}}}(n)$$, $${\rm BB}_{ω^{ω^{ω^{ω}}}}(n)$$ ... 한단계 또 초월한 $${\rm BB}_{\epsilon_{0}}(n)$$, $${\rm BB}_{\epsilon_{1}}(n)$$, $${\rm BB}_{\epsilon_{2}}(n)$$ ... 한단계 또 초월한 $${\rm BB}_{\zeta_{0}}(n)$$, $${\rm BB}_{\zeta_{1}}(n)$$, $${\rm BB}_{\zeta_{2}}(n)$$ ... ... ... ... ... ... $${\rm BB}_{ω_{\sf ZF}}(n)$$[3] 이런 식으로 정신나간 뇌절을 하는게 가능하다. 이 과정을 무한히 이어나갈수는 없는데, 매우 큰 서수가 존재함을 증명하려면 더 강력한 공리계를 필요로 하기 때문이다. 즉 더 강력한 공리계를 들고올수록 더 빠르게 증가하는 함수와 큰 수를 만드는게 가능하다.
바쁜 비버 함수의 확장은 또 다른 함수인 무한 시간 튜링 머신 바쁜 비버 함수(Infinite Time Turing Machine Busy Beaver function) $${\rm BB}_{\infty }(n)$$과도 밀접하게 연관된다.
3.4. 차분한 오리너구리 함수
차분한 오리너구리 함수(Placid platypus function) $${\rm pp}(n)$$은 튜링 머신이 n개의 1을 출력하기 위한 최소한의 상태 갯수로 정의된다. 즉 바쁜 비버 함수의 역관계이다.
$${\rm BB}^{-1}(n) = {\rm pp}(n) \Leftrightarrow {\rm pp}^{-1}(n) = {\rm BB}(n)$$
[1] [math((0,\,1) \cup (1,\,\sqrt[e]{e}\;\!])[2] 표기가 같은 프레넬 사인 적분 함수와 혼동하지 말 것.[3] $$ω_{\sf ZF}$$는 ZF 공리계에서 존재함을 증명할 수 있는 모든 계산가능한 서수의 상한이다.
3.5. 피곤한 웜뱃 함수
피곤한 웜뱃 함수(Weary wombat function) $${\rm ww}(n)$$은 튜링 머신이 $$n$$개의 1을 출력하기 위해 필요한 최소한의 쉬프트 횟수로 정의된다. 즉 미친 개구리 함수의 역관계이다.
3.6. 일반화 바쁜 비버 함수
튜링 머신이 사용할 수 있는 기호가 0과 1보다 많은 경우의 바쁜 비버 함수와 미친 개구리 함수를 생각할 수 있다. 이변수함수 꼴인 $${\rm BB}(n,\,m)$$과 $${\rm FF}(n,\,m)$$은 $$n$$개 상태와 $$m$$개 기호를 사용하는 튜링 머신에 대한 바쁜 비버 함수와 미친 개구리 함수이며, 이를 일반화 바쁜 비버 함수와 일반화 미친 개구리 함수라 한다.
3.7. 세미 바쁜 비버 함수
모든 계산 가능한 함수보다 빠르게 증가하면서도, 바쁜 비버 함수보다는 한차원 느리게 증가하는 함수 $$f$$가 존재하는가를 생각해볼 수 있다. 그에 대한 대답은 "예"이다.
대충 설명하자면, $${\rm BB}(n)$$에 대한 오라클을 가지고 있어서 바쁜 비버 함수를 계산할 수 있는 머신은 자기 자신에 대한 정지 문제를 해결하는게 가능하다. 그런데 모든 계산가능한 함수보다 점근적으로 빠르게 증가하는 어떤 함수 $$f$$에 대한 오라클을 가진 머신이 자기 자신에 대한 정지 문제를 해결할 수 없는 경우가 존재한다. 따라서 모든 계산가능한 함수보다 빠르게 증가하면서 바쁜 비버보다는 한 단계 느리게 증가하는 함수 $$f$$가 존재한다.
4. 응용
바쁜 비버는 수학적 난제를 증명하는 새로운 접근 방법을 제시한다. 예를 들어 리만 가설에 대한 반례가 존재하면 정지하고 아니면 영원히 동작하는 744 상태를 가진 튜링 머신을 만들 수 있다. 미친 개구리 함수는 정지하는 튜링 머신의 연산 상한이므로 $${\rm FF}(744)$$번의 연산을 거쳤을 때 이 튜링 머신이 정지하였는지 여부를 관찰하면 리만 가설의 참 거짓 여부를 가릴 수 있다. 즉 컴퓨터로 유한한 연산을 해서 리만 가설을 증명할 수 있다. 안타깝게도 미친 개구리 함수가 정신나갈 정도로 빠르게 증가하는 함수이기 때문에 우주가 끝날 때까지 컴퓨터를 돌려도 증명 결과는 나오지 않을 것이다.
비슷한 방법으로 순차적으로 검사를 해서 골드바흐의 추측에 대한 반례를 찾으면 정지하는 프로그램은 27 상태 튜링 머신으로 만들수 있다. 이 튜링 머신이 $${\rm FF}(27)$$번의 연산을 했을 때 정지했는지를 확인함으로써 컴퓨터로 유한번의 연산을 해서 골드바흐 추측을 증명하는게 가능하다.
재미있는 예로, ZF 공리계가 모순된다면 정지하는 748 상태 튜링 머신을 만들 수 있다. 이를 이용해 $${\rm FF}(748)$$번의 연산을 거쳤을 때 해당 튜링 머신이 정지하는지를 확인하면 ZF 공리계의 무모순성을 증명할 수 있다.[4] 그러나 이는 불완전성 정리로 인해 불가능하므로, $${\rm FF}(748)$$번째의 연산에서 튜링 머신이 정지했는지 여부를 절대로 알 수 없으며, $${\rm FF}(748)$$의 상한값을 알아내는 것이 ZF 공리계에서 불가능하다는 결론을 낼 수 있다.오해하면 안되는게, 모든 $$n$$에 대하여 완벽히 잘 정의된 함수이기 때문에 $${\rm FF}(748)$$은 정확히 고정된 유일한 자연수로 존재한다.[5] 그 값이 무엇인지 증명하는게 ZF 공리계에서 불가능하다는 뜻이다.[6]
즉 이 증명법에는 두 가지의 문제가 있는데 $$n$$이 5 이상일 때의 미친 개구리 함수의 정확한 값을 모르며, ZF 공리계에서 값을 알아내는 것이 불가능 할 수 있다는 것과, 그 값이 초월적으로 크다는 것이다. $${\rm FF}(17)$$이 인간의 인지 범위를 넘어서는 그레이엄 수 보다 훨씬 크다는 것 부터 답이 없다. $$n$$이 작을 때의 함수값을 ZF 공리계에서 구하는 게 가능하다면, 컴퓨터로 반례를 찾아내는 방식으로 수학 문제를 풀 때 필요한 연산의 수를 무한에서 유한으로 끌어 내렸다는 의미는 있다.[7]
5. 외부 링크
[4] 2016년에 나온 논문에서는 7910 상태 튜링 머신이었으나 2020년 기준으로 7910 상태 -> 1919 상태 -> 748 상태로 최적화되었다.[5] $$n$$개 상태 튜링 머신 중 무한히 동작하지 않는 튜링 머신만 모아놓으면 그 중 가장 오래 동작하는 튜링 머신이 있다는 건 당연하기 때문이다. 정수로 이루어진 유한 집합은 최대값을 가진다는 것에서 유도된다.[6] 그래서 만약 ZF 공리계보다 더 강력한 공리계를 도입해 $${\rm FF}(748)$$의 값을 증명할 수 있다면 그것을 통해 ZF 공리계의 무모순성을 증명하는 것이 이론적으로는 가능하다... (하지만 그 강력한 공리계를 증명할 수 없다.) 물론 $${\rm FF}(748)$$이 초월적으로 크기에 우주멸망까지 컴퓨터를 돌려도 실제 증명 결과는 나오지 않을 것이다.[7] 사실 이 증명법으로 수학 난제를 증명하는 데에는 바쁜 비버 함수나 미친 개구리 함수의 정확한 함수값이 아닌 '''상한값'''만을 알아도 충분하다. 정확한 함수값을 알 때보다 더 많은 연산을 해야하는 것이 문제이며 현재로서는 일정 이상의 n에 대해서는 하한값만이 주어져 있다는 것이 문제이지만 말이다. 물론 현실적으로는 n이 6 이상만 되어도 실용적인 증명법으로는 사용할 수 없을 만큼 값이 크다.