紙帶（tape）

紙帶（tape）是圖靈機的筆記本：一條被切成等大格子的長條，至少朝一個方向永遠延伸下去。每格在任一時刻恰好放一個符號。不同於只能記得自己處於有限多狀態中哪一個的有限自動機，也不同於只能看到堆疊頂端的下推自動機，圖靈機可以像你用草稿紙一樣自由地使用紙帶：讀任何一格、擦掉它、寫上新東西、稍後再回來。

兩個特性使紙帶強大。第一，它是無界的：事先不設定機器能用多少格的上限，所以它永遠不會用完空間。（它通常被稱為「無限」，但任一時刻只有有限多格與空白不同，因為機器只走了有限多步。）第二，它是可讀又可寫的：機器可以檢視一格，也可以覆寫它，次數不限。輸入字串一開始寫在紙帶上，每格一個符號，其餘各格由空白符號填滿；同一條紙帶接著兼作工作記憶體，若機器在計算一個函數，也兼作留下輸出的地方。

無界的可讀寫紙帶，是把圖靈機抬升到所有較弱模型之上的唯一要素。堆疊讓下推自動機能記住巢狀結構，卻逼它為了看頂端而忘掉底端；紙帶沒有這種紀律。誠實的提醒：「無界」並不表示機器身邊真有無限大的記憶體。它的意思是沒有固定的天花板。對任何一次會停機的計算，機器只碰到有限多格，正如真正的程式只用到它恰好需要的那麼多記憶體。