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