Turing 機械は、現在のプログラミング環境と比較すると単純で何にもできな い感がありますが、実際の計算能力はどれくらいなのか、いろいろプログラム を作って調べましょう。
文字列が与えられた時、左から読んでも右から読んでも同じものを palindrome(回文) と言います。 これを検出する Turing 機械のプログラムを考えましょう。
なお、これはアルファベットΣから作られる語全体 Σ* に対して、回文となる語は部分集合になるので、 その部分集合は「回文言語」と呼べます。 そして、回文かどうかを調べると言うことはこの言語の判定問題となります。
簡単のためにアルファベットは 0 と 1 のみを考えます。
初めに、2 本のテープを持つ場合のプログラムを考えましょう。 入力はテープ1に書かれているとします。 この場合は次のようにすれば検出できます。
これをプログラムで書くと次のようになります。
start: if head1=├ and head2=* then write ├ to tape1; write ├ to tape2; move head1 to right; move head2 to right; goto l0; l0: if head1=0 and head2=* then write 0 to tape1; write 0 to tape2; move head1 to right; move head2 to right; goto l0; l0: if head1=1 and head2=* then write 1 to tape1; write 1 to tape2; move head1 to right; move head2 to right; goto l0; l0: if head1=┤ and head2=* then write ┤ to tape1; write ┤ to tape2; stay head1; move head2 to left; goto l1; l1: if head1=┤ and head2=0 then write ┤ to tape1; write 0 to tape2; stay head1; move head2 to left; goto l1; l1: if head1=┤ and head2=1 then write ┤ to tape1; write 1 to tape2; stay head1; move head2 to left; goto l1; l1: if head1=┤ and head2=├ then write ┤ to tape1; write ├ to tape2; move head1 to left; move head2 to right; goto l2; l2: if head1=0 and head2=0 then write 0 to tape1; write 0 to tape2; move haed1 to left; move head2 to right; goto l2; l2: if head1=1 and head2=1 then write 1 to tape1; write 1 to tape2; move haed1 to left; move head2 to right; goto l2; l2: if head1=├ and head2=┤ then write ├ to tape1; write ┤ to tape2; stay haed1; stay head2; goto a; a: accept;
'*' は任意の文字の意味。実際のプログラミングでは許される記号全てが当て はまるように、全ての記号に対して同じ行のプログラムを書く。 また、この if 文に該当しない場合はすべて reject する。
Palindrome を 1 テープ Turing 機械で判定するには次のようにします。
ある文字列が Palindrome である場合、両端から文字列を見るとそれぞれが等
しくなっています。
そこで、両端から順番に読むことを考えます。
以上をまとめてプログラムを書くと次のようになります。
start: if head=├ then write ├ to tape; move head to right; goto l2; l2: if head=0 then write ├ to tape; move head to right; goto l20; l2: if head=1 then write ├ to tape; move head to right; goto l21; l2: if head=┤ then write ┤ to tape; stay head; goto a; l20: if head=0 then write 0 to tape; move head to right; goto l20; l20: if head=1 then write 1 to tape; move head to right; goto l20; l20: if head=┤ then write ┤ to tape; move head to left; goto l30; l30: if head=0 then write ┤ to tape; move head to left; goto l4; l30: if head=1 then write 1 to tape; stay head; goto r; l30: if head=├ then write ├ to tape; stay head; goto a; l4: if head=0 then write 0 to tape; move head to left; goto l4; l4: if head=1 then write 1 to tape; move head to left; goto l4; l4: if head=├ then write ├ to tape; move head to right; goto l2; a: accept; r: reject; l21: if head=0 then write 0 to tape; move head to right; goto l21; l21: if head=1 then write 1 to tape; move head to right; goto l21; l21: if head=┤ then write ┤ to tape; move head to left; goto l31; l31: if head=0 then write 0 to tape; stay head; goto r; l31: if head=1 then write ┤ to tape; move head to left; goto l4; l31: if head=├ then write ├ to tape; stay head; goto a;
カッコが閉じているかどうかをチェックすることを考えましょう。 アルファベットとしてΣ={(,)} とすると閉じているカッコで作ら れる語は言語になります。これをカッコ言語と言うことにしましょう。
2-テープ Turing 機械では簡単に作ることができます。 入力はテープ1に与えられるとします。
1-テープ Turing 機械では、対になっているカッコを順番に消していくことに より判定させます。 消し終えたカッコは別の記号(たとえば + とかに)置き換えます。 そして、 (++++) というような表現を発見したら ++++++ と書き換えるように します。 そして、全ての入力が + で書き換えたら受理します。
ある語wに対して w#wと同じ語が繰り返す 言語を考えます(# は区切り記号)。 たとえば「あ#あ」「あい#あい」「あいうえお#あいうえお」などというよう な語がこの言語に含まれます。
ある語wに対して wwと同じ語が繰り返す言語を考えま す。 たとえば「ああ」「あいあい」「あいうえおあいうえお」などというような語 がこの言語に含まれます。
次週は計算量理論についてお話します。