オートマトン

コンピュータの特徴である,を単純化かつ抽象化した数学的モデルのことをオートマトン(automaton)といいます.

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

と言われています.

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

オートマトンの種類

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

#1:相互にチューリング還元可能(Turing reducible)なときにチューリング等価になります.

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 言語 反射律 reflexivity rule 真偽値 truth value 代数的閉体 algebraic closed field 言語 language