피쉬 수

덤프버전 :

분류

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)]변환)를 아래와 같이 정의한다.

<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가지 버전이 더 존재한다.


2.2. 해설[편집]

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


2.2.1. 함수 B(m, n)[편집]

위 정의의 [math(B(m, n))]을 조금 풀어 쓰면 다음과 같다.
  • [math(B(0, n) = f(n))]
  • [math(B(m, 0) = B(m-1, 1))]
  • [math(B(m, n) = B(m-1, B(m-1,\ ...\ B(m-1, 1)\ ...\ )))] (n+1번 중첩)

예를 들어 [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=0)]이면 [math(B(0, n))]은 ([math(n)]의 값에 상관없이) [math(f(n))]의 값을 갖는다.
  • [math(B(x, n)=B(x-1, B(x-1,\ ...\ B(x-1, 1)\ ...\ )))]이므로 [math(m=x-1)]일 때 함숫값을 갖는다면 [math(m=x)]일 때도 함숫값을 갖는다.

이 함수는 [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([m, f(x)])]를 준비한다.
  • 주어진 함수 [math(f(x))]로 [math(g(x)=B(x, x))]를 정의한다.
  • 정의한 함수 [math(g(x))]로 [math(g(m))]을 계산한다.
  • 위에서 계산하고 정의한 자연수와 함수의 쌍 [math([g(m), g(x)])]가 변환 결과이다.

시험 삼아 [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)]변환을 간단히 표현하면 다음과 같다.
  • 자연수, 함수, S변환의 쌍 [math([m, f(x), S])]를 준비한다.
  • 새로운 변환 [math(S2)]를 '변환 [math(S)]를 [math(f(m))]번 반복하는 것'으로 정의한다.
  • 주어진 자연수와 함수의 쌍 [math([m, f(x)])]에 방금 정의한 변환 [math(S2)]를 가해서 새로운 쌍 [math([n, g(x)])]를 얻는다.
  • 위에서 계산하고 정의한 자연수, 함수, S변환의 쌍 [math([n, g(x), S2])]가 변환 결과이다.
피쉬 수는 자연수-함수-[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번째 피쉬 수(Fish number 1): 이 문서의 정의~SS변환까지에서 다루고 있는 피쉬 수. Fast-growing hierarchy로 나타내면 [math(f_{\omega^2+1}(63))] 정도의 값이 나온다.
  • 2번째 피쉬 수(Fish number 2): 위의 1번째 피쉬 수와 마찬가지로 2002년경에 나온 피쉬 수. 1번째 피쉬 수와 정의는 매우 비슷하나(초반은 아예 같다!), 약간의 차이가 있어 1번째 것보다는 값이 약간(?) 더 크게 나온다. Fast-growing hierarchy로 나타내면 [math(f_{\omega^3}(63))] 정도의 값이 나온다.
  • 3번째 피쉬 수(Fish number 3): 2002년경에 나온 피쉬 수.Fast-growing hierarchy로 나타내면 피쉬 수 3은 대략 [math(f_{\omega^{\omega+1}63+1}(63))] 정도의 값이 나온다.
  • 4번째 피쉬 수(Fish number 4): 2002년경에 나온 피쉬 수. 2번째로 큰 피쉬 수이며, 튜링 머신을 사용하여 바쁜 비버 함수를 응용했기 때문에 크기가 이전보다 비약적으로 상승하여 fgh로 근사가 불가능하다.[5] 게다가 기존 바쁜 비버 함수가 아닌, 고차 바쁜 비버 함수가 사용된다.[6] 7번째 피쉬 수처럼 너무 커서 정확한 값을 계산하기는 어렵다. 바쁜 비버 성장률로 나타내자면 피쉬 수 4는 [math({\rm BB}_{ω^{ω+1}63+1}(n))] 정도 나온다.
  • 5번째 피쉬 수(Fish number 5): 2003년경에 나온 피쉬 수.Fast-growing hierarchy로 나타내면 [math(f_{\epsilon_0+1}(63))] 정도의 값이 나온다.
  • 6번째 피쉬 수(Fish number 6): 2007년경에 나온 피쉬 수. Fast-growing hierarchy로 나타내면 [math(f_{\zeta_0+1}(63))] 정도의 값이 나온다
  • 7번째 피쉬 수(Fish number 7): 2013년에 라요 수를 응용하여 나온 가장 큰 피쉬 수. 고차 라요 함수가 사용됨에 따라, 피쉬 수 7이 피쉬 수 4보다 훨씬 크다. fgh의 최대치인 비가산 서수는 ZFC 공리계로도 도저히 감당 불가능하고, 피쉬 수 4도 모자라 무한 시간 튜링 머신의 값도 먼지로 만들어버리고도 한참 남을 정도로 큰데, 이 서수를 이용해도 피쉬 수 7을 근사할 수 없기 때문에 당연히 fgh를 쓰든 뭘 쓰든 정확한 크기는 알 수 없다.[7] 그래도 어쨌든 크기가 계산 불가능한 만큼 크기 때문에 라요 수처럼 크기가 큰 수들을 아득히 초월한다는 것을 알 수 있다. 성장률도 당연히 기존 라요 수, 이 라요 수를 라요수 이상으로 재귀한 값들도 먼지로 만들고 남을 정도로 뛰어넘는다.[8] 라요 성장률로 나타내자면 피쉬 수 7은 [math(Rayo_{\zeta_0}^{63}(n))] 정도 나온다.
  • Co피쉬 수 7: 현재 ZFC공리계로는 정의 불가능한 피쉬 수 7을[9] ZFC공리계로 정의 가능하게 만든 버전이다. 하지만 이 피쉬 수 7도 워낙 커서 현재까지 정의된 가산서수를 이용한 fgh의 범위를 한참 능가하였다. 게다가 이마저도 크기 측정 오류로 인해서 피쉬 수 4보다 작다고 평가받았을 뿐이지 실제로는 그보다도 더 큰 것으로 밝혀졌다.[10]
참고로 피쉬 수들을 작은 수부터 나열하면, 1번째<2번째<3번째<5번째<6번째<<4번째<<<Co7번째<<<<7번째다. 참고로 볼드체는 계산 불가능한 함수이다.[11]

5. 여담[편집]

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

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


6. 관련 문서 및 사이트[편집]



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-12-24 16:19:17에 나무위키 피쉬 수 문서에서 가져왔습니다.

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

관련 문서