μ再帰関数

μ再帰関数（ミューさいきかんすう、英: μ-recursive function）または帰納的関数（きのうてきかんすう）とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。 計算複雑性理論では、全再帰関数の集合をRと称する。