アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

能力を高める

105

4

章

能力を高める

３章では、実際のコンピュータにある複雑さを取り除き、可能な限り単純な形にまでそぎ落とした、

有限オートマトンという架空の機械について調べました。そして、その機械の振る舞いについて詳しく

調べ、それが何の役に立つのかを見ました。さらに、非決定性有限オートマトンは一風変わった実行

方法を備えているにもかかわらず、従来の決定性オートマトンと同等の能力しかないことを見ました。

非決定性や自由移動といったしゃれた機能を追加しても、有限オートマトンの能力を高めることはで

きないという事実は、このような単純な機械はすべて、ある共通レベルの計算能力で頭打ちになるこ

と、そして機械の動作方法をもっと劇的に変更しない限り、そのレベルを打ち破れないことを示唆して

います。では、これらの機械にはどの程度の能力があるのでしょうか。まあ、たいしたことはないで

しょう。その応用は文字シーケンスを受理するか否かといった非常に特殊な用途に限られています

し、この限定された小さな範囲ですら、こうした機械で認識できない言語を簡単に考え出すことができ

ます。

たとえば、開き括弧と閉じ括弧からなる文字列を読んで、括弧のバランスがとれている文字列、す

なわち、閉じ括弧がその前方にある開き括弧とペアになっている文字列だけを受理する有限状態機械

の設計について考えてみましょう

†

。

この問題を解くための一般的なやり方は、現在のネストレベル数を記録しながら、1文字ずつ読んで

いくことです。開き括弧を読むとネストレベルを増や ...