第 2 回 Turing 機械のプログラミング

本日の内容

• 2-1. Palindrome
• 2-2. カッコ言語
• 2-3. 演習
• 2-4. 次週の予告

Turing 機械は、現在のプログラミング環境と比較すると単純で何にもできな い感がありますが、実際の計算能力はどれくらいなのか、いろいろプログラム を作って調べましょう。

2-1. Palindrome

文字列が与えられた時、左から読んでも右から読んでも同じものを palindrome(回文) と言います。 これを検出する Turing 機械のプログラムを考えましょう。

なお、これはアルファベットΣから作られる語全体 Σ^* に対して、回文となる語は部分集合になるので、 その部分集合は「回文言語」と呼べます。 そして、回文かどうかを調べると言うことはこの言語の判定問題となります。

簡単のためにアルファベットは 0 と 1 のみを考えます。

k-テープ Turing 機械

初めに、2 本のテープを持つ場合のプログラムを考えましょう。 入力はテープ1に書かれているとします。 この場合は次のようにすれば検出できます。

1. 初期状態
   
2. 入力を読んでいき、テープ2に全て入力をコピーする
   
3. テープ2のヘッドを先頭に戻す
   
4. テープ1を右、テープ2を左から読んでいき、内容が全て一致したら accept 、どこかで異なれば reject する。
   

これをプログラムで書くと次のようになります。

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 する。

1-テープ Turing 機械

Palindrome を 1 テープ Turing 機械で判定するには次のようにします。 ある文字列が Palindrome である場合、両端から文字列を見るとそれぞれが等 しくなっています。

そこで、両端から順番に読むことを考えます。

1. ├ が書いてあったら一つ右にヘッドを進める。
2. 左端としてヘッドの位置の記号を読む。読んだ記号が 0 か 1 でラベルを 変える。 読んだ記号の位置には├ を書く
3. ┤を読むまで右にヘッドを進める
4. 一つヘッドを左に戻して、書いてある記号と左端の記号が一致しているか を調べる。一致してなければ reject。 一致していたらヘッドの位置に┤を書き、├を見つけるまで左にヘッドを進め る。
5. 終了条件を考えると、最終的に「(1)├┤」「(2)├0┤」「(3)├1┤」の3 つのパターンが Palindrome として認識できれば良い。 (1) は step 2 で┤を読んだら accept すれば良い。 (2),(3) は step 4 で├ を読んだら accept すれば良い。

以上をまとめてプログラムを書くと次のようになります。

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;

補足: Palindrome はオートマトンでは解けない

Turing 機械では 1 テープであっても Palindrome は解けますが、オートマト ンでは解くことができません。 これを証明します。

証明

一般性を失わず、アルファベットを $\Sigma =\left\{01\right\}$ と限定します。 このアルファベット上の Palindrome を解くオートマトンを M とし、状態数 は n と仮定し、背理法により矛盾を導きます。 さて、ここで、 s=1...101...1 という 1 が n+1 個続いてから 0 が来て、さらに 1 が n+1 個続く文字列を考えます。 これは Palindrome ですから、 M は s を受理します。 この文字列を M が読み込むときを考えます。 読み込みながら M は状態遷移を行います。 ここで M は状態数 n なので、文字列の前半部分の長さが n+1 の部分で、ある状 態 q は少なくとも 2 回現れます。 最初から i 番目の入力と j 番目の入力で状態 q になったとします(初期状 態も考慮するので i=0...n)。

この時、1 が n-j+i+1 個続いた後、0 が来て、その後 1 が n+1 個続く文字 列 t を考えます。 すると、 M がこの文字列を読み込んでいくと i 番目の入力で状態 q に入り ます。 ところが、そこで、 j+1 番目の入力と同じ入力になりますので、前半部分の 1 が n+1 個続く文字列と同様の計算を行うことになります。 したがって、 M は t を受理します。 しかし、 t は Palindrome ではありません。 つまり矛盾が生じます。したがって、 Palindrome を受理するオートマトンが 存在するという仮定は誤りだったことがわかります。

2-2. カッコ言語

カッコが閉じているかどうかをチェックすることを考えましょう。 アルファベットとしてΣ={(,)} とすると閉じているカッコで作ら れる語は言語になります。これをカッコ言語と言うことにしましょう。

k-テープ Turing 機械

2-テープ Turing 機械では簡単に作ることができます。 入力はテープ1に与えられるとします。

1. 入力を1文字読み、 ( を読んだら、テープ2 にそれを書き、ヘッドを一つ右 に進めます。
2. 入力を1文字読み、 ) を読んだら、テープ2 のヘッドを左に戻し、( が書 いてあったらそれを消します。もし ( が書いてなかったら reject します。
3. 入力が終った時、テープ 2 に何も書いてなければ accept します。

1-テープ Turing 機械

1-テープ Turing 機械では、対になっているカッコを順番に消していくことに より判定させます。 消し終えたカッコは別の記号(たとえば + とかに)置き換えます。 そして、 (++++) というような表現を発見したら ++++++ と書き換えるように します。 そして、全ての入力が + で書き換えたら受理します。

1. 入力を左から右へ順に見ていき、 ) を探します。
2. ) を発見したら + に置き換え、 ( を左へ探します。
3. )に当たらずに( を発見したら + に置き換え、 step 1 に進みます。
4. このように進めていくと一番左の ) から順に消えていくことになります。 最終的に入力が終了したら、ヘッドを左に進め、消し残しがなければ accept します。

2-3. 演習

演習2-1

ある語wに対して w#wと同じ語が繰り返す 言語を考えます(# は区切り記号)。 たとえば「あ#あ」「あい#あい」「あいうえお#あいうえお」などというよう な語がこの言語に含まれます。

1. この言語を判定するようなプログラムを好きなプログラミング言語で書き なさい。
2. この言語を判定する k テープの Turing 機械を作りなさい。
3. この言語を判定する 1 テープの Turing 機械を作りなさい。

演習2-2

ある語wに対して wwと同じ語が繰り返す言語を考えま す。 たとえば「ああ」「あいあい」「あいうえおあいうえお」などというような語 がこの言語に含まれます。

1. この言語を判定するようなプログラムを好きなプログラミング言語で書き なさい。
2. この言語を判定する k テープの Turing 機械を作りなさい。
3. この言語を判定する 1 テープの Turing 機械を作りなさい。

演習2-3

カッコ言語がオートマトンで受理できないことを証明しなさい。

2-4. 次週の予告

次週は計算量理論についてお話します。