Wikipedia

スーダン関数

スーダン関数（スーダンかんすう、英: Sudan function、独: Sudanfunktion ）とは、計算理論において再帰的でありながら原始再帰的でない関数の一例である。この関数はドイツの数学者ダフィット・ヒルベルトの教鞭を受けていた学生であったガブリエル・スーダン（英語版）によって1927年発表された[1]。オリジナルの関数は順序数上の関数として定義されているが、自然数上で定義されたバージョンが1981年にネル・ディマ (Nelu Dima) によって定義され、クリスティアン・カルデ (Cristian Calude) によって「再帰関数だが原始再帰関数でない最初の例」として紹介された[2][3][注 1]。

定義 編集

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

 

値の表 編集

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

F2(x, y) の値
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. ^ 1927年の論文の主定理においてスーダンが主張したことは、「順序数ωωは原始再帰的な手続きのみで作ることができない」ということ（木原貴行. “2019年度 数理情報学基礎論概論2・講義ノート”. pp. 20-22. 2021年3月23日閲覧。）であり、原始再帰的手続きの限界を示したという意味でスーダンの例は確かにアッカーマン以前に提示されたものである。

参考文献 編集

  1. ^ SUDAN, G. (1927). “SUR LE NOMBRE TRANSFINI ω ω”. Bulletin mathématique de la Société Roumaine des Sciences 30 (1): 11–30. ISSN 1220-3858. https://www.jstor.org/stable/43769875. 
  2. ^ “The first example of a recursive function which is not primitive recursive” (英語). Historia Mathematica 6 (4): 380–384. (1979-11-01). doi:10.1016/0315-0860(79)90024-7. ISSN 0315-0860. https://www.sciencedirect.com/science/article/pii/0315086079900247. 
  3. ^ Calude, Cristian (1988). Theories of computational complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. OCLC 316565370. https://www.worldcat.org/oclc/316565370 

外部リンク 編集

 

この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

「https://ja.wikipedia.org/w/index.php?title=スーダン関数&oldid=97486809」から取得