圖靈機簡介

圖靈機是一種接受裝置，它接受由 0 型文法生成的語言（遞迴可列舉集）。它是由艾倫·圖靈於 1936 年發明的。

定義

圖靈機 (TM) 是一種數學模型，它由一條無限長的帶組成，帶被分成單元格，輸入放在這些單元格上。它包含一個讀取輸入帶的磁頭。一個狀態暫存器儲存圖靈機的狀態。讀取輸入符號後，它會被替換為另一個符號，其內部狀態發生變化，並且它從一個單元格向右或向左移動。如果 TM 達到最終狀態，則接受輸入字串，否則拒絕。

TM 可以正式描述為一個 7 元組 (Q, X, ∑, δ, q₀, B, F)，其中 -

• Q 是一個有限的狀態集

• X 是帶字母表

• ∑ 是輸入字母表

• δ 是一個轉移函式；δ : Q × X → Q × X × {左移, 右移}。

• q₀ 是初始狀態

• B 是空白符號

• F 是最終狀態集

與先前自動機的比較

下表顯示了圖靈機與有限自動機和下推自動機的區別。

圖靈機的示例

圖靈機 M = (Q, X, ∑, δ, q₀, B, F)，其中

• Q = {q₀, q₁, q₂, q_f}
• X = {a, b}
• ∑ = {1}
• q₀ = {q₀}
• B = 空白符號
• F = {q_f }

δ 由下表給出 -

這裡轉移 1Rq₁ 表示寫入符號為 1，磁帶向右移動，下一個狀態為 q₁。類似地，轉移 1Lq₂ 表示寫入符號為 1，磁帶向左移動，下一個狀態為 q₂。

圖靈機的時空複雜度

對於圖靈機，時間複雜度是指當機器為某些輸入符號初始化時磁帶移動次數的度量，空間複雜度是指寫入的磁帶單元格數。

所有合理函式的時間複雜度 -

T(n) = O(n log n)

TM 的空間複雜度 -

S(n) = O(n)