不可計算問題

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

Chapter 3 : Undecidability

Universal Turing Machine
U(M;x) : simulate TM M on input x
encode : M = (K,Σ,Δ,S)
K = {|Σ|+1, |Σ|+2,.., |Σ|+|K|} 
where 
s         = |Σ|+1
←         = |Σ|+|K|+1
—        = |Σ|+|K|+2
→        = |Σ|+|K|+3
yes    = |Σ|+|K|+4
no        = |Σ|+|K|+5
h        = |Σ|+|K|+6

tape 1: (input)           M ; x
tape 2: (configuration) (s, >, x) in initial state
                            (w, q, u) in middle state

Halting Problem H = {M;x : M(x)≠↗}
Theorem : H is not recursive
Proof :
  suppose TM Mh decide H
  Mh(M;x) = if M(x) ≠↗then “yes” else “no”
  D(M) = if Mh(M;M)=”yes” then ↗else “yes”
  D(D) = if Mh(D;D)=”yes” then ↗else “yes”

  if D(D) ≠↗
  => Mh(D;D) = “yes”  // by definition of Mh
  => D(D) = ↗ ><      // by program of D(M=D)

  if D(D) =↗ 
  => Mh(D;D) = “no”   // by definition of Mh
=> D(D) = “yes” ><  // by program of D(M=D)

Rice Theorem :
  if C≠NULL & C≠Σ* then is L(M) in C is undecidable.
  (not recursive)
Proof :
  suppose there is a L in C accepted by machine ML

  Mx(y) : if Mh(x) = “yes” then ML(y)
             else ↗

  if M(x) = ↗ then L(Mx) = NULL
  if M(x) ≠ ↗then L(Mx) = L(ML) = L

  Claim : L(Mx) in C iff x in H
  <= if x in H then Mh(x) = “yes” 
      so Mx(y) = ML(y)
         L(Mx) = L (in C)
=> if Mh(x)= ↗   // Mh accept H,so Mh(x)≠no and Mh(x)≠halt,
   then Mx(x)=↗       // Mh(x) ≠ “yes” means Mh(x)=↗
   so L(Mx) = NULL

停止問題

Halting Problem is an undecidable problem

h(x, y) = if fy(x) <> undefine then 1 else 0 -—(1)

suppose that h is computable then we may define function g such that

g(x) = if h(x, x) = 0 then 1 else undefine

g is also computable , ie g = fp for some integer p then

if fp(p) = g(p) = undefine = h(p, p) = if fp(p) <> undefine then 1 else 0,

will return 0, contradiction.

if fp(p) = g(p) <> undefine = h(p, p) = if fp(p) <> undefine then 1 else 0,
will return 1, contradiction

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License