能夠自由存取的無限磁帶是很棒的東西，大幅提昇機器的運算能力，令運算能力的限制來源直指規則本身，就像〈停或不停？〉的停止問題，打造不出這種機器的限制來源就是規則本身，規則是運算最根本的重複，也就是某種形式的規律與不變，然而也是停止問題中矛盾的開端。
可以從另一個角度來看停止問題的導證過程，過程中其實在談的就是，若存在著可判斷停止的 A 程式（規則），必然存在著該程式判斷不了的 B 程式，A 程式必須改寫自身規則來判斷 B 程式可否停止，然而這又會存在著一個 C 程式，改寫自身後的 A 程式無法判斷的，這時 A 程式又得改寫自身來判斷 C 程式…
然而程式（規則）就是某種形式的規律，寫好的程式內容就不會變化，不斷變化、沒有規律的東西無法寫成程式。
能夠自由存取的無限磁帶，令機器的運算能力的限制來源直指規則本身，也就因此才會令已知的可行方式，像是使用雙磁帶、多維磁帶等，試圖昇級圖靈機設備來增強運算能力都沒能成功。
然而，設備確實會影響機器的運算能力，畢竟規則中就不能以該設備來進行描述，例如，若磁帶並非有限，那麼能做到的運算勢必會受到限制，畢竟能記憶的東西變少了，運算過程中若是捨棄了磁帶上某些資料，那些資料就完全消失，再也拿不回來了。
當然，現代電腦也並沒有無限多的記憶體，只不過多到多半不會用完（反而是比較擔心在管理記憶體本身資料上，能不能更快更有效率的問題），以至於許多開發者比較不會意識到記憶體有限帶來的運算能力問題。
那麼，如果磁帶不再是能自由存取呢？例如，將磁帶換成一個堆疊，資料會被放到堆疊，或者從堆疊中取回資料，因為是堆疊，存取都只能在堆疊頂端進行，這會影響運算能力嗎？
如果使用 a;b/c 的格式，來表示機器接受輸入 a，而且可在堆疊頂端取出 b 時，將 c 放到堆疊頂端，那麼可以識別 ab、aabb、aaabbb 的機器，可以如下構造：
為了讓機器能識別堆疊的底部，在堆疊底放入了一個 $，在這個機器中，c 是個計數用的符號，每看到一個 a 就在堆疊增加一個 c，之後開始遇到 b 時，每看到一個 b 就消去堆疊中的一個 c，直到堆疊為空，表示已經找到了相同數量的 b，這時不讀取任何輸入，直接進入第 4 個狀態（接受狀態）。
由於標示格式 a;b/c 是表示取出 b，放入 c，因此 a;c/cc 就表示取出一個 c，放回兩個 c，也就是在堆疊中增加了 c；類似地，a;$/c$ 是指取出 $ 並放回 c$，也就是在堆疊為空時，增加一個 c，而 b;c/ 表示取出 c 不放回任何東西。
圖靈機磁頭底下一定有資料可以讀取（就算是預設值空白之類，也算是一種資料），然而，這個只有堆疊的機器，可以不讀取任何輸入，只憑機器的堆疊頂端是否為 $，徑自進入第 4 個狀態，這也是一個規則，稱為自由轉移（free move），為了有別於必須有輸入的狀態轉移，上面的圖中使用了虛線來表示。
這個機器可以識別一連串的 a 之後，有同樣數量的 b，如果想進一步識別相同數量的 a 與 b 呢？也就是不管 a、b 出現的順序，只要它們數量相同就可以了，那麼可以改寫為以下：
由於順序不重要，因此只要看到 a 加入一個 c 計數，看到一個 b 消去一個 c 就行了，如果 a、b 有成對關係，這就是台可以識別對稱符號的機器，在這邊將 a、b 改成了 ( 與 )，令其看來是個識別對稱括號的機器，只是在突顯這點。
像這樣只有堆疊的機器，稱為下推自動機（PushDown Automaton），組態圖是個方便觀看狀態走向的工具，從中也可以察看到下推自動機的規則中有五個元素：
- 目前的狀態
- 讀取的字元
- 堆疊中取出的字元
- 置入堆疊的字元集合
- 進入哪個狀態
第一、第二與第五個元素，與圖靈機相同，至於第三、第四個元素，因針對堆疊結構而不同，對運算能力產生限制的，就是第三、第四個元素，因為規則描述上不再是自由存取，每次只能在堆疊頂端操作，由於無法直接存取堆疊中間的資料，若有些先前的歷史資訊持續被放入了堆疊，以後又被其他後續資料埋到了堆疊中間，想要回頭看看那些歷史資訊的話，勢必得將其上頭的資料都取出，然而，這些被取出的資料就永遠消失了（導入兩個以上的堆疊可以解決這個問題，然而，這就不單純只是個下推自動機，而像是個長度受限的圖靈機）。
因此，下推自動機能夠處理的，就只能是上下文無關（Context-free）的問題了，像是 abc、aabbcc、aaabbbccc 的識別，也就是識別一連串的 a 之後，有同樣數量的 b，接著是同樣數量的 c，下推自動機就做不到了，因為試圖識別 b 數量是否與 a 相同時，就會移去全部計數用的符號，這麼一來，要怎麼知道 c 的數量與 a 相同呢？
也許你會想要試著如先前那樣，寫個程式來模擬下推自動機的行為，以便更瞭解下推自動機，或者驗證下推自動機的規則是否正確，不過要特別小心，因為你是在通用圖靈機之下，撰寫程式以模擬下推自動機，一不小心可能會走錯路，例如不小心用到了圖靈機的能力，卻誤以為是下推自動機的運算能力達到了任務。
例如，你也許會試圖使用變數來記錄堆疊被取出的計數用字元，然後誤以為下推自動機可以識別 aaabbbccc，記得，下堆自動機的記錄狀置只有一個，就是那個堆疊，額外使用變數記錄，那你這個變數是放在哪呢？只要不是放在堆疊中，就犯規了！
如果有興趣，基於之前文件的程式碼，簡化改寫出一個下推自動機模擬程式並不難，改寫過程最重要的原則，關於機器本身必須記錄的資料，一定只能用到堆疊，如果你不確定，那就畫組態圖，如果程式辦到了，而你無法畫出對應的組態圖，有可能就是踩線了。
底下是個參考用的程式，有興趣就自行閱讀吧！
class Stack {
constructor(array) {
this.array = array;
}
push(elem) {
return new Stack([elem].concat(this.array));
}
pushAll(elems) {
return new Stack(elems.concat(this.array));
}
pop() {
return new Stack(this.array.slice(1));
}
get top() {
return this.array[0];
}
toString() {
return this.array.join(' ');
}
}
class Context {
constructor(state, stack, rejected = false) {
this.state = state;
this.stack = stack;
this.rejected = rejected;
}
isAcceptable(acceptables) {
return acceptables.includes(this.state);
}
reject() {
return new Context(this.state, this.stack, true);
}
isRejected() {
return this.rejected;
}
}
class Rule {
constructor({state, input, top, pushBacks, nextState}) {
this.state = state;
this.input = input;
this.top = top;
this.pushBacks = pushBacks;
this.nextState = nextState;
}
isApplicableTo(context, input) {
return this.state === context.state &&
this.input === input &&
this.top === context.stack.top;
}
next_context(context) {
let next_stack = context.stack.pop()
.pushAll(this.pushBacks);
return new Context(this.nextState, next_stack);
}
}
class Manual {
constructor(rules) {
this.rules = rules;
}
freeMove(context) {
let rule = this.rules.find(rule => rule.isApplicableTo(context, null));
if(rule) {
return this.freeMove(rule.next_context(context));
}
else {
return context;
}
}
next_context(context, input) {
let rule = this.rules
.find(rule => rule.isApplicableTo(context, input));
if(rule) {
let ctx = rule.next_context(context);
return this.freeMove(ctx);
}
return context.reject();
}
}
class PDA {
constructor(manual, context, acceptables) {
this.manual = manual;
this.context = context;
this.acceptables = acceptables;
}
canAccept(text) {
let manual = this.manual;
function digest(context, txt) {
if(context.isRejected() || txt.length === 0) {
return context;
}
let ctx = manual.next_context(context, txt[0]);
return digest(ctx, txt.slice(1));
}
let c = digest(this.context, text);
return !c.isRejected() && c.isAcceptable(this.acceptables) ;
}
}
// 識別對稱括號的規則手冊
let manual = new Manual([
new Rule({
state : 1,
input : '(',
top : '$',
pushBacks : ['c', '$'],
nextState : 2
}),
new Rule({
state : 2,
input : '(',
top : 'c',
pushBacks : ['c', 'c'],
nextState : 2
}),
new Rule({
state : 2,
input : ')',
top : 'c',
pushBacks : [],
nextState : 3
}),
new Rule({
state : 3,
input : ')',
top : 'c',
pushBacks : [],
nextState : 3
}),
new Rule({
state : 3,
input : null,
top : '$',
pushBacks : ['$'],
nextState : 1
})
]);
let stack = new Stack(['$']);
let context = new Context(1, stack);
let pda = new PDA(manual, context, [1]);
console.log(pda.canAccept('(())()'));