停止性問題の証明のメモ

関数HALT(a,x)の計算は不可能。

前提

• 関数HALT(a,x)
  • コードaとそれに対する入力xを引数に取る
  • 有限時間で停止する場合はHALT(a,x)→1
  • それ以外0

証明

• 証明は背理法で行う
• HALTを計算するチューリングマシン M_HALTを定義する

• M_HALTが矛盾した計算不可能関数UCを計算するチューリングマシンM_UCであることを示す

• チューリングマシンM_UCについて

  • 入力aについてM_HALT(a,a)を計算する。
    • M_HALTが0のとき(停止しない)、M_UC=1
    • M_HALTが1のとき(停止する)、aが表現する万能チューリングマシンMでM(a)を計算する
      • M(a)=0のときM_HALTは1を出力する
        • それいがい:0を出力する

• 上記のM_UC(a)は以下の場合のみUC(a)を有限ステップで計算が可能である

  • M_HALT(a,x)が有限ステップで計算できるとき
    • UCは計算できないので矛盾(HALTも計算できない)

ちょっと結論が怪しい？描きなおす予定