運算理論

 「 "What are the fundamental capabilities and limitations of computers?" 「電腦（運算機械）嘅基本能力同極限係乜？」 」

1. 讀取讀取器下嗰格有乜符號；
2. 編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
3. 將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

概論

可運算性理論

```def g(): # 定義 g
if halts(g): # 如果 halt(g) 係真...
loop_forever() # 做永遠唔停嘅 loop
```

運算複雜性理論

• 時間複雜度（time complexity），指一段運算要用幾多時間解；
• 空間複雜度（space complexity），指一段運算要用幾多記憶體嚟解。

• `n` 係 10，用嘅時間係 10 秒；
• `n` 係 10,000，用嘅時間係 40,000 秒

... 如此類推[13]

運算模型

圖靈機

1. 讀取讀取器下嗰格係乜符號；
2. 編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
3. 將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

• `\$0010\$0011`（「0010」喺二進制係 2，而「0011」喺二進制係 3）。

```// 由 x 嗰度減 1，再加 1 落 y 嗰度，直至 x = 0 為止。
repeat until x == 0, then HALT {
// 用 T2（睇下面）
subtract 1 from x
// 用 T1（睇下面）

go back to the first \$
}
```

T2（將個數減 1）如下：

1. 攞補充－將 1 冚唪唥變做 0，0 冚唪唥變做 1；
2. 將個數加 1（睇 T1）；
3. 再做一次補充。

T1（將個數加 1）如下：

1. 如果喺個數嘅左邊盡頭（\$）起始，行去個數嘅右邊盡頭；
2. 由右邊開始行，將所有 1 變做 0，直至
3. 將第一個 0 變成 1。

格仔自動機

1. 一粒生嘅細胞，如果鄰居數量少過 2 就會死（「孤獨」）；
2. 一粒生嘅細胞，如果鄰居數量多過 3 就會死（「迫死」）；
3. 一粒生嘅細胞，如果鄰居有 2 個或者 3 個，就會生存到下一代 ${\displaystyle t}$
4. 一粒死嘅細胞，如果鄰居啱啱好有 3 個，就會變成生嘅。

參考書

教科書

• Hopcroft, John E., and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9. One of the standard references in the field.
• Linz P. An introduction to formal language and automata. Narosa Publishing. ISBN 9788173197819.
• Michael Sipser (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. ISBN 978-1-133-18779-0.
• Eitan Gurari (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4. Archived from the original on 2007-01-07.
• Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
• Taylor, R. Gregory (1998). Models of Computation and Formal Languages. New York: Oxford University Press. ISBN 978-0-19-510983-2. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
• Lewis, F. D. (2007). Essentials of theoretical computer science A textbook covering the topics of formal languages, automata and grammars. The emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the results.
• Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1. Covers a wider range of topics than most other introductory books, including program semantics and quantification theory. Aimed at graduate students.

數學書

• Hartley Rogers, Jr (1987). Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1.
• S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9.
• Carl H. Smith, A recursive introduction to the theory of computation, Springer, 1994, ISBN 0-387-94332-3.

其他書

• Richard L. Epstein and Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 0-534-54644-7.

攷

1. Sipser, M. (2006). Introduction to the Theory of Computation (Vol. 2). Boston: Thomson Course Technology.
2. Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the Theory of Computation. Prentice Hall PTR.
3. Michael Sipser (2013). Introduction to the Theory of Computation 3rd. Cengage Learning. ISBN 978-1-133-18779-0. p. 1.
4. Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press.
5. Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View 互聯網檔案館歸檔，歸檔日期2019年6月5號，..
6. Donald Monk (1976). Mathematical Logic. Springer-Verlag.
7. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Pearson Education.
8. Khoussainov, B., & Nerode, A. (2012). Automata theory and its applications (Vol. 21). Springer Science & Business Media.
9. Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.
10. Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), pp 230–265.
11. Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
12. Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
13. Braatz, R. P., Young, P. M., Doyle, J. C., & Morari, M. (1994). Computational complexity of/spl mu/calculation. IEEE Transactions on Automatic Control, 39(5), 1000-1002.
14. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
15. Kolen, J. F., & Hutcheson, T. (2002). Reducing the time complexity of the fuzzy c-means algorithm. IEEE Transactions on Fuzzy Systems, 10(2), 263-267.
16. Alon, N., Matias, Y., & Szegedy, M. (1999). The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1), 137-147.
17. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
18. Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. MIT Press. p. 27.
19. Adamatzky, Andrew, ed. (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2.
20. Coombs, Stephen (15 February 2009), The Geometry and Pigmentation of Seashells, pp. 3–4, retrieved 2 September 2012.