多帶圖靈機（multitape Turing machine）

想像你在書桌前解一道難題。只用一張紙時，你得不斷來回挪動：這裡寫草稿、那裡記累計、上方留著原始數字，邊算邊擦邊改。若改成用三張各司其職的紙，工作就輕鬆許多，因為你不必越過一樣東西才能搆到另一樣。多帶圖靈機（multitape Turing machine）正是如此：一台有好幾條紙帶（而非一條）的圖靈機，每條都有自己可獨立移動的讀寫頭。

形式上，一台 k 帶圖靈機有 k 條紙帶與 k 個讀寫頭。在一步之內，它讀取目前各讀寫頭下方的 k 個符號，並依當前狀態與這 k 個符號，在每條帶上各寫一個新符號、各自獨立地把每個讀寫頭向左或向右移動（或原地不動），並改變狀態。於是單一轉移現在同時取決於一整個符號元組：δ(q, a1, ..., ak) = (p, b1, ..., bk, D1, ..., Dk)，其中 δ（delta）是轉移函數，每個 Di 是移動方向。輸入通常放在第一條帶上，其餘留空白。多出的帶子只是額外的草稿空間與額外的讀寫頭，沒有更玄的東西。

這個變體的重點是方便，而非能力更強。設計一台三帶機（一帶放輸入、一帶計數、一帶放輸出）遠比把所有東西塞進一條帶容易。透過模擬可以證明一個了不起的事實：任何 k 帶機都能被一台普通的單帶機模仿，方法是把 k 條帶並排成單帶上的 k 條軌道（tracks），標記每個讀寫頭的位置，並在每一步前掃過整條帶以蒐集全部 k 個符號。它們識別的語言完全相同。單帶模擬只慢一個多項式倍數（大約是時間的平方），這正是複雜度理論可以談「多項式時間」而不必指明帶數的原因。