書籍、講義

Automata Theory: An Algorithmic Approach
An Introduction to Formal Languages and Automata
Introduction to the Theory of Computation
Introduction to Automata Theory, Languages, and Computation
Elements of Automata Theory
Automata and Computability

language

邏輯敘述改成語言。邏輯推論規則改成文法。

automaton

文法改成圖。語言改成路徑。

decidable / tractable

decidable：可決定的。存在一個演算法，可以算出特定敘述是真是假。
tractable：可牽引的。存在一個高速演算法，可以算出特定敘述是真是假。

halting problem

Turing是Church的學生。Turing模仿Church的思路，將不可證明改成了不可計算。

證明相當複雜，我沒有學會。知道結論就足夠了。請見停機問題、邱奇－圖靈論題。