概説
編集オートマトン(automaton, 複数形は automata) は、一般的には「自動機械」「自動人形」などの意味で用いられている。
しかし、ここでは「オートマトン／オートマタ」を次のように抽象化して考えることにする。すなわち、
- ある入力(input) を与えると、
- 入力に対応する処理を自動的に実行し、
- ある適切な出力 (output) を行う
ようなデジタルシステム、それもできるだけ単純にモデル化したものだと捉える。
身近にみられる「オートマトン／オートマタ」の例として、切符の自動販売機を考えよう。
切符自動販売機に与える入力は、投入した硬貨の種類とその順序（「100円玉、100 円玉、50 円玉、10円玉…」）であり、自動販売機は投入された硬貨の合計金額を計算・記録し、その合計がある値以上になると、出力として切符と釣銭を吐き出す。
このような自動機械はすでに様々なものが存在するが、それぞれの機械は、その機械の複雑の程度によっては内部の構造が根本的に異なるかもしれない。現実の機械を抽象化して思考することによって、世に存在する自動機械を、複雑さの程度によってグルーピング／分類してみよう、というのがオートマトン論の第一歩となる。
なお、オートマトンが持つ記憶量は有限であるとする。無限に記憶することのできる自動機械は現実世界には存在しないし、あるいは、記憶量が有限であるという基本的な制限の中に縛っておいてもなお、案外多様な用途に応用できるのである。あるいは、有限の記憶量でどこまで可能であるか、その限界を探ってみるという態度もよいかもしれない。
先に種明かしをすれば、このような抽象化・モデル化されたオートマトンの分類としては、
- 有限オートマトン
- プッシュダウンオートマトン
- 線形拘束オートマトン
- チューリング機械
などが挙げられ、上から下に向かって複雑になり、それぞれの分類の複雑さの度合いは、単に「複雑さが 2 倍・100倍」というのではなく、本質的・根本的に複雑さの程度が異なるのである。
最後に挙げたチューリング機械は、「いかなる電子計算機の可能なことならばチューリング機械でも可能である」という意味で、電子計算機の基本的機能をモデル化したものと考えることができる。チューリング機械は、電子計算機の出現と同じくらいの時期が、それより少し前の 1930 年代に、イギリスの数学者チューリング（A.M.Turing, 1912-1954) により提案された。
これらのオートマトンを順を追って少しずつみていくことにしよう。