From Wikipedia, the free encyclopedia
運算模型(粵拼:wan6 syun3 mou4 jing4;英文:model of computation)係運算理論上嘅一個概念。一個運算模型會描述一部機械內含乜嘢函數,會點樣由輸入嗰度計個輸出出嚟。電腦科學家會用運算模型進行「唔同運算機械做起運算上嚟有乜分別」嘅研究。
圖靈機(Turing machine)係廿世紀運算理論最常分析嘅運算模型。一部圖靈機嘅運作如下:一部圖靈機會讀取一條分做若干個格嘅帶,條帶每個格裏面都會有個符號(可以係 1 同 0 等多個款);喺每一個時間點,部圖靈機個讀取器都會位於條帶其中一格,而部機就會做以下三個基本作業當中是但一個[1]:
圖靈機呢部抽象機械就噉睇好似好簡單,但查實可以計到好多嘢。
想像以下嘅演算法,條帶上面有兩個數值, 同 ,兩個都用二進制表達,而兩個數之間同條帶嘅起始有個 $
做標示,即係話部機會讀嘅輸入會類似噉嘅樣:
$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)如下:
T1(將個數加 1)如下:
例如如果輸入係 $0010$0011
,部機行完一次段演算法之後,條帶嘅狀態就會變成 $0000$0101
(0101 喺二進制入面係 5)-呢一部圖靈機曉做加減數。
格仔自動機(cellular automaton)係一種離散(discrete)運算模型。一部格仔自動機會有若干個格仔,每個格仔可以有若干個可能狀態,例如「著咗」(用黑色代表)同「冇著」(用冇色代表)。攞是但一個格仔,佢都有一個初始狀態,時間 喺初始嗰陣係 0, 會一吓一吓噉跳,變成 1、2、3... 等嘅離散數值;每當 跳嗰時,每個格仔嘅狀態會按自己同周圍格仔而家嘅狀態以及某啲事先講定咗嘅法則改變[2]。
生命棋(Conway's Game of Life)係一個出名嘅格仔自動機。生命棋嘅世界係一塊(無限大嘅)兩維四方格板,每一格(每個細胞)都有兩個可能嘅狀態:一係生(黑色),一係死(冇色)。每格會同佢上下左右以及對角嗰八個「鄰居」互動。每一步 嘅改變法則如下[3]:
生命棋嘅演算法一開始行( 開始演進),就會出好似附圖噉嘅樣嘅變化。
格仔自動機喺各科學領域上有相當嘅價值。生物學家就發現,好似生命棋等嘅格仔自動機可以攞嚟模擬好多生物學上嘅現象,例如有某啲品種嘅貝殼嘅式樣(一格格有色冇色)就係以類似格仔自動機噉嘅機制產生嘅:呢啲貝殼當中有啲色素細胞,會按照相鄰色素細胞嘅活動決定點分泌色素,從而決定個貝殼嘅色水同式樣[4]。
... 呀噉。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.