JavaScriptによるチューリングマシン　その1

　丸岡章氏による著作「計算理論とオートマトン言語理論」のp.148には正しい括弧を受理するチューリングマシンの例があります。ちょっと勉強がてら実装してみます。

この本ではテープの記号とマシンのヘッドを１行に並べて表示する「様相」という方法が出てきます。例えばテープの内容がABCDEで、状態qのマシンのヘッドが記号Cを読み取る状態にあるときはABqCDEと表記します。この表記を使うとチューリングマシンの計算過程は様相の時間的変化として記述されます。これでもよいのですが、慣れないうちわかりにくいと思ったので、今回の実装では ABqCDE を A|B|q->C|D|E と表記するようにしました。q->C が状態qのマシンが記号Cを読み取る様子を表しています。

具体的なアルゴリズムや処理の詳細などはぜひ丸岡章氏の素晴らしい著作を読んでいただければと思います。

プログラム
実行結果
- 例1. ((())()) は受理するか？
- 例2. ((())())) は受理するか
参考文献・参考サイト

プログラム

<html>
    <body>
        <script type="text/javascript" src="turing_machine.js"></script>
    </body>
</html>

const R = 1;
const L = -1;
const Q = ["q0","q1","q2","q3"];
// 入力アルファベット
const Sigma = [")","("];
// テープアルファベット
const Gamma = [")","(","(.","X","X.","_"];
// 遷移関数
const delta = {
    "q0":{"(":["q1","(.",R]},
    "q1":{")":["q2","X",L],"(":["q1","(",R],"X":["q1","X",R],"_":["q3","_",L]},
    "q2":{"(":["q1","X",R],"(.":["q1","X.",R],"X":["q2","X",L],"X.":["qr","",""]},
    "q3":{"(":["qr","",""],"(.":["qr","",""],"X":["q3","X",L],"X.":["qa","",""]}
};

// 開始状態
const q_s = "q0";
// 受理状態
const q_accept = "qa";
// 非受理状態
const q_reject = "qr";
// ヘッドの位置を示す変数
var current_idx = 0;
// マシンの状態
var current_q = q_s;
// テープの初期化
var tape = "((())())__".split("");
//var tape = "((())()))__".split("");

for(let i=0;i<100;i++){
    document.write(i + " : " + tape.slice(0,current_idx).join("|") + "|" + current_q +"->" 
                    + tape.slice(current_idx,tape.length).join("|") );
    document.write("<br>");
    a = tape[current_idx];
    let [new_q,new_a,d] = delta[current_q][a];
    if(new_q == q_accept){
        document.write("Accept !!!");
        break;
    }
    if(new_q == q_reject){
        document.write("Reject !!!");
        break;
    }
    tape[current_idx] = new_a;
    current_q = new_q;
    current_idx += d;
}

実行結果

教科書内で $X_\vdash, (_\vdash$ と表記されているものについてはそれぞれ「X.」「(.」と表示しています。

例1. ((())()) は受理するか？

この例では括弧がきちんと対応しているので正しい括弧です。受理するか見てみます。

0 : |q0->(|(|(|)|)|(|)|)|_|_
1 : (.|q1->(|(|)|)|(|)|)|_|_
2 : (.|(|q1->(|)|)|(|)|)|_|_
3 : (.|(|(|q1->)|)|(|)|)|_|_
4 : (.|(|q2->(|X|)|(|)|)|_|_
5 : (.|(|X|q1->X|)|(|)|)|_|_
6 : (.|(|X|X|q1->)|(|)|)|_|_
7 : (.|(|X|q2->X|X|(|)|)|_|_
8 : (.|(|q2->X|X|X|(|)|)|_|_
9 : (.|q2->(|X|X|X|(|)|)|_|_
10 : (.|X|q1->X|X|X|(|)|)|_|_
11 : (.|X|X|q1->X|X|(|)|)|_|_
12 : (.|X|X|X|q1->X|(|)|)|_|_
13 : (.|X|X|X|X|q1->(|)|)|_|_
14 : (.|X|X|X|X|(|q1->)|)|_|_
15 : (.|X|X|X|X|q2->(|X|)|_|_
16 : (.|X|X|X|X|X|q1->X|)|_|_
17 : (.|X|X|X|X|X|X|q1->)|_|_
18 : (.|X|X|X|X|X|q2->X|X|_|_
19 : (.|X|X|X|X|q2->X|X|X|_|_
20 : (.|X|X|X|q2->X|X|X|X|_|_
21 : (.|X|X|q2->X|X|X|X|X|_|_
22 : (.|X|q2->X|X|X|X|X|X|_|_
23 : (.|q2->X|X|X|X|X|X|X|_|_
24 : |q2->(.|X|X|X|X|X|X|X|_|_
25 : X.|q1->X|X|X|X|X|X|X|_|_
26 : X.|X|q1->X|X|X|X|X|X|_|_
27 : X.|X|X|q1->X|X|X|X|X|_|_
28 : X.|X|X|X|q1->X|X|X|X|_|_
29 : X.|X|X|X|X|q1->X|X|X|_|_
30 : X.|X|X|X|X|X|q1->X|X|_|_
31 : X.|X|X|X|X|X|X|q1->X|_|_
32 : X.|X|X|X|X|X|X|X|q1->_|_
33 : X.|X|X|X|X|X|X|q3->X|_|_
34 : X.|X|X|X|X|X|q3->X|X|_|_
35 : X.|X|X|X|X|q3->X|X|X|_|_
36 : X.|X|X|X|q3->X|X|X|X|_|_
37 : X.|X|X|q3->X|X|X|X|X|_|_
38 : X.|X|q3->X|X|X|X|X|X|_|_
39 : X.|q3->X|X|X|X|X|X|X|_|_
40 : |q3->X.|X|X|X|X|X|X|X|_|_
Accept !!!

受理しました。成功です。

例2. ((())())) は受理するか

次に例1の括弧の末尾に")"を加えた、正しくない括弧を受理するか確認します。

0 : |q0->(|(|(|)|)|(|)|)|)|_|_
1 : (.|q1->(|(|)|)|(|)|)|)|_|_
2 : (.|(|q1->(|)|)|(|)|)|)|_|_
3 : (.|(|(|q1->)|)|(|)|)|)|_|_
4 : (.|(|q2->(|X|)|(|)|)|)|_|_
5 : (.|(|X|q1->X|)|(|)|)|)|_|_
6 : (.|(|X|X|q1->)|(|)|)|)|_|_
7 : (.|(|X|q2->X|X|(|)|)|)|_|_
8 : (.|(|q2->X|X|X|(|)|)|)|_|_
9 : (.|q2->(|X|X|X|(|)|)|)|_|_
10 : (.|X|q1->X|X|X|(|)|)|)|_|_
11 : (.|X|X|q1->X|X|(|)|)|)|_|_
12 : (.|X|X|X|q1->X|(|)|)|)|_|_
13 : (.|X|X|X|X|q1->(|)|)|)|_|_
14 : (.|X|X|X|X|(|q1->)|)|)|_|_
15 : (.|X|X|X|X|q2->(|X|)|)|_|_
16 : (.|X|X|X|X|X|q1->X|)|)|_|_
17 : (.|X|X|X|X|X|X|q1->)|)|_|_
18 : (.|X|X|X|X|X|q2->X|X|)|_|_
19 : (.|X|X|X|X|q2->X|X|X|)|_|_
20 : (.|X|X|X|q2->X|X|X|X|)|_|_
21 : (.|X|X|q2->X|X|X|X|X|)|_|_
22 : (.|X|q2->X|X|X|X|X|X|)|_|_
23 : (.|q2->X|X|X|X|X|X|X|)|_|_
24 : |q2->(.|X|X|X|X|X|X|X|)|_|_
25 : X.|q1->X|X|X|X|X|X|X|)|_|_
26 : X.|X|q1->X|X|X|X|X|X|)|_|_
27 : X.|X|X|q1->X|X|X|X|X|)|_|_
28 : X.|X|X|X|q1->X|X|X|X|)|_|_
29 : X.|X|X|X|X|q1->X|X|X|)|_|_
30 : X.|X|X|X|X|X|q1->X|X|)|_|_
31 : X.|X|X|X|X|X|X|q1->X|)|_|_
32 : X.|X|X|X|X|X|X|X|q1->)|_|_
33 : X.|X|X|X|X|X|X|q2->X|X|_|_
34 : X.|X|X|X|X|X|q2->X|X|X|_|_
35 : X.|X|X|X|X|q2->X|X|X|X|_|_
36 : X.|X|X|X|q2->X|X|X|X|X|_|_
37 : X.|X|X|q2->X|X|X|X|X|X|_|_
38 : X.|X|q2->X|X|X|X|X|X|X|_|_
39 : X.|q2->X|X|X|X|X|X|X|X|_|_
40 : |q2->X.|X|X|X|X|X|X|X|X|_|_
Reject !!!

非受理となりました。例1のときとはマシンの状態が異なるところがポイントでしょうか。