スーダン関数
(sudan function から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/19 02:28 UTC 版)
スーダン関数（スーダンかんすう、英: Sudan function、独: Sudanfunktion ）とは、計算理論において再帰的でありながら原始再帰的でない関数の一例である。この関数はドイツの数学者ダフィット・ヒルベルトの教鞭を受けていた学生であったガブリエル・スーダンによって1927年発表された[1]。オリジナルの関数は順序数上の関数として定義されているが、自然数上で定義されたバージョンが1981年にネル・ディマ (Nelu Dima) によって定義され、クリスティアン・カルデ (Cristian Calude) によって「再帰関数だが原始再帰関数でない最初の例」として紹介された[2][3][注 1]。
- ^ 1927年の論文の主定理においてスーダンが主張したことは、「順序数ωωは原始再帰的な手続きのみで作ることができない」ということ（木原貴行. “2019年度 数理情報学基礎論概論2・講義ノート”. pp. 20-22. 2021年3月23日閲覧。）であり、原始再帰的手続きの限界を示したという意味でスーダンの例は確かにアッカーマン以前に提示されたものである。
- ^ SUDAN, G. (1927). “SUR LE NOMBRE TRANSFINI ω ω”. Bulletin mathématique de la Société Roumaine des Sciences 30 (1): 11–30. ISSN 1220-3858.
- ^ “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.
- ^ Calude, Cristian (1988). Theories of computational complexity. Amsterdam: North-Holland. ISBN 978-0-444-70356-9. OCLC 316565370
[続きの解説]
「スーダン関数」の続きの解説一覧
- 1 スーダン関数とは
- 2 スーダン関数の概要
- 3 外部リンク
- スーダン関数のページへのリンク
