圖靈機
空白符號(blank symbol)
空白符號(blank symbol)是機器表達「這裡還沒寫過任何東西」的方式。由於紙帶無限長而輸入只有有限長,輸入以外的每一格都必須放點什麼,而那個東西就是空白。把它想成空白筆記紙的顏色:凡是你還沒畫過的地方都有它,而且明顯不同於你可能畫下的任何記號。
形式上,空白是一個特殊符號,常寫作 B 或方框字元,它屬於紙帶字母表,卻不屬於輸入字母表。所以計算一開始時,紙帶上以輸入符號寫著輸入字串,其餘各格由空白填滿,向兩端的虛無無限延伸。空白讓機器能偵測輸入的結尾:當讀寫頭往右掃過輸入、第一次讀到空白時,它就知道自己已經走出了結尾。機器也可以自己寫上空白,把格子擦回空的狀態。
空白必須被排除在輸入字母表之外,理由細微卻重要:如果空白能出現在輸入內部,機器就無法分辨真正的輸入結尾和身為輸入一部分的空白。藉由把空白保留給「空」這個含意,模型免費得到一個乾淨、無歧義的邊界標記。空白是紙帶字母表在輸入字母之外提供給機器做記帳的若干額外符號之一。
對輸入字母表 {0, 1},紙帶字母表可能是 {0, 1, X, B},其中 B 是空白。輸入 10 的紙帶是 ... B B 1 0 B B ...,所以當讀寫頭向右越過 0 並讀到 B 時,機器便斷定輸入到此結束。
空白標記輸入以外的一切,並充當輸入結束的訊號。
空白屬於紙帶字母表,卻永遠不屬於輸入字母表。正是這項排除,讓機器有一個無歧義的方法知道有限的輸入在哪裡結束。
又稱
另見