運算模型

運算模型（粵拼：wan6 syun3 mou4 jing4；英文：model of computation）係運算理論上嘅一個概念。一個運算模型會描述一部機械內含乜嘢函數，會點樣由輸入嗰度計個輸出出嚟。電腦科學家會用運算模型進行「唔同運算機械做起運算上嚟有乜分別」嘅研究。

圖靈機

内文：圖靈機

睇埋：圖靈論題

圖靈機（Turing machine）係廿世紀運算理論最常分析嘅運算模型。一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 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）－呢一部圖靈機曉做加減數。

格仔自動機

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

内文：格仔自動機

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

例：生命棋

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

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

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

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

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

第啲運算模型

• 寄存器機（register machine）
• 遞歸函數（μ-recursive functions）
• 組合子邏輯（combinatory logic）
• λ 演算（lambda calculus）
• 馬可夫演算法（Markov algorithm）
• 有限狀態機（FSM）

... 呀噉。

睇埋

• 運算理論
• 電腦科學
• 系統