運算理論

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search
一部圖靈機嘅想像圖;部機會一路讀取條帶上面嘅一格,並且對嗰個格作出運算,再決定要使唔使改嗰格同埋跟住要向左郁定向右郁。

運算理論粵拼wan6 syun3 lei5 leon6英文theory of computation)係數學理論電腦科學嘅一個子領域,專門研究機械點樣用演算法(algorithm)解難。運算理論會用數學證明等嘅方法,嘗試思考唔同種類嘅理論性運算機械喺解難能力上有乜差異(自動機理論)、有啲乜嘢問題係能夠(或者唔能夠)用運算機械解嘅(可運算性理論)、以及一個運算上嘅問題最高嘅可能解決效率(運算複雜性理論)等等嘅問題[1][2]

用一句嘢概括嘅話,運算理論主要思考嘅係呢個問題[3]

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

運算理論會攞一啲運算模型(model of computation;一個運算模型會描述一部機械點由輸入嗰度計個輸出出嚟)嚟將運算機械概念化。當中喺廿一世紀最常用嘅運算模型係所謂嘅圖靈機(Turing machine;個名取自大數學家亞倫圖靈),圖靈機可以想像成一部噉嘅機械:部圖靈機會讀取一條分做若干個格嘅帶,每個格裏面都會有個符號(1 同 0 等);喺每一個時間點,部圖靈機個讀取器都讀住其中一格,並且會做以下三個基本作業嘅其中一個[4]

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

圖靈機呢部抽象(abstract)機械就噉睇好似好簡單,但查實可以計到好多嘢[5],好似簡單嘅數噉[6],而有咗加減數,就可以計到好多嘢。好似圖靈機等嘅概念性機械就係運算模型,運算理論家會思考唔同種類嘅運算模型,以及剖析呢啲運算模型喺解難能力上有乜分別,加深人對運算同電腦嘅理論性了解[7]

概論[編輯]

運算理論可以分做三大子領域:

自動機理論[編輯]

內文: 自動機理論

自動機理論(automata theory)研究抽象機械,以及唔同種類嘅抽象機械喺解難能力上有乜唔同。自動機理論最基本嘅諗頭係抽象機械(abstract machine)-一部抽象機械內部有一啲函數,並且會攞一啲輸入,按輸入同內部嘅函數計個輸出出嚟,例如係以下呢部極簡單嘅抽象機械[8]

DFAexample.svg

上圖呢部機械會攞一串符號做輸入,再話俾用家知,串符號入面 0 嘅數量係咪雙數:部機開始於 S1 狀態;當部機讀到一個 0 嗰陣,會進入 S2 狀態,而當佢再讀到個 0 嗰時,會返去 S1 狀態;如果佢讀到嘅係 1 或者第啲符號嗰時,部機唔會改變狀態;喺部機讀完嗮串符號之後,如果串符號入面 0 嘅數量係雙數,佢會處於 S1 狀態,否則佢就會處於 S2 狀態。呢部抽象機械可以用多種唔同嘅物理機制實現。自動機理論為「運算機械」-即係電腦-呢個詞奠立咗個定義(任何曉自動噉做一連串運算嘅機械),會想像同研究種種抽象機械嘅特性以及佢哋喺解難能力上有乜差異,而呢啲研究對電腦嘅設計同改良好有幫助[8][9]

可運算性理論[編輯]

內文: 可運算性理論

可運算性理論(computability theory)集中於思考唔同嘅運算問題係咪可運算嘅(computable)-如果一個問題係可以用電腦解決嘅,噉呢個問題就係可運算嘅,否則呢個問題就係不可運算嘅,好似係好出名嘅停機問題(halting problem)噉。首先,電腦程式可以分做兩大種[10]

例:while (true) continue;呢種程式唔會停機-部電腦一行呢個程式就會一路行落去,永世唔會停。
例:print "Hello, world!";呢種程式會停機-部電腦會逐行逐行碼行咗佢,最後停低。

根據英國數學家亞倫圖靈(Alan Turing)嘅證明,呢個世界冇可能有電腦能夠攞一個程式嘅碼做輸入,再俾出正確嘅「呢段碼會唔會停機」輸出(停機問題)。圖靈用嘅係反證法(proof by contradiction),證明如果呢個世界上有個程式能夠做到噉嘅工作,就會發生一啲冇可能嘅事。呢個證明大致上係噉嘅[11]

想像有個程式,halts(f),如果 f 係一個會停機嘅子程序halts(f) 會出「真」(1),否則halts(f) 會出「假」(0),再想像以下呢個程序:

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

呢個程序會引致一個大矛盾:如果 g() 係會停機嘅,噉 halts(g) 會出「真」,於是 g() 就會進入永遠係噉行(loop_forever)嘅狀態-出現矛盾;而如果 g() 係唔會停機嘅,噉 halts(g) 會出「假」,於是 g() 就唔會進入永遠係噉行(loop_forever)嘅狀態-又出現矛盾。因為噉,如果呢個世界有電腦曉攞一個程式嘅碼做輸入,再俾出正確嘅「呢段碼會唔會停機」輸出嘅話,就會出現一個邏輯上嘅矛盾,所以呢一個程式冇可能存在喺呢個世界上-即係話「攞一個程式嘅碼做輸入,再正確噉判斷個程式會唔會停機」係一個不可運算嘅問題[11][12]

可運算性理論會思考停機問題等唔同種類嘅運算問題,並且理解呢啲問題當中有邊啲係可運算嘅、邊啲係不可運算嘅,而呢啲研究增加咗人類對電腦嘅局限嘅理解[11]

運算複雜性理論[編輯]

內文: 運算複雜性理論

運算複雜性理論(computational complexity theory)係運算理論第三個子領域:喺知道咗一個問題係有可能用電腦解決之後,電腦科學家往往會希望知道要解決呢個問題有幾撈絞-例如想像有一個問題,可運算性理論嘅分析顯示佢係有可能用電腦解決嘅,但打後嘅分析發現,解決呢個問題要用嗰個演算法,就算用最先進嘅電腦行都要用(例如)成 100 年先行得完,噉嘅話呢個問題喺實際應用上根本冇得有效率噉解決。對「可以解到嘅問題要嘥幾多時間空間先解到」嘅思考就係運算複雜性理論嘅重心[13][14]

運算複雜性理論最重視嘅變數有兩個[13]

  • 時間複雜度(time complexity),指一段運算要用幾多時間解;
  • 空間複雜度(space complexity),指一段運算要用幾多記憶體嚟解。

喺分析一個演算法嘅複雜性嗰陣,電腦科學家會將時間複雜度同空間複雜度表達做輸入嘅大細嘅函數,即係話一個演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣(大 O 符號;big O notation):O(n log n),當中 n 係個輸入嘅大細(例:如果個輸入係個數字,n 會係佢有幾多個位),O(n log n) 反映個演算法要行嘅步嘅數量隨 n 嘅變化,而 T(n log n) 就係實際行要花嘅時間隨 n 嘅變化。例如如果話一個演算法用嘅時間(以秒計)係 T(n log n) ,而 n 表示個輸入有幾多個位:

  • n 係 10,用嘅時間係 10 秒;
  • n 係 10,000,用嘅時間係 40,000 秒

... 如此類推[13]

舉個簡單例子說明,想像而家電腦科學家想諗個演算法出嚟,解決「俾一柞數字個程式,搵吓柞數字當中有冇某一個特定數字」;最原始嘅演算法係將柞數字逐個逐個睇一次,比較吓個數字同個目標數字係咪一樣;用呢種做法嘅話,最壞情況係每次要搵數字嗰陣,都要耖足嗮成柞數先俾到答案(有定冇),所以呢個演算法嘅最壞情況(worst-case scenario)時間複雜性就係 n 個單位嘅時間,當中 n 代表輸入嗰柞數字入面有幾多個數字,而單位時間代表耖一個數字要用嘅時間[15]

喺電腦科學上,對唔同嘅演算法作出運算複雜性分析好有用:一般認為,一個好用嘅演算法理應能夠喺不損準確性嘅情況下,盡可能用最少嘅時間同空間嚟達成任務-所以對研究演算法嘅電腦科學家嚟講,時間複雜度同空間複雜度都係有用嘅指標,可以攞嚟量度一個演算法有幾好用[16][17]

運算模型[編輯]

內文: 運算模型

圖靈機[編輯]

內文: 圖靈機

圖靈機(Turing machine)係廿世紀運算理論最常分析嘅運算模型。一部圖靈機嘅運作如下:一部圖靈機會讀取一條分做若干個格嘅帶,條帶每個格裏面都會有個符號(可以係 1 同 0 等多個款);喺每一個時間點,部圖靈機個讀取器都會位於條帶其中一格,而部機會做以下三個基本作業當中是但一個[4][18]

  1. 讀取讀取器下嗰格係乜符號;
  2. 編輯嗰格-寫一個新嘅符號落去或者刪除咗嗰格佢;
  3. 將條帶向左或者向右移一格,等個讀取器可以讀取打前嗰個格隔離嘅一個格。
一條圖靈機輸入帶嘅抽象圖解; 代表第 款符號。

圖靈機呢部抽象(abstract)機械就噉睇好似好簡單,但查實可以計到好多嘢[5]

例:圖靈機計加減法

想像以下嘅演算法,條帶上面有兩個數值,,兩個都用二進制表達,而兩個數之間同條帶嘅起始有個 $ 做標示,即係話部機會讀嘅輸入會類似噉嘅樣[6]

  • $0010$0011(「0010」喺二進制係 2,而「0011」喺二進制係 3)。

再想像部圖靈機跟以下嘅演算法行[6]

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

 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。

例如如果輸入係 $0010$0011,部機行完一次段演算法之後,條帶嘅狀態就會變成 $0000$0101(「0101」喺二進制入面係 5)-呢一部圖靈機曉做加減數[6]

格仔自動機[編輯]

生命棋嘅圖例;黑色格代表「生」,冇色格代表「死」。
內文: 格仔自動機

格仔自動機(cellular automaton)係一種離散(discrete)運算模型。一部格仔自動機會有若干個格仔,每個格仔可以有若干個可能狀態,例如「著咗」(用黑色代表)同「冇著」(用冇色代表)。攞是但一個格仔,佢都有一個初始狀態,時間 喺初始嗰陣係 0, 會一吓一吓噉跳,變成 1、2、3... 等嘅離散數值;每當 跳嗰時,每個格仔嘅狀態會按自己同周圍格仔而家嘅狀態以及某啲事先講定咗嘅法則改變[19]

例:生命棋

生命棋(Conway's Game of Life)係一個出名嘅格仔自動機。生命棋嘅世界係一塊(無限大嘅)兩維四方格板,每一格(每個細胞)都有兩個可能嘅狀態:一係生(黑色),一係死(冇色)。每格會同佢上下左右以及對角嗰八個「鄰居」互動。每一步 嘅改變法則如下[20]

  1. 一粒生嘅細胞,如果鄰居數量少過 2 就會死(「孤獨」);
  2. 一粒生嘅細胞,如果鄰居數量多過 3 就會死(「迫死」);
  3. 一粒生嘅細胞,如果鄰居有 2 個或者 3 個,就會生存到下一代
  4. 一粒死嘅細胞,如果鄰居啱啱好有 3 個,就會變成生嘅。

生命棋嘅演算法一開始行( 開始演進),就會出好似附圖噉嘅樣嘅變化[20]

格仔自動機喺各科學領域上有相當嘅價值。生物學家就發現,好似生命棋等嘅格仔自動機可以攞嚟模擬好多生物學上嘅現象,例如有某啲品種嘅貝殼嘅式樣(一格格有色冇色)就係以類似格仔自動機噉嘅機制產生嘅:呢啲貝殼當中有啲色素細胞,會按照相鄰色素細胞嘅活動決定點分泌色素,從而決定個貝殼嘅色水同式樣[21]

一個有格仔自動機機制嘅貝殼

第啲運算模型[編輯]

睇埋[編輯]

參考書[編輯]

教科書[編輯]

  • 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. 4.0 4.1 Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary Edition). Princeton University Press.
  5. 5.0 5.1 Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.
  6. 6.0 6.1 6.2 6.3 Turing Machine example to add two numbers.
  7. Donald Monk (1976). Mathematical Logic. Springer-Verlag.
  8. 8.0 8.1 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Pearson Education.
  9. Khoussainov, B., & Nerode, A. (2012). Automata theory and its applications (Vol. 21). Springer Science & Business Media.
  10. Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (58): 345–363.
  11. 11.0 11.1 11.2 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.
  12. 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.
  13. 13.0 13.1 13.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press.
  14. 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.
  15. Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
  16. 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.
  17. 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.
  18. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
  19. Toffoli, Tommaso; Margolus, Norman (1987). Cellular Automata Machines: A New Environment for Modeling. MIT Press. p. 27.
  20. 20.0 20.1 Adamatzky, Andrew, ed. (2010). Game of Life Cellular Automata. Springer. ISBN 978-1-84996-216-2.
  21. Coombs, Stephen (15 February 2009), The Geometry and Pigmentation of Seashells, pp. 3–4, retrieved 2 September 2012.

[編輯]