0646righ1113 ◆OPKWA8uhcY
2017/01/18(水) 20:36:37.46ID:ZtV8agPEそうでなければ走り続ける関数とします。
このとき、以下の関数Hは存在しません。
・Af(xs)の実行は停止する ⇒ H(Af,xs)はTrueを出力する。
・Af(xs)の実行は停止しない ⇒ H(Af,xs)はFalseを出力する。
Hが存在すると仮定して、
M(B(fix B))を、H(M,B(fix B))=TrueならM(B(fix B))自身は停止せず(無限リストを吐く)、
H(M,B(fix B))=Falseなら[1]を出力してM(B(fix B))を停止するプログラムとする。
・M(M(fix M))が停止したとすると、Mの定義よりH(M,M(fix M))=False。
Hの定義より H(M,M(fix M))=FalseとなるのはM(M(fix M))が停止しないときのみなので、矛盾。
・M(M(fix M))が停止しないとすると、Mの定義よりH(M,M(fix M))=True。
Hの定義より、H(M,M(fix M))=TrueとなるのはM(M(fix M))が停止するときのみなので、矛盾。
よってHは存在しない。⇒コラッツ遷移を上から押さえる関数を決定するプログラムは存在しない。
いかがでしょうか。