Μ再帰関数
μ再帰関数(または部分μ再帰関数)は、有限個の自然数の引数をとり、1つの自然数を返す部分関数である。μ再帰関数は初期関数を含み、合成や原始再帰やμ作用素において閉じている、部分関数の最小のクラスである。
原始再帰関数も同じような形式で定義されるが、全域関数という点が異なる。また、原始再帰関数は、3つの基本関数(定数関数、後者関数、射影関数)と2つの作用素(合成と原始再帰)で定義されるが、μ再帰関数にはさらにμ作用素が登場する。これはアッカーマン関数のように原始再帰関数でない全域再帰関数を定義するためである。μ再帰関数においてμ作用素は計算を終了させる。μ作用素は無制限探索演算子として働き、(全域関数の定義から)無制限ではあるが何らかの手段(帰納的定義など)で最終的に数を生成し計算を終わらせるのである。
しかし、無制限μ作用素自身が部分的な場合(つまり、ある数について数を返せないことがある場合)、それを使って定義された関数も部分関数となり、一部の数については値が定義されない。この場合、無制限という性質上、μ作用素は永遠に探索を続け、計算を終了して数を返すことがない。アルゴリズムによっては、"u" という記号で 「決定不能(undecided)」を表し、計算を終了させるとする場合もある(例えば、Kleene (1952) pp. 328ff)。換言すれば、部分μ再帰関数は部分μ作用素を使うため、全域的でない可能性がある。全域μ再帰関数(total μ-recursive functions)は部分μ再帰関数の部分集合である。
μ再帰関数(ミューさいきかんすう、英: μ-recursive function)または帰納的関数(きのうてきかんすう)とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数(原始帰納的関数)と密接な関連があり、その帰納的定義(後述)は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。
また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。
計算複雑性理論では、全再帰関数の集合をRと称する。