Automata的一些觀念(2)

1.
 Turing  thesis: 當代電腦的計算能力等價於 Turing machine 
a.所有電腦能做到的,TM也可以做到
b.沒有人可證明不存在一個演算法是Turing machine做不到的
c.沒有人能證明現代電腦能比Turing machine還強

2.
A nondeterministic pushdown automaton, or NPDA, M
is specified by a sixtuple M = (Q,Σ,Γ,δ,s,F), where

• Q is a finite set of states;
• Σ is an input alphabet;
• Λ is a pushdown alphabet, ⊥ is in Γ;
• δ ⊆ Q × Σ × Γ × Q × Γ ∗ is a finite transition relation;

• F ⊆ Q is a set of final states.

3.
deteministic pushdown automata:
是較嚴格的Npda
1.δ (q,a,b) 最多只會有一個element
2.δ (q,Λ ,b) 不為空集合的話,δ (q,c ,b) 必為空集合,任何c屬於Σ

4.
standard Turing Machime

1.TM has a tape unbounded in both directions, allowing any number of left and right moves.
2.TM is detetministic in the sence that δ  defines at most 1 move for each configuration.
3.No special input file.Inital time the tape has content.
3.No special output device.When halt,the content of tape can be viewed as output.