# 訊息

## 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,