スーダン機能

計算理論において、スーダン関数は再帰的ではあるが原始再帰的ではない関数の例である。これは、よりよく知られているアッカーマン関数にも当てはまる。

1926年、デイヴィッド・ヒルベルトは、すべての計算可能な関数は原始再帰的であると推測した。これは、彼の教え子であるガブリエル・スーダンとヴィルヘルム・アッカーマンによって、相次いで発表された異なる関数を用いて反駁された。スーダンは1927年に^{[ 1 ]} 、アッカーマンは1928年に^{[ 2 ]発表した。}

スーダン関数は、原始再帰ではない再帰関数の最も初期の公開例である。^{[ 3 ]}

${\displaystyle {\begin{array}{lll}F_{0}(x,y)&=x+y\\F_{n+1}(x,0)&=x&{\text{if }}n\geq 0\\F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1)&{\text{if }}n\geq 0\\\end{array}}}$

最後の式は、以下のように等価的に記述できます。

${\displaystyle {\begin{array}{lll}F_{n+1}(x,y+1)&=F_{n}(F_{n+1}(x,y),F_{0}(F_{n+1}(x,y),y+1))\\\end{array}}}$[ ^{4 ]​}

これらの方程式は、項書き換えシステム（TRS）の規則として使用できます。

一般化された関数${\displaystyle F(x,y,n){\stackrel {\mathrm {def} }{=}}F_{n}(x,y)}$書き換えルールにつながる

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&F(x,y,0)&\rightarrow x+y\\{\text{(r2)}}&F(x,0,n+1)&\rightarrow x\\{\text{(r3)}}&F(x,y+1,n+1)&\rightarrow F(F(x,y,n+1),F(F(x,y,n+1),y+1,0),n)\\\end{array}}}$

各還元ステップにおいて、F の最も右の最も内側の出現箇所は、規則 (r1) ～ (r3) のいずれかを適用して書き換えられます。

Calude (1988) は、次のような例を挙げています。${\displaystyle F(2,2,1)\rightarrow _{*}12}$[ ^{5 ]​}

還元シーケンスは^{[ 6 ]}

• ロゼッタコード（2024年7月23日）。「スーダン機能」。

• OEIS: A260003、A260004