第二再帰定理との比較
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「第二再帰定理との比較」の解説
第二再帰定理と比較すると、第一再帰定理は狭い前提条件を満たす場合に限りより強い帰結を与える。ロジャース[1967]では第一再帰定理を弱再帰定理(英: weak recursion theorem)、第二再帰定理を強再帰定理(英: strong recursion theorem)と表現している。 ひとつの相違は、第一再帰定理は最小不動点を与えるものであるが、第二再帰定理は最小不動点に限らないということである。いまひとつの相違は、第一再帰定理は再帰方程式を帰納作用素に書き換えられる再帰方程式系に対してのみ適用できるが、第二再帰定理は任意の全域帰納的関数に適用できるということである。この制限はクリーネの不動点定理の連続写像という制限と類似している。
※この「第二再帰定理との比較」の解説は、「クリーネの再帰定理」の解説の一部です。
「第二再帰定理との比較」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- 第二再帰定理との比較のページへのリンク