唯讀輸入帶與工作帶的約定（read-only input and work tapes）

這裡有個難題。我們想談論用記憶體少於自身輸入大小的機器，例如對 n 個符號的輸入只用 O(log n) 個草稿格子。但在普通的單帶機器上，輸入本身就躺在紙帶上、佔了 n 個格子，於是你永遠無法算到 n 以下。這就像要求學生用比考題印刷面積還少的紙來做筆記，而題目和筆記又共用同一張紙。解法是給他一塊獨立的草稿板。

這個約定是使用具有兩種紙帶的機器。其一是一條唯讀輸入帶：輸入寫在那裡，讀寫頭可以在上面移動、讀取符號，卻永遠不能覆寫它們。其二是一條或多條讀寫工作帶，一開始是空白的，機器所有的塗寫都在這裡進行。空間複雜度於是定義為所用的工作帶格子數，完全忽略輸入帶（以及若有的唯寫輸出帶）。一瞬間，次線性的界限就有意義了：機器可以讀取它很長的輸入，卻只保留少數幾個工作格子，於是像 L（對數空間）這樣的類別才有意義。

這是 L、NL 以及每個次線性空間類別背後的標準設定。重點是讀取不花記憶體代價，只有記住才花空間。一台對數空間機器無法把整個輸入抄進工作記憶體（那需要 n 個格子），所以它必須反覆掃描輸入來處理，僅保留常數個指標與計數器。提醒：這個約定只在次線性空間時改變局面；到了多項式空間以上，要不要把輸入帶算進去毫無差別，因為你早已綽綽有餘。