蒼い影

ギリシア語のautmatosからきたことばといわれる。

古くは、人や動物の動きをまねする装置のことで、やがてロボットということばで置き換えられた。

現在オートマトンは、自動機械の抽象的モデルとして、情報科学の一つの研究対象をさしている。

オートマトンの素材としては、思考上の計算機としてのチューリング機械、神経回路網の数学的モデル、順序回路の抽象化としての順序機械の理論などがあった。

オートマトンでは、時間は0、1、2、……、t、……と不連続に刻まれ、各瞬間ｔにおいて、有限個の内部状態のどれかをとる。

有限個の内部状態のなかには、一つの初期状態と、いくつかの最終状態があり、初期状態で動き始め、止まるのは最終状態である。

チューリング機械は、升目にくぎられた、左端をもつが右方向にいくらでも長く伸びているテープと、本体と、テープ上に記号を書いたり消したり読み取ったりするヘッドという部分からなっている。

この升目一つには、一つの記号が書き込めるものとする。

それぞれのチューリング機械では、現在の内部状態と、見ている記号によって、次の瞬間における動作と内部状態が決まっている。

動作には、現在見ている記号を他の記号に書き換える、ヘッドを右、あるいは左に升目一つ分だけ動かす、という三つがある。

テープ上に、左端から有限の文字列が書かれていて、機械がこの文字列を、初期状態で左端を見、定められた規則に従って順次内部状態を変えながら三つの動作のどれかを行い、最終状態に到達すれば、最初にテープ上に書かれた文字列は、この機械によって受理されたという。

チューリング機械は、所要時間と記憶容量になんらの制限を置かず、電子計算機の忠実なモデルとはいえない。

そこで、時間と空間とに制限を置き、より忠実なモデルとして考えられたのが有限オートマトンあるいは単にオートマトンといわれるものである。

update:2010年03月17日