圖靈機 (Turing Machine)

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

Finite state automata :

M = (K, Σ, δ, S, F)
K : set of state
Σ: finite set of input symbol
s : s in K, initial state
δ: (K*Σt*Σs)->K * Σ*
F : F in K, final state set

regular expression :

A->wB, A->w

Pumping lemma for regular expression

if z in L and |z| >= n, we may write z = uvw
1. |v| >= 1
2. |uv| <= n
3. i uviw in L

Theorem : L(Finite state automata) = L(Regular expression)

Push down automata

M = (K, Σi, Σs, δ, s, F)
K : set of state
Σi: finite set of input symbol
Σs: finite set of stack symbol
s : s in K, initial state
δ: (K * Σi * Σs)-> K * Σ*
F : F in K, final state set

Context free grammar :

G = (V,T,P,S)
A->α, αin (V∪T)*

Pumping lemma for context free grammar :

if z in L and |z| >= n, we may write z = uvwxy
1. |vx| >= 1
2. |vwx| <= n
3. i uviwxiy in L

Turing Machine (TM)

M = (K,Σ,δ,S)
K : set of state
Σ: finite set of symbol
s : s in K, initial state
δ: (K*Σ)->(K∪{h,”yes”,”no”})* Σ*(←,—,→)

example : A TM that decide plaindromes

  plaindromes (迴文) : 正讀倒讀都一樣的 word。
  K   Σ    δ
  s    0 (q0 ,> ,→)  s :start,q0:上次讀的bit為0.
  s    1 (q1 ,> ,→)             q1: 上次讀的bit為1.
  s    > (s  ,> ,→)  寫上一個 >
  s    _ (yes,_ ,—) 
  q0   0 (q0 ,0 ,→)  q0:移到最後一個bit “_”
  q0   1 (q0 ,1 ,→)  
  q0   _ (q0’,_ ,←)
  q1   0 (q1 ,0 ,←) q1:移到最後一個bit “_”
  q1   1 (q1 ,1 ,←)
  q1   _ (q1’,_ ,←)
  q0’  0    (q  ,_ ,←) q0’: 看看是否為0
  q0’  1    (no ,1 ,—)
  q0’  >    (yes,_ ,→)
  q1’  0    (no ,1 ,—) q1’: 看看是否為1
  q1’  1    (q  ,_ ,←)
  q1’  >    (yes,> ,→)
  q    0    (q  ,0 ,←)  q  : 回到開頭,繼續檢查下一個。
  q    1    (q  ,1 ,←)
  q    >    (s  ,> ,→)

Unrestricted Grammar

α->β

Theorem : L(Turing Machine) = L(Unrestricted Grammar)
L(Turing Machine) = L(First Order Logic)

Church-Turing Thesis :

“Computable function” can be identified with the class of partial recursive functions.

Closure Property :

A class of languages is closed under a particular operatio.

Example :

  intersection     : L1∩L2
  union : L1∪L2
  concatenation : L1L2
  Kleene operator    : L1*
Chapter 2 : Turing Machine
Theorem : Single tape TM can simulate TM in O(f(n)^2)

Linear speedup :
  if L in TIME(f(n)) then ε>0,L in TIME(εf(n)+n+2)

Nondeterministic Turing Machine
  M = (K,Σ,Δ,S)
  K : set of state
  Σ: finite set of symbol
  s : s in K, initial state
  Δ: (K*Σ)*[(K∪{h,”yes”,”no”})* Σ*{←,—,→}] 
  (it’s a relation)

  if path, M(x;path) = “yes” then M accept x
                                           else M reject x
  if x,path M(x;path) & |path|<(f(|x|) then M decide x in f(|x|)

Complexity of Nondeterministic Turing Machine
  M accept x => T(M(x)) = 所有 “yes” path中最短的 path長度。
  M reject x => T(M(x)) = 整棵tree的大小。

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

圖靈-邱奇假說

Turing Machine Powerful Thesis (Church)

1. There is no formalism to model any mechanical calculus that is more powerful than Turing Machine and equivalent formalisms.
2. Any algorithm can be coded in term of a Turing Machine.

Chapter 2 : Turing Machine
Theorem : Single tape TM can simulate TM in O(f(n)^2)

Linear speedup :
if L in TIME(f(n)) then ε>0,L in TIME(εf(n)+n+2)

Nondeterministic Turing Machine

M = (K,Σ,Δ,S)
K : set of state
Σ: finite set of symbol
s : s in K, initial state
Δ: (K*Σ)*[(K∪{h,”yes”,”no”})* Σ*{←,—,→}]
(it’s a relation)

if path, M(x;path) = “yes” then M accept x
else M reject x
if x,path M(x;path) & |path|<(f(|x|) then M decide x in f(|x|)

Complexity of Nondeterministic Turing Machine

M accept x => T(M(x)) = 所有 “yes” path中最短的 path長度。
M reject x => T(M(x)) = 整棵tree的大小。

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

Facebook

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