オートマトン

コンピュータの特徴である，

• 入力 $\Sigma$
• 出力 $\Delta$
• 状態（データ）$Q$

を単純化かつ抽象化した数学的モデルのことをオートマトン（automaton）といいます．

一般的にコンピュータを構成する3要素は，

• 計算などの処理を行うプロセッサ（processor）
• プログラムやデータを記憶するメモリ（memory）
• 入出力装置（input/output device）

と言われています．

一般的なコンピュータのプロセッサはレジスタマシン（register machine）と言われるチューリング等価（Turing equivalent #1）な計算モデルに基づいています．そして，チューリングマシンは無限に長いテープと，そのテープに書かれている記号を読みとって内部の状態を変えるオートマトンから構成されます．

オートマトンの種類

変換機械	入力列 $\{\Sigma\}$ を入力すると，出力列 $\{\Delta\}$ を出力するオートマトン
認識機械	入力列 $\{\Sigma\}$ を入力すると，その入力列 $\{\Sigma\}$ がオートマトンが定めている条件を満足しているならば「True」を，条件を満たしていないならば「False」を出力するオートマトン

---

#1：相互にチューリング還元可能（Turing reducible）なときにチューリング等価になります．

Mathematics is the language with which God has written the universe.