수단 함수

**수단 함수**(Sudan function)는 계산 이론에서 재귀적이지만 원시 재귀적이지는 않은 함수의 예이다. 이는 더 잘 알려진 아커만 함수의 경우에도 마찬가지이다. 1926년에 다비트 힐베르트는 모든 계산 가능한 함수가 원시 재귀 함수라고 추측했다. 이는 그의 제자인 가브리엘 수단과 빌헬름 아커만에 의해 빠르게 연속해서 출판된 다양한 기능을 사용하여 반박되었다. 수단은 1927년, 아커만은 1928년에 발표되었다. 수단 함수는 원시 재귀가 아닌 재귀 함수의 가장 먼저 발표된 예이다.
# 정의
:\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} 마지막 방정식은 다음과 같이 동등하게 쓸 수 있다. :\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}.
# 값 표

## F0의 값
*F*0(*x*, *y*) = x + y {| class="wikitable" |- ! *y* \ *x* !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 |- ! 0 | 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 |- ! 1 | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 |- ! 2 | 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 |- ! 3 | 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 |- ! 4 | 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 |- ! 5 | 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 |- ! 6 | 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 |- ! 7 | 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 |- ! 8 | 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 |- ! 9 | 9 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 |- ! 10 | 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 || 19 || 20 |- |}
## F1의 값
*F*1(*x*, *y*) = 2y · (x + 2) − y − 2 {| class="wikitable" |- ! *y* \ *x* !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 |- ! 0 | 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 |- ! 1 | 1 || 3 || 5 || 7 || 9 || 11 || 13 || 15 || 17 || 19 || 21 |- ! 2 | 4 || 8 || 12 || 16 || 20 || 24 || 28 || 32 || 36 || 40 || 44 |- ! 3 | 11 || 19 || 27 || 35 || 43 || 51 || 59 || 67 || 75 || 83 || 91 |- ! 4 | 26 || 42 || 58 || 74 || 90 || 106 || 122 || 138 || 154 || 170 || 186 |- ! 5 | 57 || 89 || 121 || 153 || 185 || 217 || 249 || 281 || 313 || 345 || 377 |- ! 6 | 120 || 184 || 248 || 312 || 376 || 440 || 504 || 568 || 632 || 696 || 760 |- ! 7 | 247 || 375 || 503 || 631 || 759 || 887 || 1015 || 1143 || 1271 || 1399 || 1527 |- ! 8 | 502 || 758 || 1014 || 1270 || 1526 || 1782 || 2038 || 2294 || 2550 || 2806 || 3062 |- ! 9 | 1013 || 1525 || 2037 || 2549 || 3061 || 3573 || 4085 || 4597 || 5109 || 5621 || 6133 |- ! 10 | 2036 || 3060 || 4084 || 5108 || 6132 || 7156 || 8180 || 9204 || 10228 || 11252 || 12276 |- |}
## F2의 값
{| class="wikitable" |- ! *y* \ *x* !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 |- ! rowspan="2" | 0 | 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 |- | colspan="8" align="center" | *x* |- ! rowspan="4" | 1 | F1 (F2(0, 0),
F2(0, 0)+1) | F1 (F2(1, 0),
F2(1, 0)+1) | F1 (F2(2, 0),
F2(2, 0)+1) | F1 (F2(3, 0),
F2(3, 0)+1) | F1 (F2(4, 0),
F2(4, 0)+1) | F1 (F2(5, 0),
F2(5, 0)+1) | F1 (F2(6, 0),
F2(6, 0)+1) | F1 (F2(7, 0),
F2(7, 0)+1) |- | F1(0, 1) | F1(1, 2) | F1(2, 3) | F1(3, 4) | F1(4, 5) | F1(5, 6) | F1(6, 7) | F1(7, 8) |- | 1 || 8 || 27 || 74 || 185 || 440 || 1015 || 2294 |- | colspan="8" align="center" | *2x+1 · (x + 2) − x − 3*
≈ 10lg 2·(x+1) + lg(x+2) |- ! rowspan="4" | 2 | F1 (F2(0, 1),
F2(0, 1)+2) | F1 (F2(1, 1),
F2(1, 1)+2) | F1 (F2(2, 1),
F2(2, 1)+2) | F1 (F2(3, 1),
F2(3, 1)+2) | F1 (F2(4, 1),
F2(4, 1)+2) | F1 (F2(5, 1),
F2(5, 1)+2) | F1 (F2(6, 1),
F2(6, 1)+2) | F1 (F2(7, 1),
F2(7, 1)+2) |- | F1(1, 3) | F1(8, 10) | F1(27, 29) | F1(74, 76) | F1(185, 187) | F1(440, 442) | F1(1015, 1017) | F1(2294, 2296) |- | 19 | 10228 | 15569256417 | ≈ 5,742397643 · 1024 | ≈ 3,668181327 · 1058 | ≈ 5,019729940 · 10135 | ≈ 1,428323374 · 10309 | ≈ 3,356154368 · 10694 |- | colspan="8" align="center" | 22x+1·(x+2) − x − 1 · (2x+1·(x+2) − x − 1) − (2x+1·(x+2) − x + 1)
≈ 10lg 2 · (2x+1·(x+2) − x − 1) + lg(2x+1·(x+2) − x − 1) ≈ 10lg 2 · 2x+1·(x+2) + lg(2x+1·(x+2)) ≈ 10lg 2 · (2x+1·(x+2)) = 1010lg lg 2 + lg 2·(x+1) + lg(x+2) ≈ 1010lg 2·(x+1) + lg(x+2) |- ! rowspan="5" | 3 | F1 (F2(0, 2),
F2(0, 2)+3) | F1 (F2(1, 2),
F2(1, 2)+3) | F1 (F2(2, 2),
F2(2, 2)+3) | F1 (F2(3, 2),
F2(3, 2)+3) | F1 (F2(4, 2),
F2(4, 2)+3) | F1 (F2(5, 2),
F2(5, 2)+3) | F1 (F2(6, 2),
F2(6, 2)+3) | F1 (F2(7, 2),
F2(7, 2)+3) |- | F1(F1(1,3),
F1(1,3)+3) | F1(F1(8,10),
F1(8,10)+3) | F1(F1(27,29),
F1(27,29)+3) | F1(F1(74,76),
F1(74,76)+3) | F1(F1(185,187),
F1(185,187)+3) | F1(F1(440,442),
F1(440,442)+3) | F1(F1(1015,1017),
F1(1015,1017)+3) | F1(F1(2294,2297),
F1(2294,2297)+3) |- | F1(19, 22) | F1(10228, 10231) | F1(15569256417,
15569256420) | F1(≈6·1024, ≈6·1024) | F1(≈4·1058, ≈4·1058) | F1(≈5·10135, ≈5·10135) | F1(≈10309, ≈10309) | F1(≈3·10694, ≈3·10694) |- | 88080360 | ≈ 7,04 · 103083 | ≈ 7,82 · 104686813201 | ≈ 101,72·1024 | ≈ 101,10·1058 | ≈ 101,51·10135 | ≈ 104,30·10308 | ≈ 101,01·10694 |- | colspan="8" align="center" | longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2) |- ! rowspan="5" | 4 | F1 (F2(0, 3),
F2(0, 3)+4) | F1 (F2(1, 3),
F2(1, 3)+4) | F1 (F2(2, 3),
F2(2, 3)+4) | F1 (F2(3, 3),
F2(3, 3)+4) | F1 (F2(4, 3),
F2(4, 3)+4) | F1 (F2(5, 3),
F2(5, 3)+4) | F1 (F2(6, 3),
F2(6, 3)+4) | F1 (F2(7, 3),
F2(7, 3)+4) |- | F1 (F1(19, 22),
F1(19, 22)+4) | F1 (F1(10228,
10231),
F1(10228,
10231)+4) | F1 (F1(15569256417,
15569256420),
F1(15569256417,
15569256420)+4) | F1 (F1(≈5,74·1024, ≈5,74·1024),
F1(≈5,74·1024, ≈5,74·1024)) | F1 (F1(≈3,67·1058, ≈3,67·1058),
F1(≈3,67·1058, ≈3,67·1058)) | F1 (F1(≈5,02·10135, ≈5,02·10135),
F1(≈5,02·10135, ≈5,02·10135)) | F1 (F1(≈1,43·10309, ≈1,43·10309),
F1(≈1,43·10309, ≈1,43·10309)) | F1 (F1(≈3,36·10694, ≈3,36·10694),
F1(≈3,36·10694, ≈3,36·10694)) |- | F1(88080360,
88080364) || F1(10230·210231−10233,
10230·210231−10229) || colspan="6" | |- | ≈ 3,5 · 1026514839 || colspan="7" | |- | colspan="8" align="center" | much longer expression, starts with 2222x+1 an, ≈ 10101010lg 2·(x+1) + lg(x+2) |}
## F3의 값
{| class="wikitable" |- ! *y* \ *x* !! 0 !! 1 !! 2 !! 3 !! 4 |- ! rowspan="2" | 0 | 0 || 1 || 2 || 3 || 4 |- | colspan="5" align="center" | *x* |- ! rowspan="4" | 1 | F2 (F3(0, 0),
F3(0, 0)+1) | F2 (F3(1, 0),
F3(1, 0)+1) | F2 (F3(2, 0),
F3(2, 0)+1) | F2 (F3(3, 0),
F3(3, 0)+1) | F2 (F3(4, 0),
F3(4, 0)+1) |- | F2(0, 1) | F2(1, 2) | F2(2, 3) | F2(3, 4) | F2(4, 5) |- | 1 | 10228 | ≈ 7,82 · 104686813201 | | |- | colspan="5" align="center" | No closed expressions possible within the framework of normal mathematical notation |- ! rowspan="4" | 2 | F3 (F4(0, 1),
F4(0, 1)+2) | F3 (F4(1, 1),
F4(1, 1)+2) | F3 (F4(2, 1),
F4(2, 1)+2) | F3 (F4(3, 1),
F4(3, 1)+2) | F3 (F4(4, 1),
F4(4, 1)+2) |- | F3 (1, 3) | F3 (10228, 10230) | F3 (≈104686813201,
≈104686813201) | | |- | | |- | colspan="5" align="center" | No closed expressions possible within the framework of normal mathematical notation |}