1 개요
ふぃっしゅ数
Fish number
일본 2ch에서 큰 수 만들기 배틀의 결과로 탄생한 큰 수. 대략 2002년 무렵에 탄생했으며, 이 수를 만든 사람은 휫슛슈(ふぃっしゅっしゅ)라는 아이디를 쓰는 2채널러. 유명한 큰 수인 그레이엄 수를 소개하는 과정에서 그레이엄 수보다 큰 수를 만들어보자는 취지에서 "가장 커다란 수를 제시하는 녀석이 우승"이라는 스레가 생겼고, 그 과정에서 휫슛슈라는 사람이 정의한 것. 애초에 그레이엄 수 스레에서 촉발된 것이기 때문에 일종의 그레이엄 수에 대한 오마주로서 특정한 자연수와 함수에서 얻어지는 변환을 63회 반복한 수로 정의되어 있다. 일본 인터넷 세계에서는 나름 그레이엄 수보다 큰 일본의 피쉬 수로 지명도가 있으나, 거대함 이외의 수학적인 의미는 없으며, 설명도 이해하기 어려운 편. 사실 단순히 크기만 놓고 따지면 이것보다 훨씬 큰 수도 많다.
2 정의
피쉬 수는 또한 여러 버전이 있는데 대표적인 F1(피쉬 수 버전1)의 정의는 다음과 같다.[1]
1. 자연수-함수쌍에서 자연수-함수쌍으로의 사상 [math]S[/math]([math]S[/math]변환)를 아래와 같이 정의한다.[math]S : [m, f(x)] \to [g(m), g(x)][/math]
단 [math]g(x)[/math]는 아래와 같이 정의된다.
[math]B(0, n) = f(n)[/math]
[math]B(m+1, 0) = B(m, 1)[/math]
[math]B(m+1, n+1) = B(m, B(m+1, n))[/math]
[math]g(x) = B(x, x)[/math]
1. 자연수-함수-[math]S[/math]변환쌍에서 자연수-함수-[math]S[/math]변환쌍으로의 사상 [math]SS[/math]를 아래와 같이 정의한다.
[math]SS : [m, f(x), S] \to [n, g(x), S2][/math]
단 [math]S2[/math]와 [math]n, g(x)[/math]는 순서대로 아래와 같이 정의된다.
[math]S2 = S^{f(m)}[/math]
[math]S2 : [m, f(x)] \to [n, g(x)][/math]
1. [math][3, x+1, S][/math]에 [math]SS[/math] 변환을 63번 반복하여 얻은 자연수를 피쉬 수([math]F_1[/math]), 함수를 피쉬 함수([math]F_1(x)[/math])라 한다.
이 이외에도 6가지 버전이 더 존재한다.
3 접근
다음은 피쉬 수의 계산 과정을 그나마 이해하기 쉽도록 풀어 쓴 것이다. 더 쉽게 서술하실 수 있으신 분이 수정 바람.
3.1 함수 B(m, n)
위 정의의 [math]B(m, n)[/math]을 조금 풀어 쓰면 다음과 같다.
- [math]B(0, n) = f(n)[/math]
- [math]B(m, 0) = B(m-1, 1)[/math]
- [math]B(m, n) = B(m-1, B(m-1,\ ...\ B(m-1, 1)\ ...\ ))[/math] (n+1번 중첩)
예를 들어 [math]f(x)=x+1[/math]일 때 [math]B(2, 2)[/math]를 전개하면 다음과 같다.
[math]B(2, 2)[/math]
[math]=B(1, B(1, B(1, 1)))[/math]
[math]=B(1, B(1, B(0, B(0, 1))))[/math]
[math]=B(1, B(1, B(0, 2)))[/math]
[math]=B(1, B(1, 3))[/math]
[math]=B(1, B(0, B(0, B(0, B(0, 1)))))[/math]
[math]=...[/math]
[math]=7[/math]
위와 같이 [math]f(x)=x+1[/math]인 특수한 경우를 아커만 함수(Ackermann function)라고 하고, [math]Ack(m, n)[/math]과 같이 표기한다.
계산 과정이 복잡하다 보니 계산해서 특정한 값이 정말 나오기는 하는 건지 의심스러울 수 있는데, 이는 수학적 귀납법으로 다음과 같이 증명할 수 있다.
- [math]m=0[/math]이면 [math]B(0, n)[/math]은 ([math]n[/math]의 값에 상관없이) [math]f(n)[/math]의 값을 갖는다.
- [math]B(x, n)=B(x-1, B(x-1,\ ...\ B(x-1, 1)\ ...\ ))[/math]이므로 [math]m=x-1[/math]일 때 함숫값을 갖는다면 [math]m=x[/math]일 때도 함숫값을 갖는다.
이 함수는 [math]m[/math], [math]n[/math]의 값에 따라 그 결과가 기하급수적이라는 말로는 부족할 정도로 커지며, 특히 [math]m[/math]이 커질 때 그런 경향을 보인다. 예를 들어 [math]Ack(2, 4)[/math]는 11이지만, [math]Ack(4, 2)[/math]는 19729자리 수가 나온다.
3.2 S변환
[math]S[/math]변환은 다음과 같이 표현할 수 있다.
- 자연수와 함수의 쌍 [math][m, f(x)][/math]를 준비한다.
- 주어진 함수 [math]f(x)[/math]로 [math]g(x)=B(x, x)[/math]를 정의한다.
- 정의한 함수 [math]g(x)[/math]로 [math]g(m)[/math]을 계산한다.
- 위에서 계산하고 정의한 자연수와 함수의 쌍 [math][g(m), g(x)][/math]가 변환 결과이다.
시험 삼아 [math][3, x+1][/math]에 [math]S[/math]변환을 두 번 반복해 보자.
[math][g(3), g(x)][/math] = [math][Ack(3, 3), Ack(x, x)][/math]인데, [math]Ack(m, n) = 2 \uparrow^{m-2} (n+3)-3[/math]임이 알려져 있으므로(#) 변환 결과는 [math][2^6 - 3, Ack(x, x)][/math] = [math][61, Ack(x, x)][/math]이 된다.
이를 한 번 더 변환하면 [math][61, Ack(x, x)][/math] = [math][g(61), g(x)][/math] = [math][B(61, 61), B(x, x)][/math]가 된다. 여기서 [math]B(m, n)[/math]이 어떤 함수인지 짐작해 보기 위해 [math]B(2, 4)[/math]를 전개해 보자.
[math]B(2, 4)[/math]
[math]=B(1, B(1, B(1, B(1, B(1, 1)))))[/math]
[math]=...[/math]
[math]=B(1, B(1, B(1, B(1, 61))))[/math]
[math]=B(1, B(1, B(1, B(0, B(0, B(0, ... B(0, 1) ... ))))))[/math] ([math]B(0, n)[/math]이 62회 중첩)
[math]=B(1, B(1, B(1, g^{62}(1))))[/math] ([math]B(0, n)=g(n)[/math]이므로)
[math]=B(1, B(1, B(1, g^{61}(3))))[/math]
[math]=B(1, B(1, B(1, g^{60}(61))))[/math]
[math]=...[/math]
이 시점에서 이미 정상적인 계산이 불가능해진다. [math]Ack(4, 2)[/math]도 이미 19729자리 수가 나오는 마당에 [math]g(61)=Ack(61, 61)[/math]은... 게다가 이건 계산이 끝날 시점도 아니고, 계산 초반이다. 덤으로, 원래 계산하려던 것이 [math]B(2, 4)[/math]가 아니라 [math]B(61, 61)[/math]이었음을 생각해 보자.
여담으로, 위에서 전개한 [math]B(2, 4)[/math]의 값을 그나마 짧고 알아보기 쉽게 표현하자면 [math]g^{g^{g^{g^{62}(1)+1}(1)+1}(1)+1}(1)[/math]이 된다. ???
3.3 SS변환
[math]SS[/math]변환을 간단히 표현하면 다음과 같다.
- 자연수, 함수, 변환의 쌍 [math][m, f(x), S][/math]를 준비한다.
- 새로운 변환 [math]S2[/math]를 '변환 [math]S[/math]를 [math]f(m)[/math]번 반복하는 것'으로 정의한다.
- 주어진 자연수와 함수의 쌍 [math][m, f(x)][/math]에 방금 정의한 변환 [math]S2[/math]를 가해서 새로운 쌍 [math][n, g(x)][/math]를 얻는다.
- 위에서 계산하고 정의한 자연수, 함수, 변환의 쌍 [math][n, g(x), S2][/math]가 변환 결과이다.
피쉬 수는 자연수-함수-[math]S[/math]변환쌍인 [math][3, x+1, S][/math]에 [math]SS[/math]변환을 63번 가해서 나온 자연수로, 피쉬 함수는 같은 과정을 거쳐서 나온 함수로 정의된다.
[math][3, x+1, S][/math]에 [math]SS[/math]변환을 가해 보자. [math]f(3)=4[/math]이므로 새로 정의할 [math]S2[/math]변환은 [math]S[/math]변환을 4번 반복하는 것으로 나타낼 수 있다. 하지만 [math][3, x+1][/math]에 S변환 2번부터 이미 답이 없다는 것을 생각하면... 게다가 1회 변환부터 답이 없는 [math]SS[/math]변환을 무려 63번이나 반복해야 피쉬 수가 나온다. 생각하는 것을 그만두었다
4 여담
만든 이의 설명에 따르면 이미 2회 변환에서 그레이엄 수보다 큰 결과값이 나온다. ㄷㄷ
만든 이가 온라인상에 거대수론이라는 논문 형태로 정리해 놓았다.