不動点定理の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/03 01:23 UTC 版)
「クリーネの再帰定理」の記事における「不動点定理の証明」の解説
この証明では以下で定義される計算可能関数 h {\displaystyle h} を利用する。 自然数 x {\displaystyle x} が与えられたとき、関数 h {\displaystyle h} は次のような計算を行う部分計算可能関数の指標を出力する： 入力 y {\displaystyle y} が与えられると、 まず φ x ( x ) {\displaystyle \varphi _{x}(x)} の計算を試行する。この計算が出力 e {\displaystyle e} を返したならば、そのときに限って φ e ( y ) {\displaystyle \varphi _{e}(y)} を計算してその値を返す。 任意の x {\displaystyle x} について、 φ x ( x ) {\displaystyle \varphi _{x}(x)} が停止するならば φ h ( x ) = φ φ x ( x ) {\displaystyle \varphi _{h(x)}=\varphi _{\varphi _{x}(x)}} であり、停止しないならば φ h ( x ) {\displaystyle \varphi _{h(x)}} は停止しない。これは φ h ( x ) ≃ φ φ x ( x ) {\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}} と書ける。関数 h {\displaystyle h} は部分計算可能関数 g ( x , y ) = φ φ x ( x ) ( y ) {\displaystyle g(x,y)=\varphi _{\varphi _{x}(x)}(y)} からSmn定理を用いて構成できる： 各 x {\displaystyle x} に対して、 h ( x ) {\displaystyle h(x)} はプログラム y ↦ g ( x , y ) {\displaystyle y\mapsto g(x,y)} の指標である。 証明を完成させる為に、 F {\displaystyle F} を任意の全域計算可能関数とする。また h {\displaystyle h} を上で構成した関数とする。いま e {\displaystyle e} を合成 F ∘ h {\displaystyle F\circ h} の指標とする。これは全域計算可能関数である。すると h {\displaystyle h} の定義より φ h ( e ) ≃ φ φ e ( e ) {\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}} が成り立つ。ところが e {\displaystyle e} は F ∘ h {\displaystyle F\circ h} の指標だったから、 φ e ( e ) = ( F ∘ h ) ( e ) {\displaystyle \varphi _{e}(e)=(F\circ h)(e)} であり、 φ φ e ( e ) ≃ φ F ( h ( e ) ) {\displaystyle \varphi _{\varphi _{e}(e)}\simeq \varphi _{F(h(e))}} 。 ≃ {\displaystyle \simeq } の推移性により、これは φ h ( e ) ≃ φ F ( h ( e ) ) {\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}} を意味する。すなわち n = h ( e ) {\displaystyle n=h(e)} について φ n ≃ φ F ( n ) {\displaystyle \varphi _{n}\simeq \varphi _{F(n)}} が成り立つ。
※この「不動点定理の証明」の解説は、「クリーネの再帰定理」の解説の一部です。
「不動点定理の証明」を含む「クリーネの再帰定理」の記事については、「クリーネの再帰定理」の概要を参照ください。
- 不動点定理の証明のページへのリンク
