不動点を持たない（fixed-point free）関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「不動点を持たない（fixed-point free）関数」の解説
関数 F {\displaystyle F} が任意の e {\displaystyle e} に対して φ e ≄ φ F ( e ) {\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}} を満たすときfixed point freeという。不動点定理によれば計算可能なfixed-point free関数は存在しない。しかし計算可能でないfixed-point free関数は幾つも存在する。アースラノフの完全性条件は、帰納的可算集合 A {\displaystyle A} に関する次の条件が同値であることを述べる： A {\displaystyle A} はチューリング次数 0 ′ {\displaystyle {\boldsymbol {0}}'} つまり停止性問題の次数を持つ。 Fixed-point free関数 f ≤ T A {\displaystyle f\leq _{T}A} が存在する。
※この「不動点を持たない（fixed-point free）関数」の解説は、「クリーネの再帰定理」の解説の一部です。
「不動点を持たない（fixed-point free）関数」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
ウィキペディア小見出し辞書の「不動点を持たない関数」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 不動点を持たない関数のページへのリンク
