수단 함수

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

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

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

정의

${\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}}$

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

${\displaystyle {\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}}}$.

값 표

F₀의 값

F₀(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

F₁의 값

F₁(x, y) = 2^y · (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

F₂의 값

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)

F₃의 값

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

외부 링크

• Rosetta Code. “Sudan function”.
• OEIS: A260003, A260004