只能堆疊的機器

December 16, 2021

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

運算能力的限制

可以從另一個角度來看停止問題的導證過程,過程中其實在談的就是,若存在著可判斷停止的 A 程式(規則),必然存在著該程式判斷不了的 B 程式,A 程式必須改寫自身規則來判斷 B 程式可否停止,然而這又會存在著一個 C 程式,改寫自身後的 A 程式無法判斷的,這時 A 程式又得改寫自身來判斷 C 程式…

然而程式(規則)就是某種形式的規律,寫好的程式內容就不會變化,不斷變化、沒有規律的東西無法寫成程式。

能夠自由存取的無限磁帶,令機器的運算能力的限制來源直指規則本身,也就因此才會令已知的可行方式,像是使用雙磁帶、多維磁帶等,試圖昇級圖靈機設備來增強運算能力都沒能成功。

然而,設備確實會影響機器的運算能力,畢竟規則中就不能以該設備來進行描述,例如,若磁帶並非有限,那麼能做到的運算勢必會受到限制,畢竟能記憶的東西變少了,運算過程中若是捨棄了磁帶上某些資料,那些資料就完全消失,再也拿不回來了。

當然,現代電腦也並沒有無限多的記憶體,只不過多到多半不會用完(反而是比較擔心在管理記憶體本身資料上,能不能更快更有效率的問題),以至於許多開發者比較不會意識到記憶體有限帶來的運算能力問題。

磁帶換成堆疊

那麼,如果磁帶不再是能自由存取呢?例如,將磁帶換成一個堆疊,資料會被放到堆疊,或者從堆疊中取回資料,因為是堆疊,存取都只能在堆疊頂端進行,這會影響運算能力嗎?

如果使用 a;b/c 的格式,來表示機器接受輸入 a,而且可在堆疊頂端取出 b 時,將 c 放到堆疊頂端,那麼可以識別 abaabbaaabbb 的機器,可以如下構造:

只能堆疊的機器

為了讓機器能識別堆疊的底部,在堆疊底放入了一個 $,在這個機器中,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,如果想進一步識別相同數量的 ab 呢?也就是不管 ab 出現的順序,只要它們數量相同就可以了,那麼可以改寫為以下:

只能堆疊的機器

由於順序不重要,因此只要看到 a 加入一個 c 計數,看到一個 b 消去一個 c 就行了,如果 ab 有成對關係,這就是台可以識別對稱符號的機器,在這邊將 ab 改成了 (),令其看來是個識別對稱括號的機器,只是在突顯這點。

下推自動機

像這樣只有堆疊的機器,稱為下推自動機(PushDown Automaton),組態圖是個方便觀看狀態走向的工具,從中也可以察看到下推自動機的規則中有五個元素:

  • 目前的狀態
  • 讀取的字元
  • 堆疊中取出的字元
  • 置入堆疊的字元集合
  • 進入哪個狀態

第一、第二與第五個元素,與圖靈機相同,至於第三、第四個元素,因針對堆疊結構而不同,對運算能力產生限制的,就是第三、第四個元素,因為規則描述上不再是自由存取,每次只能在堆疊頂端操作,由於無法直接存取堆疊中間的資料,若有些先前的歷史資訊持續被放入了堆疊,以後又被其他後續資料埋到了堆疊中間,想要回頭看看那些歷史資訊的話,勢必得將其上頭的資料都取出,然而,這些被取出的資料就永遠消失了(導入兩個以上的堆疊可以解決這個問題,然而,這就不單純只是個下推自動機,而像是個長度受限的圖靈機)。

因此,下推自動機能夠處理的,就只能是上下文無關(Context-free)的問題了,像是 abcaabbccaaabbbccc 的識別,也就是識別一連串的 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('(())()'));