μ再帰関数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/10/22 08:07 UTC 版)
μ再帰関数(ミューさいきかんすう、英: μ-recursive function)または帰納的関数(きのうてきかんすう)とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数(原始帰納的関数)と密接な関連があり、その帰納的定義(後述)は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。
- 1 μ再帰関数とは
- 2 μ再帰関数の概要
- 3 他の計算可能性モデルとの等価性
- 4 関連項目
μ再帰関数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/09 06:43 UTC 版)
複数の自然数を引数として1つの自然数を返す関数であり、原始再帰関数に基づいて構築され、それにμ再帰を施したもの。
※この「μ再帰関数」の解説は、「計算理論」の解説の一部です。
「μ再帰関数」を含む「計算理論」の記事については、「計算理論」の概要を参照ください。
- μ再帰関数のページへのリンク