スーダン関数

スーダン関数（スーダンかんすう、テンプレート:Lang-en-short、テンプレート:Lang-de-short）とは、計算理論において再帰的でありながら原始再帰的でない関数の一例である。この関数はドイツの数学者ダフィット・ヒルベルトの教鞭を受けていた学生であったテンプレート:Ill2によって1927年発表された。オリジナルの関数は順序数上の関数として定義されているが、自然数上で定義されたバージョンが1981年にネル・ディマ (Nelu Dima) によって定義され、クリスティアン・カルデテンプレート:Enlinkによって「再帰関数だが原始再帰関数でない最初の例」として紹介された。

定義

以後 $x,y,n\in {\mathbb{N}}_0$ （変数は全て0を含む自然数）とする。$$\begin{array}{cc}{F}_0(x,y)& =x+y,\\ F_{n+1}(x,0)& =x,\\ F_{n+1}(x,y+1)& =F_n(F_{n+1}(x,y),F_{n+1}(x,y)+y+1).\end{array}$$

値の表

F₀(x, y) の値

yテンプレート:Backslashx	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	6
2	2	3	4	5	6	7
3	3	4	5	6	7	8
4	4	5	6	7	8	9
5	5	6	7	8	9	10
6	6	7	8	9	10	11

F₁(x, y) の値

yテンプレート:Backslashx	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	3	5	7	9	11	13
2	4	8	12	16	20	24	28
3	11	19	27	35	43	51	59
4	26	42	58	74	90	106	122
5	57	89	121	153	185	217	249
6	120	184	248	312	376	440	504

一般に、F₁(x, y) は F₁(0, y) + 2^y x と等しい。

F₂(x, y) の値

yテンプレート:Backslashx	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	8	27	74	185	440
2	19	F1(8, 10) = 10228	F1(27, 29) ≈ 1.55 テンプレート:E	F1(74, 76) ≈ 5.74 テンプレート:E	F1(185, 187) ≈ 3.67 テンプレート:E	F1(440, 442) ≈ 5.02 テンプレート:E

外部リンク

• OEIS: A260003, A260004