μ再帰関数（ミューさいきかんすう、）または帰納的関数（きのうてきかんすう）は、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。計算複雑性理論では、全再帰関数の集合をRと称する。μ再帰関数（または部分μ再帰関数）は、有限個の自然数の引数をとり、1つの自然数を返す部分関数である。μ再帰関数は初期関数を含み、合成や原始再帰やμ作用素において閉じている、部分関数の最小のクラスである。原始再帰関数もほぼ同じ定義となるが、全域関数という点が異なる。また、原始再帰関数は、3つの基本関数（定数関数、後者関数、射影関数）と2つの作用素（合成と原始再帰）で定義されるが、μ再帰関数にはさらにμ作用素が登場する。これはアッカーマン関数のように原始再帰関数でない全域再帰関数を定義するためである。μ再帰関数においてμ作用素は計算を終了させる。μ作用素は無制限探索演算子として働き、（全域関数の定義から）無制限ではあるが何らかの手段（帰納的定義など）で最終的に数を生成し計算を終わらせるのである。しかし、無制限μ作用素自身が部分的な場合（つまり、ある数について数を返せないことがある場合）、それを使って定義された関数も部分関数となり、一部の数については値が定義されない。この場合、無制限という性質上、μ作用素は永遠に探索を続け、計算を終了して数を返すことがない。アルゴリズムによっては、"u" という記号で 「決定不能（undecided）」を表し、計算を終了させるとする場合もある（例えば、Kleene (1952) pp. 328ff）。換言すれば、部分μ再帰関数は部分μ作用素を使うため、全域的でない可能性がある。全域μ再帰関数（total μ-recursive functions）は部分μ再帰関数の部分集合である。最初の3つの関数を「初期関数（initial functions）」または「基本関数（basic functions)」と呼ぶ。以下の定義は Kleene (1952) p. 219 に基づいている。その他の記号体系については「記号体系」の節を参照されたい。部分μ再帰関数同士を比較する演算子として formula_37（strong equality）がある。部分関数 formula_20 と formula_39 について、が成り立つのは、任意の引数の組み合わせについて、両関数の定義が存在して値が同じであるか、さもなくばどちらも未定義である場合だけである。ここである疑問が生じる。ここで説明されている計算のアルゴリズムは停止しないのか、である。ここでは「計算不能」な関数を扱っているのだろうか。計算可能かどうかはどうやって決定されるのか。クリーネは以下のように記している。まず、以下のような「効率的に決定可能な述語」について考える。クリーネは次のように提案している。「命題 R(x,0), R(x,1), R(x,2), ... を順に調べていき、真であるものを探す。我々が満足するまで…そこで、我々の採用しているアルゴリズムが「決定可能」かどうかをどうやって判断すればよいだろうか。「停止判定」アルゴリズムを使って停止するかどうかを調べられるだろうか。そのような判定が不可能であるという証明は非常に複雑である。重要な点は、クリーネが全ての全域再帰関数をゲーデル数によって数え上げ、カントールの対角線論法を使って、それ以上の再帰関数が定義可能であることを示したことである。結論から言えば、μ再帰関数の停止判定はμ再帰関数の体系では不可能であり、これはチャーチ＝チューリングのテーゼを受け入れた場合、チューリングマシンの停止問題と同じであることが判っている。クリーネは以下の最終定理で、「チューリングマシンによる計算可能関数」と「部分μ再帰関数」が等価であることを示した。クリーネはこれを証明するために、5つの原始再帰関数の作用素とμ作用素をチューリングマシンでエミュレートできることを示し、逆にチューリングマシンの動作を数値化することでその動作をμ再帰関数で表現できることを示した。クリーネの正規形定理（Normal form theorem）とは、原始再帰関数 formula_41 と formula_42 について、"k" 個の自由変数を持つμ再帰関数 formula_43 があり、以下を満足する "e" が存在する。ここで、"e" は関数 "f" のインデックスまたはゲーデル数である。つまり、任意のμ再帰関数は原始再帰関数に1回だけμ作用素を適用することで定義される。ミンスキー（1967）は、ここで定義された U が基本的に万能チューリングマシンと等価であると述べた。

出典:wikipedia