只能堆疊的機器

能夠自由存取的無限磁帶是很棒的東西，大幅提昇機器的運算能力，令運算能力的限制來源直指規則本身，就像〈停或不停？〉的停機問題，打造不出這種機器的限制來源就是規則本身，規則是運算最根本的重複，也就是某種形式的規律與不變，然而也是停止問題中矛盾的開端。

運算能力的限制

可以從另一個角度來看停止問題的導證過程，過程中其實在談的就是，若存在著可判斷停止的 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('(())()'));