圖靈機
讀寫頭(tape head)
讀寫頭(tape head)是機器唯一會移動的指尖:它此刻正觸碰的那一格。紙帶可以無限長,但機器無法一次看到全部;它只能讀、也只能寫讀寫頭底下的那一格。要檢視遠處的某一格,它必須把讀寫頭一步一步走過去,像一個人透過小窗讀一卷卷軸那樣。
每一步,讀寫頭依轉移函數所示,恰好做三件事:讀出當前格中的符號,往同一格寫回一個符號(可能相同,也可能不同),然後恰好往左或往右挪一格。在基本模型裡它不能原地不動,也不能跳躍;移動永遠是單步。由於讀寫頭先讀後寫,典型的一步是:「我在這裡看到一個 a,我寫上 X 把它劃掉,然後右移去看下一個符號。」
讀寫頭能對所造訪的格子既讀又寫,正是它與早期機器的全部差別。DFA 的輸入指標只能讀,而且只往右移、不回頭。圖靈機的讀寫頭可以重讀、改寫,並來回穿梭,這正是圖靈機比對相隔很遠的輸入片段的方法(例如檢查字串前半是否等於後半)。代價是讀寫頭成了瓶頸:要比對第 1 格與第 1000 格,它必須實際走過一千格,這也是為什麼這個模型雖然表達力最強卻很慢的原因之一。
要檢查輸入 ab 是否等於 ba,讀寫頭讀出第一個 a、做記號,往右走去與對應字母比對,再往左走回去處理下一個。這一路來回走動,正是相隔遙遠的格子比對一次要花許多步的原因。
讀寫頭一次只看到一格;要碰到另一格,意味著一步一步走過去。
在標準模型裡,讀寫頭每一步都必須移動(左或右)。有些課本加上「原地不動」選項;它不改變哪些語言能被識別,只是方便而已(見「原地不動移動」)。
又称
另见