「スーダン関数」の版間の差分

}}）とは、[[計算理論]]において[[μ再帰関数|再帰的]]でありながら[[原始再帰関数|原始再帰的]]でない[[関数 (数学)|関数]]の一例である。この関数は[[ドイツ]]の[[数学者]][[ダフィット・ヒルベルト]]の教鞭を受けていた学生であった[[ルーマニア人]]{{ill2|ガブリエル・スーダン|en|Gabriel Sudan}}によって1927年発表された<ref>{{Cite journal|last=SUDAN|first=G.|date=1927|title=SUR LE NOMBRE TRANSFINI ω ω|url=https://www.jstor.org/stable/43769875|journal=Bulletin mathématique de la Société Roumaine des Sciences|volume=30|issue=1|pages=11–30|issn=1220-3858}}</ref>。オリジナルの関数は順序数上の関数として定義されているが、自然数上で定義されたバージョンが1981年にディマによって定義され、カルデによって「再帰関数だが原始再帰関数でない最初の例」として紹介された<ref>{{Cite journal|date=1979-11-01|title=The first example of a recursive function which is not primitive recursive|url=https://www.sciencedirect.com/science/article/pii/0315086079900247|journal=Historia Mathematica|volume=6|issue=4|pages=380–384|language=en|doi=10.1016/0315-0860(79)90024-7|issn=0315-0860}}</ref><ref>{{Cite book|title=Theories of computational complexity|url=https://www.worldcat.org/oclc/316565370|publisher=North-Holland|date=1988|location=Amsterdam|isbn=978-0-444-70356-9|oclc=316565370|first=Cristian|last=Calude}}</ref><ref group="注">1927年の論文の主定理においてスーダンが主張したことは、「順序数{{Math|ω^ω}}は原始再帰的な手続きのみで作ることができない」ということ（{{Cite web|url=http://www.math.mi.i.nagoya-u.ac.jp/~kihara/pdf/teach/fom2019spring.pdf|title=2019年度 数理情報学基礎論概論2・講義ノート|accessdate=2021-03-23|author=木原貴行|pages=20-22}}）であり、原始再帰的手続きの限界を示したという意味でスーダンの例は確かにアッカーマン以前に提示されたものである。</ref>。