スーダン関数

ウィキペディア

スーダン関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/19 02:28 UTC 版)

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

定義

以後 ${\displaystyle x,y,n\in \mathbb {N} _{0}}$ この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。