μ再歸函數
μ-recursive function。歸納的函數 (recursive function)
原始再歸函數 (primitive recursion function) 定數函數 (constant function)$ \N\to\{0\}は原始再歸函數である 後者函數 (successor function)$ S:\N\to\N,n\mapsto n+1は原始再歸函數である 射影函數 (projection function)$ P^n_i:\N^n\to\N,(x_1,\dots,x_i,\dots,x_n)\mapsto x_iは原始再歸函數である 合成 (composition。置換 (substitution))。$ f:\N^m\to\Nと$ g_1,\dots,g_n:\N^n\to\Nが原始再歸函數ならば、$ f(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n)):\N^n\to\Nも原始再歸函數である 原始再歸 (primitive recursion)。$ f:\N^n\to\Nと$ g:\N^{n+2}\to\Nが原始再歸函數ならば、以下の通り再歸的に定義される函數$ h:\N^{n+1}\to\Nも原始再歸函數である $ h(x_1,\dots,x_n,0):=f(x_1,\dots,x_n)
$ h(x_1,\dots,x_n,y+1):=g(x_1,\dots,x_n,y,h(x_1,\dots,x_1,y))
$ f:\N^{n+1}\to\Nが原始再歸函數であり、$ \forall x_1,\dots,x_n\exist y(f(x_1,\dots,x_n,y)=0)であるならば、$ \mu y(f(x_1,\dots,x_n,y)=0):\N^n\to\Nはμ再歸函數である μ作用素
$ \exist y_{\in\N}~\varphi(y)である時に、$ \mu y~\varphi(y):=\min\{y|\varphi(y)\}
$ A(m,n):=\begin{cases}n+1 & m=0 \\ A(m-1,1) & n=0 \\ A(m-1,A(m,n-1)) & その他\end{cases}
Ackermann 數
$ \alpha(n)は、$ A(m-1,m-1)<n\le A(m,m)を滿たす$ m
Union-Find
はい、Ackermann 函數$ A(m,n)を自然數から實數/複素數へ拡張する試みは複數存在します。ただし、階乘のやうに「自然で廣く受け入れられた唯一の擴張 (=Γ 函數)」があるわけではなく、極めて多義的で、未だ標準的な“Ackermann のΓ函數”のやうなものは確立してゐません。 以下に既存の研究・アプローチを整理します。
■ 1. そもそも「アッカーマン函数の連續化」は難しい
アッカーマン函数は
各変数ごとに段階的な離散遷移
超高速な成長
非正則(非解析)的な振る舞ひ
を持ち、テイラー展開や差分方程式からのアナロジーが壊れやすい為、
自然な連續化を定める“正則化 (regularization)”が困難です。
■ 2. それでも提案されてゐる方法はある
(1) ハイパー演算列の正則化(ウォッシャーマンの一般化)
● Ackermann は
$ A(m,n)=H_m(n+3)-3
でハイパー演算 H_m の形に書けます。
したがって
• ハイパー演算 $ H_m の「指数 m」の連續化」
• 引数 n の連續化
が出来れば、A(m,n) の連續化も出来ます。
これに対して Wolfram (Mathematica) や Walker, Knuth らの研究で
連續冪乘 (continuous tetration)
連續 pentation, hexation… の定義
Carleman 行列による analytic continuation
正則化されたハイパー演算列
などが提案されてゐます。
これを用ゐれば
$ A(z,w)=H_z(w+3)-3
の形で 複素数 $ z,w を許す拡張が(定義すれば)形式上可能です。
ただし、
指数の連續化(tetration)すら未だ完全に標準形が無い
ため、A の連續化も多数の非同値な定義があり定まってゐません。
(2) 差分方程式の正則化による試み
アッカーマン函数は
$ \begin{aligned} A(0,n)&=n+1,\\ A(m+1,0)&=A(m,1),\\ A(m+1,n+1)&=A(m, A(m+1,n)). \end{aligned}
を満たしますが、これを「偏差分方程式」として連續化しようとする研究があります。
具体的には、
• Peter Walker (1994-) の Ackermann 連續化の議論
• Ecalle の解析的連續化(resurgent functions)理論を応用したもの
などが報告されています。
しかし、
連續化すると解析的構造がほとんど存在しない(branch が大量に生じる)
ため、一般に実数域・複素数域でよい性質を持つ拡張はほぼ不可能とされます。
(3) Carleman 行列による「関数反復の解析的連續」
関数反復 $ f^{(n)}(x) を
• 自然数反復
→ 実反復
→ 複素反復
へと一般化する研究があり、
これによりアッカーマン函数の下位段(例:指数/tetration)は実・複素拡張があります。
アッカーマンも
$ A(m,n) = f_m^{\,n}(1)
のように 関数反復の入れ子として書けるため、
理論的には反復の解析的連續化を代入する試みが可能です。
しかし、
Carleman 行列は巨大(無限次元)
収束解析が極めて難しい
多様な branch に依存
するため、既存文献でも Ackermann の実/複素正則化はほぼ扱はれてゐません。
■ 3. “実数アッカーマン函数”として提案された具体的な定義例
完全ではないが文献に見られる例:
● 例:ハイパー演算列の正則化に基づくもの
$ A(x,y) = \exp_x(y+3)-3
ここで $ \exp_x は「連續化されたハイパー演算の x 番目」。
ただし、
tetration の branch choice
超指数化の定義
によって値が大きく変はるので、標準化されてゐない。
● 例:修正 Ackermann(高階反復方程式の連續化)
特定の解析的 class 内で
$ \partial_n A(m,n)=A(m-1,A(m,n))
のような“疑似偏微分方程式”を構成する方法。
これは Ecalle の分野で議論されるが、一般に explicit ではない。
結論:理論的枠組みはあるが、使ひ物になる形の明示的実装はほぼ存在しない。
■ 4. 結論
まとめると:
● 研究自体は存在する
ハイパー演算列の連續化
関数反復の解析的連續化(Carleman 行列)
Ecalle の正則化理論
などを利用し、「形式的には」アッカーマン函数を実・複素に拡張することが可能。
● しかし、
広く認められた標準的定義は無い
解析的構造が壊れやすく、多くの branch が生まれる
実数域でも連續性・単調性すら確保できない場合が多い
● よって、
ガンマ函数のように“自然で一意に見える連續化”はアッカーマンには無い。
研究は点在するが統一理論には至ってゐない。