計數器機（register / counter machine）

想像一位書記員，有固定數量的計數盒與一本極小的規則手冊。每個盒子可放任意整數顆石子。手冊只允許書記員做兩種事：往某盒加一顆石子，或試著從某盒拿走一顆石子（若該盒已空，就改跳到另一條規則）。這就是全部的本領了。計數器機（counter machine，又稱暫存器機 register machine）正是這樣一台精簡到極致的電腦：一個有限程式操作著幾個整數計數器，只有遞增、遞減與測試是否為零。

形式上，計數器機有固定有限個暫存器，各持一個自然數，以及一張有限的、編了號的指令清單。典型指令為 INC(r)（暫存器 r 加 1，跳到下一條指令），以及一個合併的「測試並遞減」：「若暫存器 r 為零，跳到指令 j；否則 r 減 1 並繼續」。輸入以一個數字載入某個暫存器；機器停機時答案就放在某暫存器裡。沒有符號、沒有紙帶、沒有字串，只有往上往下計數，以及依某計數器是否歸零來分支。

令人吃驚的定理是：一台只有兩個計數器、配上這個極小指令集的機器，已經是圖靈完備（Turing-complete）的：它能計算每一個圖靈可計算的函數。訣竅在編碼：你可以把好幾條工作帶或暫存器的全部內容打包進單一整數（例如用質數的冪，如 2^a * 3^b * 5^c），於是遞增、遞減與零測試就足以讀取並更新該編碼。計數器機之所以重要，是因為它顯示計算所需的硬體竟少得驚人，而且因其極簡結構讓模擬容易寫下來，它是不可判定性證明的愛用工具。誠實的提醒是：「兩個計數器就夠」是關於可計算性、而非效率的優美結果，那些編碼會讓這類機器慢得荒謬。