mir.pe (일반/어두운 화면)
최근 수정 시각 : 2023-03-01 17:51:02

피쉬 수

1. 개요2. 피쉬 수 1
2.1. 정의2.2. 해설
2.2.1. 함수 B(m, n)2.2.2. S변환2.2.3. SS변환
2.3. 근사
3. 피쉬 수 2
3.1. 정의
4. 자매품5. 여담6. 관련 문서 및 사이트

1. 개요

ふぃっしゅ数 / Fish number[1]

일본 2ch에서 큰 수 만들기 배틀의 결과로 탄생한 큰 수. 대략 2002년 무렵에 탄생했으며, 이 수를 만든 사람은 휫슛슈(ふぃっしゅっしゅ)라는 아이디를 쓰는 2채널러.

유명한 큰 수인 그레이엄 수를 소개하는 과정에서 그레이엄 수보다 큰 수를 만들어보자는 취지에서 "가장 커다란 수를 제시하는 녀석이 우승"이라는 스레가 생겼고, 그 과정에서 휫슛슈라는 사람이 정의한 것. 그레이엄 수에 대한 오마주의 의미로[2], 특정한 자연수와 함수에서 얻어지는 변환을 63회 반복한 수로 정의되어 있다.

일본 인터넷 세계에서는 나름 그레이엄 수보다 큰 일본의 피쉬 수로 지명도가 있으나, 거대함 이외의 수학적인 의미는 없으며[3], 설명도 이해하기 어려운 편. 사실 단순히 크기만 놓고 따지면 TREE(3), BIGG, 바쁜 비버, 라요 수, 거대수 정원수 등과 등과 같이 이것보다 훨씬 큰 수도 많다.[4]

2. 피쉬 수 1

2.1. 정의

F1(피쉬 수 버전1)의 정의는 다음과 같다.[출처]
1. 자연수-함수쌍에서 자연수-함수쌍으로의 사상 [math(S)]([math(S)]변환)를 아래와 같이 정의한다.
S:[m,f(x)]→[g(m),g(x)]S : [m, f(x)] \to [g(m), g(x)]
단 g(x)g(x)는 아래와 같이 정의된다.
B(0,n)=f(n)B(0, n) = f(n)
B(m+1,0)=B(m,1)B(m+1, 0) = B(m, 1)
B(m+1,n+1)=B(m,B(m+1,n))B(m+1, n+1) = B(m, B(m+1, n))
g(x)=B(x,x)g(x) = B(x, x)
1. 자연수-함수-SS변환쌍에서 자연수-함수-SS변환쌍으로의 사상 SSSS를 아래와 같이 정의한다.
SS:[m,f(x),S]→[n,g(x),S2]SS : [m, f(x), S] \to [n, g(x), S2]
단 S2S2와 n,g(x)n, g(x)는 순서대로 아래와 같이 정의된다.
S2=Sf(m)S2 = S^{f(m)}
S2:[m,f(x)]→[n,g(x)]S2 : [m, f(x)] \to [n, g(x)]
1. [3,x+1,S][3, x+1, S]에 SSSS 변환을 63번 반복하여 얻은 자연수를 피쉬 수(F1F_1), 함수를 피쉬 함수(F1(x)F_1(x))라 한다.

이 이외에도 6가지 버전이 더 존재한다.

2.2. 해설

다음은 피쉬 수의 계산 과정을 그나마 이해하기 쉽도록 풀어 쓴 것이다.

2.2.1. 함수 B(m, n)

위 정의의 [math(B(m, n))]을 조금 풀어 쓰면 다음과 같다.
예를 들어 [math(f(x)=x+1)]일 때 [math(B(2, 2))]를 전개하면 다음과 같다.
[math(B(2, 2))]
[math(=B(1, B(1, B(1, 1))))]
[math(=B(1, B(1, B(0, B(0, 1)))))]
[math(=B(1, B(1, B(0, 2))))]
[math(=B(1, B(1, 3)))]
[math(=B(1, B(0, B(0, B(0, B(0, 1))))))]
[math(=...)]
[math(=7)]

위와 같이 [math(f(x)=x+1)]인 특수한 경우를 아커만 함수(Ackermann function)라고 하고, [math(Ack(m, n))]과 같이 표기한다.

계산 과정이 복잡하다 보니 계산해서 특정한 값이 정말 나오기는 하는 건지 의심스러울 수 있는데, 이는 수학적 귀납법으로 다음과 같이 증명할 수 있다.
이 함수는 [math(m)], [math(n)]의 값에 따라 그 결과가 기하급수적이라는 말로는 부족할 정도로 커지며, 특히 [math(m)]이 커질 때 그런 경향을 보인다. 예를 들어 [math(Ack(2, 4))]는 11이지만, [math(Ack(4, 2))]는 무려 19729자리 수가 나온다. [math(Ack(5, 2))]는 [math(10^{10^{100}})] [math( \uparrow \uparrow 10^{10^{100}})] 보다도 더 큰 수이다.

이 아커만 함수 B(n,n)는 fgh로 [math(f_\omega(n))]으로 근사할 수 있다.

2.2.2. S변환

[math(S)]변환은 다음과 같이 표현할 수 있다.
시험 삼아 [math([3, x+1])]에 [math(S)]변환을 두 번 반복해 보자.

[math([g(3), g(x)])] = [math([Ack(3, 3), Ack(x, x)])]인데, [math(Ack(m, n) = 2 \uparrow^{m-2} (n+3)-3)]임이 알려져 있으므로( #) 변환 결과는 [math([2^6 - 3, Ack(x, x)])] = [math([61, Ack(x, x)])]이 된다.

이를 한 번 더 변환하면 [math([61, Ack(x, x)])] = [math([g(61), g(x)])] = [math([B(61, 61), B(x, x)])]가 된다. 여기서 [math(B(m, n))]이 어떤 함수인지 짐작해 보기 위해 [math(B(2, 4))]를 전개해 보자.

[math(B(2, 4))]
[math(=B(1, B(1, B(1, B(1, B(1, 1))))))]
[math(=...)]
[math(=B(1, B(1, B(1, B(1, 61)))))]
[math(=B(1, B(1, B(1, B(0, B(0, B(0, ... B(0, 1) ... )))))))] ([math(B(0, n))]이 62회 중첩)
[math(=B(1, B(1, B(1, g^{62}(1)))))] ([math(B(0, n)=g(n))]이므로)
[math(=B(1, B(1, B(1, g^{61}(3)))))]
[math(=B(1, B(1, B(1, g^{60}(61)))))]
[math(=...)]

이 시점에서 이미 정상적인 계산이 불가능해진다. [math(Ack(4, 2))]도 이미 19729자리 수가 나오고, [math(Ack(5, 2))]는 구골플렉스↑↑구골플렉스를 넘어가는 마당에 [math(g(61)=Ack(61, 61))]은... 게다가 이건 계산이 끝날 시점도 아니고, 계산 초반이다. 그리고, 원래 계산하려던 것이 [math(B(2, 4))]가 아니라 [math(B(61, 61))]이었음을 생각해 보자.

여담으로, 위에서 전개한 [math(B(2, 4))]의 값을 그레이엄 함수로 그나마 짧고 알아보기 쉽게 표현하자면 [math(g^{g^{g^{g^{62}(1)+1}(1)+1}(1)+1}(1))]이 된다. 참고로 +1은 그거 맞다. 물론 저 함수에서는 1만 더해도 엄청나게 커진다.

2.2.3. SS변환

[math(SS)]변환을 간단히 표현하면 다음과 같다. 피쉬 수는 자연수-함수-[math(S)]변환쌍인 [math([3, x+1, S])]에 [math(SS)]변환을 63번 가해서 나온 자연수로, 피쉬 함수는 같은 과정을 거쳐서 나온 함수로 정의된다.

[math([3, x+1, S])]에 [math(SS)]변환을 가해 보자. [math(f(3)=4)]이므로 새로 정의할 [math(S2)]변환은 [math(S)]변환을 4번 반복하는 것으로 나타낼 수 있다. 하지만 [math([3, x+1])]에 S변환 2번부터 이미 답이 없다는 것을 생각하면 그냥 포기하는게 더 나은 수준. 게다가 1회 변환부터 답이 없는 [math(SS)]변환을 무려 63번이나 반복해야 피쉬 수가 나온다.

2.3. 근사

피쉬 수 1는 너무나 크기 때문에 따로 표기할 방법이 없어 얼마나 큰지 알 수 없을 것처럼 보인다. 하지만 Fast-growing hierarchy를 이용하면 피쉬 수 1의 크기를 비교적 정확히 측정할 수 있다.
먼저, [math(g(n)=B(n,n)=Ack(n,n)=2 \uparrow^{m-2} (n+3)-3)]이므로 [math(g(n)=2 \uparrow^{m-2} (n+3)-3)]이다. 그리고 S변환은 [math(S : [m, f(n)\ \!\!] \to [g(m), g(n)\ \!\!])]이므로 [math(Ack(n,n))]함수를 재귀하는 것과 동치라는 것도 알 수 있다. 따라서 [math(S2)]변환은 이의 반복이고, 다시 변환을 하는 [math(SS)]변환은 다시 이 과정을 반복하는 것으로 생각할 수 있다.
이제 그레이엄 함수 g(n)은 [math(g(n)=2 \uparrow^{m-2} (n+ 3)-3)\approx f_\omega (n))]으로 근사할 수 있으며, S변환의 반복과 S2변환의 반복을 적용하면 [math(f_{\omega^2}(n))]의 성장률을 가진다. 따라서 SS변환을 n번 반복하는 것은 [math(f_{\omega^2+1}(n))]이며,피쉬 수 1는 [math(f_{\omega^2+1}(63))]으로 근사가 가능하다. BEAF로는 [math(\{4, 64, 1, 1, 2\})]에 근사하게 된다.

3. 피쉬 수 2

3.1. 정의

피쉬 수 2의 정의는 다음과 같다.
앞서 정의했던 S변환을 다시 사용해서,
[math(S2=S^{f(m)})]
[math(S2:[m,f(x)\ \!\!] → [n,p(x)\ \!\!])]
[math(S2^x:[m,f(x)\ \!\!] → [q(x),g(x)\ \!\!])]
[math([3,x+1,S])]에 대해, [math(SS)]변환을 63번 반복해서 얻은 자연수를 피쉬 수 2([math(F_2)]), 함수를 피쉬 함수([math(F_2(x))])라 한다.

4. 자매품

이 수 자체로도 이미 상당히 큰데, 현재 시점에서는 자매품이 무려 7(+1)개나 있다. 다음 내용은 Googology Wiki(큰 수 위키)의 내용을 참고하여 작성하였다.
참고로 피쉬 수들을 작은 수부터 나열하면, 1번째<2번째<3번째<5번째<6번째<<4번째<<<Co7번째 <<<<7번째다. 참고로 볼드체는 계산 불가능한 함수이다.[12]

5. 여담

만든 이의 설명에 따르면 이미 2회 변환에서 그레이엄 수보다 큰 결과값이 나온다.

만든 이가 온라인상에 거대수론이라는 논문 형태로 정리해 놓았다.

6. 관련 문서 및 사이트

[1] Fish 맞다. [2] 그레이엄 수가 G(64)임을 상기하자. 비슷하게도 그레이엄 수 보다 더 작은 모우저도 63번 이상 재귀하면 그레이엄 수 보다 더 커진다. [3] 그레이엄 수가 의미 있는 이유는 단순히 크기 때문이 아니라 '수학적 증명에 사용되는 수' 가운데 가장 크기 때문임을 상기할 것. [4] 다만 피쉬수의 자매품들도 바쁜 비버등을 응용하여 계산이 불가능한 정도의 크기인 피쉬수도 있으며, 피쉬 수의 최종 크기인 피쉬 수 7은 거대수 정원수를 제외하면 따라올 수가 없다. [출처] 해당 페이지의 'Definition of Fish number version 1 (F1)' 문단 [6] 기본적으로 바쁜 비버 함수가 계산 불가능한 함수이기 때문에, 비가산 서수를 이용하지 않는 한 fgh로도 근사가 불가능하다. [7] 고차 바쁜 비버이기 때문에, 바쁜 비버 함수를 바쁜 비버 만큼 재귀하는 일반적인 방법으로는 피쉬 수 4의 성장률을 절대 따라가지 못한다. 재귀로 수를 늘리는 건 사실상 의미가 없다. 바쁜 비버를 바쁜 비버 이상만큼, 셀 수 없는 엄청난 수만큼 확장해야 된다. [8] 사실 라요 수만 해도 fgh의 비가산 서수로 감당하기는 불가능하다. [9] 이 피쉬 수를 만들려면 라요 수를 재귀가 아니라 라요 수 이상으로 계속해서 확장해야 된다. 재귀만 해서는 피쉬 수 7을 넘을 수 없다. 라요 수 원품을 확장한 2차 라요 함수는 바쁜 비버 함수랑 라요 수의 성장률을 비교하는 것은 물론, 1부터 1씩 더하는 것과 라요 수의 성장률을 비교하는 것보다도 훨씬 초월할 정도의 격이 다른 성장률을 가진다. 이 2차 라요 함수도 피쉬수 7에는 아직 시작에 불과하다. 게다가 성장률도 3차 4차 ...넘어갈 수록 이전 보다도 격이 다르게 아득히 빨라진다. 피쉬 수 6 자체의 값도 어마어마한 크기인데 피쉬 수 7은 그야말로 라요 수와는 비교조차 할 수 없는 큰 수인 것이다. [10] 이 수의 제작자는 피쉬 수 7의 원품인 라요 수도 ZFC 공리계에서 정의 가능하도록 설계하였다. [11] 제작자의 말에 따르면 Co피쉬 수 7은 ZFC 집합이론에서 공식화된 가장 강력한 수이다. 때문에 라요 수 바로 앞에 오는 어마어마하게 큰 수이며 무한 시간 튜링머신까지 모두 압도한다. [12] fgh의 계산 불가능한 함수도 라요 수부터는 한계에 부딪혔는데 7번째 피쉬 수는 라요 수보다도 비교도 안 되게 큰 탓에 애초에 크기를 비교하거나 짐작하는 것 자체가 완전히 무의미하다. 그런데 저 라요 수도 확장하면 피쉬 수 7 넘어가는데 피쉬 수 7은 확장해도 다음 수인 거대수 정원수는 커녕 U(1)보다도 한참 작다.

분류