피쉬 수

1 개요

ふぃっしゅ数
Fish number

일본 2ch에서 큰 수 만들기 배틀의 결과로 탄생한 큰 수. 대략 2002년 무렵에 탄생했으며, 이 수를 만든 사람은 휫슛슈(ふぃっしゅっしゅ)라는 아이디를 쓰는 2채널러. 유명한 큰 수인 그레이엄 수를 소개하는 과정에서 그레이엄 수보다 큰 수를 만들어보자는 취지에서 "가장 커다란 수를 제시하는 녀석이 우승"이라는 스레가 생겼고, 그 과정에서 휫슛슈라는 사람이 정의한 것. 애초에 그레이엄 수 스레에서 촉발된 것이기 때문에 일종의 그레이엄 수에 대한 오마주로서 특정한 자연수와 함수에서 얻어지는 변환을 63회 반복한 수로 정의되어 있다. 일본 인터넷 세계에서는 나름 그레이엄 수보다 큰 일본의 피쉬 수로 지명도가 있으나, 거대함 이외의 수학적인 의미는 없으며, 설명도 이해하기 어려운 편. 사실 단순히 크기만 놓고 따지면 이것보다 훨씬 큰 수도 많다.

2 정의

피쉬 수는 또한 여러 버전이 있는데 대표적인 F1(피쉬 수 버전1)의 정의는 다음과 같다.

1. 자연수-함수쌍에서 자연수-함수쌍으로의 사상 $$S$$ ( $$S$$ 변환)를 아래와 같이 정의한다.

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

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

3 접근

다음은 피쉬 수의 계산 과정을 그나마 이해하기 쉽도록 풀어 쓴 것이다. 더 쉽게 서술하실 수 있으신 분이 수정 바람.

3.1 함수 B(m, n)

위 정의의 $$B(m, n)$$ 을 조금 풀어 쓰면 다음과 같다.

• $$B(0, n) = f(n)$$
• $$B(m, 0) = B(m-1, 1)$$
• $$B(m, n) = B(m-1, B(m-1,\ ...\ B(m-1, 1)\ ...\ ))$$ (n+1번 중첩)

예를 들어 $$f(x)=x+1$$ 일 때 $$B(2, 2)$$ 를 전개하면 다음과 같다.
$$B(2, 2)$$
$$=B(1, B(1, B(1, 1)))$$
$$=B(1, B(1, B(0, B(0, 1))))$$
$$=B(1, B(1, B(0, 2)))$$
$$=B(1, B(1, 3))$$
$$=B(1, B(0, B(0, B(0, B(0, 1)))))$$
$$=...$$
$$=7$$

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

계산 과정이 복잡하다 보니 계산해서 특정한 값이 정말 나오기는 하는 건지 의심스러울 수 있는데, 이는 수학적 귀납법으로 다음과 같이 증명할 수 있다.

• $$m=0$$ 이면 $$B(0, n)$$ 은 ( $$n$$ 의 값에 상관없이) $$f(n)$$ 의 값을 갖는다.
• $$B(x, n)=B(x-1, B(x-1,\ ...\ B(x-1, 1)\ ...\ ))$$ 이므로 $$m=x-1$$ 일 때 함숫값을 갖는다면 $$m=x$$ 일 때도 함숫값을 갖는다.

이 함수는 $$m$$ , $$n$$ 의 값에 따라 그 결과가 기하급수적이라는 말로는 부족할 정도로 커지며, 특히 $$m$$ 이 커질 때 그런 경향을 보인다. 예를 들어 $$Ack(2, 4)$$ 는 11이지만, $$Ack(4, 2)$$ 는 19729자리 수가 나온다.

3.2 S변환

$$S$$ 변환은 다음과 같이 표현할 수 있다.

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

시험 삼아 $$[3, x+1]$$ 에 $$S$$ 변환을 두 번 반복해 보자.

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

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

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

이 시점에서 이미 정상적인 계산이 불가능해진다. $$Ack(4, 2)$$ 도 이미 19729자리 수가 나오는 마당에 $$g(61)=Ack(61, 61)$$ 은... 게다가 이건 계산이 끝날 시점도 아니고, 계산 초반이다. 덤으로, 원래 계산하려던 것이 $$B(2, 4)$$ 가 아니라 $$B(61, 61)$$ 이었음을 생각해 보자.

여담으로, 위에서 전개한 $$B(2, 4)$$ 의 값을 그나마 짧고 알아보기 쉽게 표현하자면 $$g^{g^{g^{g^{62}(1)+1}(1)+1}(1)+1}(1)$$ 이 된다. ???

3.3 SS변환

$$SS$$ 변환을 간단히 표현하면 다음과 같다.

• 자연수, 함수, 변환의 쌍 $$[m, f(x), S]$$ 를 준비한다.
• 새로운 변환 $$S2$$ 를 '변환 $$S$$ 를 $$f(m)$$ 번 반복하는 것'으로 정의한다.
• 주어진 자연수와 함수의 쌍 $$[m, f(x)]$$ 에 방금 정의한 변환 $$S2$$ 를 가해서 새로운 쌍 $$[n, g(x)]$$ 를 얻는다.
• 위에서 계산하고 정의한 자연수, 함수, 변환의 쌍 $$[n, g(x), S2]$$ 가 변환 결과이다.

피쉬 수는 자연수-함수- $$S$$ 변환쌍인 $$[3, x+1, S]$$ 에 $$SS$$ 변환을 63번 가해서 나온 자연수로, 피쉬 함수는 같은 과정을 거쳐서 나온 함수로 정의된다.

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

4 여담

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

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

5 관련 문서 및 사이트

• 그레이엄 수
• 큰 수
• Googology Wiki의 Fish numbers 문서, Fish number 1 문서