スーダン関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

スーダン関数(スーダンかんすう、: Sudan function: Sudanfunktion )とは、計算理論において再帰でありながら原始再帰でない関数の一例である。その様な例としてアッカーマン関数が知られているが、スーダン関数はこの性質が知られる事となった最初の関数である。

この関数はドイツ数学者ダフィット・ヒルベルトの教鞭を受けていた学生であったルーマニア人ガブリエル・スーダン英語版に1927年発見及び発表された[1]

定義[編集]

以後 (変数は全て0を含む自然数)とする。

値の表[編集]

F0(xy) の値
y\x 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(xy) の値
y\x 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(xy) は F1(0, y) + 2y x と等しい。

F2(xy) の値
y\x 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 ×1010 F1(74, 76) ≈ 5.74 ×1024 F1(185, 187) ≈ 3.67 ×1058 F1(440, 442) ≈ 5.02 ×10135

脚注[編集]

  1. ^ Bull. Math. Soc. Roumaine Sci. 30 (1927), 11–30; Jbuch 53, 171

参考文献[編集]

  • Cristian Calude, Solomon Marcus英語版, Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Mathematica 6 (1979), no. 4, 380–384 doi:10.1016/0315-0860(79)90024-7