スーダン関数

スーダン関数（スーダンかんすう、、）とは、計算理論において再帰的でありながら原始再帰的でない関数の一例である。この関数はドイツの数学者ダフィット・ヒルベルトの教鞭を受けていた学生であったによって1927年発表された。オリジナルの関数は順序数上の関数として定義されているが、自然数上で定義されたバージョンが1981年にネル・ディマ (Nelu Dima) によって定義され、クリスティアン・カルデによって「再帰関数だが原始再帰関数でない最初の例」として紹介された1927年の論文の主定理においてスーダンが主張したことは、「順序数は原始再帰的な手続きのみで作ることができない」ということ（）であり、原始再帰的手続きの限界を示したという意味でスーダンの例は確かにアッカーマン以前に提示されたものである。。

定義
以後  （変数は全て0を含む自然数）とする。

値の表

+ F0(x, y) の値 yx 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

+ F1(x, y) の値 yx 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

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

+ F2(x, y) の値 yx 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   F1(74, 76) ≈ 5.74  F1(185, 187) ≈ 3.67  F1(440, 442) ≈ 5.02 

 脚注 

参考文献

外部リンク
 OEIS: A260003, A260004

Category:算術
Category:巨大数
Category:特殊関数
Category:計算理論
Category:数学に関する記事