運算理論

係數學同理論電腦科學嘅一個子領域，專門研究機械點樣用演算法解難。運算理論會用數學證明等嘅方法，嘗試思考唔同種類嘅理論性運算機械喺解難能力上有乜差異、有啲乜嘢問題係能夠用運算機械解嘅以及一個運算上嘅問題最高嘅可能解決效率等等嘅問題。

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

運算理論會攞一啲運算模型嚟將運算機械概念化。當中喺廿一世紀最常用嘅運算模型係所謂嘅圖靈機，圖靈機可以想像成一部噉嘅機械：部圖靈機會讀取一條分做若干個格嘅帶，每個格裏面都會有個符號；喺每一個時間點，部圖靈機個讀取器都讀住其中一格，並且會做以下三個基本作業嘅其中一個：
讀取讀取器下嗰格有乜符號；
編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔蘺嘅一個格。

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

基本概念 

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

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

要解決嘅問題：家吓俾一列正數你，假設呢個列唔係一個空列，同我搵嗰列數入面最大嗰個出嚟。
用嘅演算法嘅步驟：
設一個變數，叫佢做「max」，並且將佢個數值設做「0」；
將收到嗰列正數逐個逐個攞嚟同 max 比較吓；
如果撞到一個大過 max 嘅數嘅話，將 max 嘅數值設做 x，並且繼續將 max 同下個正數比較吓；
將最後得出嗰個 max 嘅數值俾出嚟。max 嘅數值會係成列數入面最大嗰個。

呢段演算法用 Python寫出嚟嘅話會係：
 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 嘅數量係咪雙數：部機開始於  狀態；當部機讀到一個 0 嗰陣，會進入  狀態，而當佢再讀到個 0 嗰時，會返去  狀態；如果佢讀到嘅係 1 或者第啲符號嗰時，部機唔會改變狀態；喺部機讀完嗮成串符號之後，如果串符號入面 0 嘅數量係雙數，佢會處於  狀態，否則佢就將會處於  狀態。呢部抽象機械可以用多種唔同嘅物理機制實現－運算理論上嘅思考係抽象嘅。

可運算度 

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

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

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

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

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

呢個程序會引致一個大矛盾：如果 g() 係會停機嘅，噉 halts(g) 會出「真」，於是 g() 就會進入永遠係噉行嘅狀態－出現矛盾；而如果 g() 係唔會停機嘅，噉 halts(g) 會出「假」，於是 g() 就唔會進入永遠係噉行嘅狀態－又出現矛盾。因為噉，如果呢個世界有電腦曉攞一個程式嘅碼做輸入，再俾出正確嘅「呢段碼會唔會停機」輸出嘅話，就會出現一個邏輯上嘅矛盾，所以呢一個程式冇可能存在喺呢個世界上－即係話「攞一個程式嘅碼做輸入，再正確噉判斷個程式會唔會停機」係一個不可運算嘅問題。可運算度理論會思考停機問題等唔同類嘅運算問題，並且理解呢啲問題當中有邊啲係可運算嘅、邊啲係不可運算嘅，而呢啲研究增加咗人類對電腦嘅局限嘅理解。

運算複雜度 

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

運算複雜度理論最重視嘅運算複雜度指標有兩個：
時間複雜度，指一段運算要用幾多時間解；
空間複雜度，指一段運算要用幾多記憶體嚟解。

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

當中  係個輸入嘅大細。

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

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

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

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

運算模型

圖靈機 

圖靈機係廿世紀運算理論最常分析嘅運算模型。一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中是但一個：
讀取讀取器下嗰格係乜符號；
編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔蘺嘅一個格。

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

格仔自動機 

格仔自動機係一種離散運算模型。一部格仔自動機會有若干個格仔，每個格仔可以有若干個可能狀態，例如「著咗」同「冇著」。攞是但一個格仔，佢都有一個初始狀態，時間  喺初始嗰陣係 0， 會一吓一吓噉跳，變成 1、2、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.
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 at MIT.
Theory of Computation at Harvard.
Computability Logic - A theory of interactive computation. The main web source on this subject.

應用數學