수단 함수

수단 함수(Sudan function)는 계산 이론에서 재귀적이지만 원시 재귀적이지는 않은 함수의 예이다. 이는 더 잘 알려진 아커만 함수의 경우에도 마찬가지이다.

1926년에 다비트 힐베르트는 모든 계산 가능한 함수가 원시 재귀 함수라고 추측했다. 이는 그의 제자인 가브리엘 수단과 빌헬름 아커만에 의해 빠르게 연속해서 출판된 다양한 기능을 사용하여 반박되었다. 수단은 1927년, 아커만은 1928년에 발표되었다.

수단 함수는 원시 재귀가 아닌 재귀 함수의 가장 먼저 발표된 예이다.

 정의 

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

 값 표 

 F0의 값 
F0(x, y) = x + y
 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의 값 
F1(x, y) = 2y · (x + 2) − y − 2
 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의 값 
 y \ x  0  1  2  3  4  5  6  7 0 0  1  2  3  4  5  6  7 x 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 2x+1 · (x + 2) − x − 3≈ 10lg 2·(x+1) + lg(x+2) 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 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) 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 longer expression, starts with 222x+1 an, ≈ 101010lg 2·(x+1) + lg(x+2) 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)   ≈ 3,5 · 1026514839   much longer expression, starts with 2222x+1 an,  ≈ 10101010lg 2·(x+1) + lg(x+2)

 F3의 값 
 y \ x  0  1  2  3  4 0 0  1  2  3  4 x 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 No closed expressions possible within the framework of normal mathematical notation 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)   No closed expressions possible within the framework of normal mathematical notation

 외부 링크 

 OEIS: A260003, A260004

분류:산술
분류:특수 함수
분류:계산 이론