再帰関数との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/20 10:14 UTC 版)
再帰関数は、例えばμ作用素（英語版）を使って定義できる。μ作用素は入力に対して、出力が返ってくることを保証しない。このような関数を部分関数 (Partial Function) と言い、始域のどのような入力に対しても出力が返ってくる関数を全域関数 (Total Function) と言う。 原始再帰関数は全て全域再帰的であるが、全域再帰関数が全て原始再帰的とは言えない。アッカーマン関数 A(m,n) は全域再帰関数でありながら原始再帰的でない有名な例である。アッカーマン関数を使って、原始再帰関数が全域再帰関数の部分集合であるとする見方もある。この場合、関数が原始再帰的であるとは、その関数がチューリングマシンで計算可能で、かつある m に対して A(m, n)以下のステップ数で必ず停止するものと定義される。
※この「再帰関数との関係」の解説は、「原始再帰関数」の解説の一部です。
「再帰関数との関係」を含む「原始再帰関数」の記事については、「原始再帰関数」の概要を参照ください。
ウィキペディア小見出し辞書の「再帰関数との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 再帰関数との関係のページへのリンク
