圖靈機
格局(瞬間描述,configuration)
格局(configuration)是機器在某一瞬間的完整快照:一張照片,捕捉了你若離開後再回來、要接續計算所需的一切。對圖靈機來說,那意味著三件事合在一起:控制處於哪個狀態、整條紙帶上究竟寫了什麼,以及讀寫頭停在哪裡。其餘都無關緊要,因為機器的下一步只取決於這些。
寫格局的一種標準、精簡的方式,是把紙帶內容寫出來,並把當前狀態恰好插在讀寫頭所讀符號的前面。所以字串 1 0 q3 1 1 表示:紙帶上是 1 0 1 1,機器處於狀態 q3,讀寫頭停在第三格(緊接 q3 之後的那個 1)。q3 左邊的一切是讀寫頭已經越過的紙帶;從被標記的符號往右是剩下的部分。尾端的空白通常省略,因為它們是隱含的。兩個格局完全相同,當且僅當狀態、紙帶內容與讀寫頭位置三者皆相符。
格局是描述整個計算所用的詞彙:機器透過單次套用轉移函數從一個格局走到下一個,而計算不過是一連串格局。它們也是關於圖靈機之證明的主力:起始格局(狀態 q0、讀寫頭在最左邊的輸入符號上)、接受格局(狀態 q_accept)與拒絕格局(狀態 q_reject)都是特例,許多論證的進行方式,就是推理格局如何一個接一個。
假設紙帶是 X a b,讀寫頭在 b 上、處於狀態 q5。格局是 X a q5 b。套用 δ(q5, b) = (q6, Y, L) 後,讀寫頭往左越過 a,得到下一個格局 X q6 a Y。
把狀態寫在所讀格子的正前方,一行就同時記下狀態、紙帶與讀寫頭。
格局是圖靈機版的、相當於下推自動機瞬間描述的東西,但它必須記下整條紙帶(與讀寫頭位置),而非只記一個堆疊,因為任何格子都可能被重新造訪。
又称
另见