수단 함수

1. 개요

수단 함수는 다음과 같이 재귀적으로 정의되는 함수이다. 이 함수는 F0, F1, F2, F3과 같이 여러 단계로 구성되며, 각 단계별로 다른 값을 가진다. 특히 F1 함수는 2^y · (x + 2) − y − 2로 표현되며, F2, F3 함수는 복잡한 형태로 정의되어 일반적인 수학적 표기법으로 닫힌 형태를 나타내기 어렵다.

2. 정의

수단 함수(Sudan function)는 다음과 같이 정의된다.

:$\backslash begin\{array\}\{lll\}$
F_0 (x, y) & = x+y \\
F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\
F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\
\end{array}

이는 재귀 함수이다.

2.1. 재귀적 정의

$\backslash begin\{array\}\{lll\}$
F_0 (x, y) & = x+y \\
F_{n+1} (x, 0) & = x & \text{if } n \ge 0 \\
F_{n+1} (x, y+1) & = F_n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1) & \text{if } n\ge 0 \\
\end{array}

마지막 방정식은 다음과 같이 동등하게 쓸 수 있다.

$\backslash begin\{array\}\{lll\}$
F_{n+1} (x, y+1) & = F_n(F_{n+1} (x, y), F_0(F_{n+1}(x, y), y + 1) \\
\end{array}.

2.2. 동등한 표현

마지막 방정식은 다음과 같이 동등하게 쓸 수 있다.

:$\backslash begin\{array\}\{lll\}$
F_{n+1} (x, y+1) & = F_n(F_{n+1} (x, y), F_0(F_{n+1}(x, y), y + 1) \\
\end{array}.

3. 값 표

수단 함수는 레벨에 따라 값이 급격하게 커지기 때문에, 각 레벨별로 표를 제시하여 값을 나타낸다. F₂부터는 일반적인 수학 표기 체계 내에서는 닫힌 표현이 불가능하다.

3.1. F₀의 값

F₀(x, y) = x + y

3.2. F₁의 값

F₁(x, y) = 2^y · (x + 2) - y - 2 의 값은 다음과 같다.

3.3. F₂의 값

3.4. F₃의 값

4. 한국 수학계의 연구

현재 한국 수학계에서 수단 함수에 대한 연구는 활발하게 이루어지고 있지 않다. 다만, 구트슈타인 함수와 같이 재귀적 정의를 가지면서도 비계산적인 성질을 보이는 함수에 대한 연구는 일부 진행되고 있다.