波斯特機

波斯特機(Post machine)圖靈機的一種等價表述形式·其指令為形如。siRqk' q}s>Lqk及。s>seqk
的四元組.其含義表示當內部狀態為q，所指單元內容為s，時，分別進行右移、左移及把s，改為s,，同時都取新的內部狀態為qk.另外，通常約定q。為初始狀態，而不指定終止狀態，當沒有任何指令可用時，便自動停機.其餘的詳細描述參見“圖靈機”.這種想計算機稱為波斯特機.由於波斯特機與圖靈機完全等價，有時也稱為圖靈機.