從堆疊頂端再往上爬
你已花了好幾階，每次只給機器多一點點記憶體，看著它的能力跟著長大。一台 DFA 只記得目前的狀態——一道對自己去過哪裡一無所知的旋轉柵門。一台下推自動機裝上了一個堆疊，足以計數像 a^n b^n 那樣配對的巢狀，卻仍對最上面那盤之外的一切視而不見。每一次，總有一個頑固的語言剛好溜出能力範圍：DFA 做不到 a^n b^n，而 PDA 做不到 a^n b^n c^n（要讓三個數量同步前進，一個堆疊就少了）。本階梯接下來顯而易見的問題是：什麼樣的記憶體才足夠算出任何算得出來的東西？
答案由艾倫·圖靈於 1936 年找到，簡單得近乎令人難為情。把記憶體上的限制拿掉。不再是一個只能碰最上面的堆疊，而是給機器一長條紙——一條分成許多格子的紙帶，每格放一個符號——再加上一個停在某格上方、可移動的讀寫頭。讀寫頭可以讀它正下方的符號、把它擦掉並寫上一個新的，然後向左或向右走一格。整個升級就這麼多。要放在腦海裡的畫面是一本無盡的筆記本：你可以翻回先前寫過的任何內容、把它劃掉、再重寫。沒有東西被鎖起來；也沒有東西被擠出頂端。
為什麼筆記本是對的畫面
有三項自由把紙帶與你見過的每一種記憶體區分開來。第一，它可讀也可寫：輸入不是一段流過一次的串流，而是寫在紙帶上，機器在運作時可以把它覆寫掉（DFA 永遠不能更動自己讀到的東西）。第二，讀寫頭可雙向移動：它能折返去重新檢視一個很久以前經過的符號，而堆疊則把頂端之下的一切都藏起來。第三，紙帶是無界的：它有一個左端，輸入就放在那裡，但向右無限延伸，所以機器永遠不會用完空間。輸入右側躺著無限多個格子，裝著一個特別的空白符號（寫作 ⊔ 或 B），那是紙帶用來說「這裡還沒寫東西」的方式。
符號住在哪裡：兩個字母表與一張快照
正如 PDA 把它的輸入字母表 Σ 與堆疊字母表 Γ 分開，圖靈機也用到兩個你必須分清楚的字母表。輸入字母表 Σ（Sigma）裝著輸入字串可能包含的符號。紙帶字母表 Γ（Gamma）是一個嚴格更大的集合，是機器可以寫到紙帶上的東西：它包含整個 Σ，加上空白符號，再加上機器自己發明的任何私用記帳符號——例如把一個已標記的 'a' 寫成 X，表示「這個 'a' 已經數過了」。空白符號住在 Γ 裡，卻從不在 Σ 裡，所以輸入字串本身絕不會含有空白。
在 PDA 那裡，你學到單一個數字——目前的狀態——已不足以描述處境；你需要一張 (狀態, 剩餘輸入, 堆疊) 的快照。圖靈機需要同一種完整的照片，稱為格局（configuration）。要確切知道一台 TM 站在哪裡，你需要三樣東西：(1) 它目前的狀態、(2) 紙帶的全部內容、(3) 讀寫頭的位置。把這三樣捕捉下來，你就能僅憑它們繼續這場計算——格局就是機器在某一瞬間的全部處境，正如瞬間描述之於 PDA。
一步動作：讀、寫、移動
DFA 的規則讀一個符號並改變狀態。PDA 的規則讀三樣東西並重建堆疊頂端。圖靈機那條單一的規則，也就是它的轉移函數，在一個節拍裡做得最多。它的形狀是 delta(q, a) = (p, b, D)：在狀態 q、讀寫頭正讀著符號 a 時，機器移動到狀態 p、把那同一格裡的 a 覆寫成符號 b，然後讓讀寫頭朝方向 D 走一格，其中 D 是 L（左）或 R（右）。讀這一格、寫這一格、走一步——這就是整套指令，而每一場圖靈計算都只是這個三件組反覆進行。
留意三個誠實的細節。機器每一步都必須寫某個符號——想讓一格保持不變，它就把剛讀到的同一個符號寫回去（b = a），正如 PDA 可以彈出 X 再推入 X 以原地不動。讀寫頭可以寫上一個空白，等於把一格擦掉。又因為規則讀的是讀寫頭下方的符號、且可重寫整條紙帶，TM 能標記一個符號、走到很遠的地方、做些工作、再折返讀自己留下的便條——這正是最終攻破 a^n b^n c^n 的那一步動作。這種折返對堆疊是不可能的，也正是這個模型更強的核心所在。
Marking off matched pairs for a^n b^n on a Turing machine
(input alphabet Sigma = {a, b}; tape alphabet Gamma = {a, b, X, B}; B = blank)
Idea: cross off the leftmost a (write X), shuttle right to cross off the
leftmost remaining b (write X), return left, repeat. Accept when none left.
Configuration shown as: ...tape..., ^ marks the cell under the head
start [ a a b b B ] input aabb on the tape
^
mark a [ X a b b B ] write X over first a, walk RIGHT past a's
^
[ X a b b B ] keep stepping right over a, then over b...
^
find b [ X a X b B ] write X over first b, now walk LEFT
^
back left [ X a X b B ] step left until an X, then onto the next a
^
mark a [ X X X b B ] cross the next a ... walk right to next b
^
find b [ X X X X B ] cross the last b
scan [ X X X X B ] no a, no b left -> ACCEPT (counts matched)
If an a is left with no b (or a b with no a), the scan finds a leftover
letter -> REJECT. The X's are the machine's private notes, never input.三種結局，以及一台也會計算的機器
DFA 結束時，只是把輸入讀完了，你再檢查它的狀態是不是接受狀態。圖靈機結束的方式不同，因為它掌控自己的讀寫頭，不必穩步朝著輸入的盡頭前進。一場 TM 運行會抵達三種結局之一。它可以在指定的接受狀態停機（成功）。它可以在指定的拒絕狀態停機（失敗）。或者——真正新出現的可能性——它可以永遠循環，根本不停機，讀寫頭無止盡地折返，卻從未進入任何接受或拒絕狀態。這第三種結局在底下幾階沒有對應物：DFA 總會停下，圖靈機卻不必。
那第三種結局逼出一個整個階梯都將仰賴的區別，所以現在就用白話認識它。一個語言被某台 TM 辨識（recognize），是指這台機器恰好接受該語言中的字串——但對於不在語言中的字串，它可以拒絕或永遠循環。一個語言被某台 TM 判定（decide），是指這台機器是一台會停機的機器：它總會停下、接受成員並拒絕非成員、從不循環。判定是黃金標準——每一次都給出明確的是或否——而辨識則容忍一台可能一頭栽進無盡計算、永不給你答案的機器。本階梯第三與第四篇正是專講這道縫隙；現在只要先記下：循環是真實存在的，而它把這兩個詞劈成了兩半。
最後一次重新框定，能讓這個模型不顯得狹隘。我們一直把 TM 說成針對某語言的是/否機器，但那完全相同的硬體會計算函數。讓紙帶上一開始放著輸入；當機器停機（若它會停機）時，紙帶上剩下的不論是什麼字串，就是輸出。所以一台輸入為二進位數 1011 的 TM 可以在紙帶上留著 1100 停機——它計算了一次遞增。把輸入複製成並排的兩份，或把兩個數相加，做法相同：寫、標記、折返、重寫。因此圖靈機不只是一台比 PDA 更強的辨識器；它是一台完完整整、雖極其簡單的電腦——這正是它成為「可計算」一詞之定義的緣由。