什麼是理論計算機科學中的圖靈機？

圖靈機是一種計算模型，類似於有限自動機 (FA)、下推自動機 (PDA)，它基於無限制文法工作。與 FA 和 PDA 相比，圖靈機是最強大的計算模型。

正式地，圖靈機 M 可以定義如下：

M = (Q, X, ∑, δ, q0, B, F)

• Q 表示有限的、非空的狀態集。

• X 表示帶字母表。

• ∑ 表示非空的輸入字母表。

• δ 是轉移函式，其對映關係為 δ : Q x X → Q x X x {左移, 右移}。

• q0 是機器的初始狀態。

• B 是空白符號。

• F 是最終狀態集或停機狀態集。

單帶圖靈機有一個無限長的單帶，它被分成若干個單元格。

這些單元格中包含帶符號。

存在一個有限控制器，它根據給定的輸入控制圖靈機的執行。

有限控制器有一個讀/寫頭，它指向帶上的一個單元格。

圖靈機可以從一個單元格左右移動到另一個單元格。

輸入和輸出帶符號

↑

有限控制器

圖靈機對輸入可以有三種類型的動作。

列印 Si，左移一個方格 (L)，並轉到狀態 qj。

列印 Si，右移一個方格 (R)，並轉到狀態 qj。

列印 Si，不移動 (N)，並轉到狀態 qj。

Bhanu Priya

更新於：2023年9月14日

32K+ 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習