運算理論

圖靈機嘅大致實現；部機會一路讀取條帶上面嘅一格，並且對嗰個格作出運算，再決定
(1) 使唔使改嗰格，同埋
(2) 跟住要向左郁定向右郁。

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

用一句嘢概括嘅話，運算理論主要思考嘅係呢個問題：

「

電腦（運算機械）嘅基本能力同極限係乜？

」

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

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

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

基本概念

内文：運算同運算問題

睇埋：理論電腦科學

廣義上，運算係指涉及跟從一個定義好嘅模型、通過一連串算術同非算術步驟做嘅計算，廣義上可以包含任何由輸入俾輸出嘅過程。呢啲計算可以係算術性質嘅（加減乘除等），又可以係做邏輯代數嘅處理，中途會處理資訊。運算嘅例子有演算法：喺行一段演算法嗰陣，一部電腦會接收用家俾嘅一串演算法，一段演算法包含一串有先後之分嘅指示，每行指示教部電腦做某啲計算，等等，通過行呢段演算法，部電腦會俾出一個輸出，如果段演算法設計得好而且部電腦能夠無誤噉行段演算法嘅話，個輸出正正會係個用家想要嘅結果。

舉個簡單例子說明，好似係以下呢段用粵文寫嘅演算法（虛擬碼）噉，就做咗一連串嘅運算：

要解決嘅問題：家吓俾一列正數（輸入）你，假設呢個列唔係一個空列，同我搵嗰列數入面最大嗰個出嚟。

用嘅演算法嘅步驟：

1. 設一個變數，叫佢做「max」，並且將佢個數值設做「0」；
2. 將收到嗰列正數逐個逐個攞嚟同 max 比較吓；
3. 如果撞到一個大過 max 嘅數（叫呢個數做「x」）嘅話，將 max 嘅數值設做 x，並且繼續將 max 同下個正數比較吓；（邏輯代數）
4. 將最後得出嗰個 max 嘅數值俾出嚟（輸出）。max 嘅數值會係成列數入面最大嗰個。

呢段演算法用 Python（1991 年出嘅一種程式語言）寫出嚟嘅話會係：

# Input：一列冧巴，叫列冧巴做「L」。
# Output：L 入面最大嘅冧巴。

def find_max (L):
   max = 0         # 設最大值做 0。
   for x in L:     # 同 L 入面每個元件做以下嘅嘢...
      if x > max:       # 如果 x 大過最大值...
         max = x         # ... 設最大值做 x。
   return max      # 做完嗮上述嘅嘢後，俾返個最大值出嚟。

研究運算嘅領域係電腦科學，而運算理論係電腦科學一個高度理論化嘅子領域：電腦科學會研究運算嘅應用，研究點用電腦運算造出有經濟價值嘅產品同技術，例如電腦圖像學研究電腦圖像－用電腦嘅運算功能造圖像嘅技術，而呢啲圖像可以用嚟製作電腦動畫等嘅產品；但另一方面，電腦科學又會用好似數學噉嘅方法研究運算呢家嘢嘅本質－做呢啲研究嘅電腦科學子領域就係運算理論。

主要子理論

運算理論上最重要嘅子理論有以下呢啲：

自動機理論

内文：自動機理論

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

上圖呢部機械會攞一串符號做輸入，再話俾用家知，串符號入面 0 嘅數量係咪雙數：部機開始於 ${\text{S}}_{1}$ 狀態；當部機讀到一個 0 嗰陣，會進入 ${\text{S}}_{2}$ 狀態，而當佢再讀到個 0 嗰時，會返去 ${\text{S}}_{1}$ 狀態；如果佢讀到嘅係 1 或者第啲符號嗰時，部機唔會改變狀態；喺部機讀完嗮成串符號之後，如果串符號入面 0 嘅數量係雙數，佢會處於 ${\text{S}}_{1}$ 狀態，否則佢就將會處於 ${\text{S}}_{2}$ 狀態。呢部抽象機械可以用多種唔同嘅物理機制實現－運算理論上嘅思考係抽象嘅。

可運算度

内文：可運算度理論

睇埋：有效方法

可運算度理論集中於思考唔同嘅運算問題係咪可運算嘅－如果一個問題係可以用電腦解決嘅，噉呢個問題就係可運算嘅，否則呢個問題就係不可運算嘅，好似係好出名嘅停機問題噉。首先，電腦程式可以分做兩大種：

例 1：While (真), 做...；呢種程式唔會停機－部電腦一行呢個程式就會一路行落去，永世唔會停。

例 2：同我出 "Hello, world!"；呢種程式會停機－部電腦會逐行逐行碼行咗佢，最後停低。

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

想像有個程式，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）嘅狀態－又出現矛盾。因為噉，如果呢個世界有電腦曉攞一個程式嘅碼做輸入，再俾出正確嘅「呢段碼會唔會停機」輸出嘅話，就會出現一個邏輯上嘅矛盾，所以呢一個程式冇可能存在喺呢個世界上－即係話「攞一個程式嘅碼做輸入，再正確噉判斷個程式會唔會停機」係一個不可運算嘅問題。可運算度理論會思考停機問題等唔同類嘅運算問題，並且理解呢啲問題當中有邊啲係可運算嘅、邊啲係不可運算嘅，而呢啲研究增加咗人類對電腦嘅局限嘅理解。

運算複雜度

内文：運算複雜度理論同運算複雜度

睇埋：窮舉搜尋

運算複雜度理論係運算理論第三個子領域：知道咗一個問題係有可能用電腦解決之後，電腦科學家往往會希望知道個問題「有幾撈絞」－舉例說明，想像有個問題，可運算度理論嘅分析證明咗個問題係有可能用電腦解決嘅，但打後進一步嘅分析發現，解決呢個問題要用嗰段演算法好複雜，就算用最先進嘅電腦行都要用成 100 年先行得完，噉嘅話喺實際應用上個問題根本無法有效率噉解決。運算複雜度理論嘅重心就係思考「可以解到嘅問題，要嘥幾多時間空間先解到」。

運算複雜度理論最重視嘅運算複雜度指標有兩個：

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

喺分析一段演算法嘅複雜度嗰陣，電腦科學家會將時間複雜度同空間複雜度表達做輸入嘅大細嘅函數，即係話一段演算法嘅時間複雜度同空間複雜度通常寫成類似噉嘅樣（大 O 符號）：

$O(n\log n)$

當中 $n$ 係個輸入嘅大細（例：如果個輸入係個數字，$n$ 會係佢有幾多個位）。

舉個簡單例子說明，想像而家電腦科學家想諗段演算法出嚟，解決「俾一柞數字個程式，搵吓柞數字當中有冇某一個特定數字」；最原始嘅演算法係將柞數字逐個逐個睇一次，比較吓個數字同個目標數字係咪一樣，用虛擬碼表達嘅話如下：

for i : 1 to length of A
    if A[i] is equal to x
        return TRUE
return FALSE

用呢種做法嘅話，最壞情況係每次要搵數字嗰陣，都要耖caau3足嗮成柞數先俾到答案（答案係有定冇），所以呢段演算法嘅最壞情況時間複雜度就係 n 個單位嘅時間，當中 n 代表輸入嗰柞數字入面有幾多個數字，而單位時間代表耖一個數字要用嘅時間。

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

運算模型

内文：運算模型

圖靈機

内文：圖靈機

睇埋：圖靈論題

圖靈機係廿世紀運算理論最常分析嘅運算模型。一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 1 同 0 等多個款）；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中是但一個：

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

一條圖靈機輸入帶嘅抽象圖解；$s_{i}$ 代表第 $i$ 款符號。

圖靈機呢部抽象機械就噉睇好似好簡單，但查實可以計到好多嘢。

例：圖靈機計加減法

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

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

再想像部圖靈機跟以下嘅演算法行：

// 由 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）－呢一部圖靈機曉做加減數。

格自動機

生命棋嘅圖例；黑色格代表「生」，冇色格代表「死」。

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

内文：格仔自動機

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

生命棋係一部出名嘅格仔自動機。生命棋嘅世界係一塊無限大嘅 2D 四方格板，每一格（每粒細胞）都有兩個可能嘅狀態：一係生（黑色）一係死（冇色）。每格會同佢上下左右以及對角嗰八個「鄰居」互動。喺每一步（每步算係一吓剔tik1）$t$ 改變法則如下：

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

生命棋嘅演算法一開始行（$t$ 開始演進），就會出好似附圖噉嘅樣嘅變化。

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

第啲模型

• 寄存器機
• 遞歸函數
• 組合子邏輯
• λ 演算
• 馬可夫演算法
• 有限狀態機

呀噉。

睇埋

• 電腦科學 · 程式編寫
• 離散數學 · 演算法
• 人工智能
• 複雜系統
• 亞倫圖靈

文獻

教科書

• 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.
• 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.
• Carl H. Smith, A recursive introduction to the theory of computation, Springer, 1994, ISBN 0-387-94332-3.

拎

• Theory of Computation （英文），MIT 講運算理論。
• Theory of Computation （英文），哈佛大學講運算理論。