変換機
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/26 07:11 UTC 版)
言語を認識するだけでなく、 Σ ∗ {\displaystyle {\mathit {\Sigma }}^{*}} から Σ ∗ {\displaystyle {\mathit {\Sigma }}^{*}} への部分函数 f {\displaystyle f} を計算する機械を考えることもできる。すなわち機械 M {\displaystyle M} は、各 x ∈ d o m ( f ) {\displaystyle x\in \mathrm {dom} (f)} に対しては文字列 f ( x ) {\displaystyle f(x)} をテープに書いてから初めて受理状態へ移り、 x ∉ d o m ( f ) {\displaystyle x\notin \mathrm {dom} (f)} に対しては決して受理状態へ移らない。このような M {\displaystyle M} が存在するとき、 f {\displaystyle f} は部分帰納的あるいは計算可能(computable)であるという。
※この「変換機」の解説は、「チューリングマシン」の解説の一部です。
「変換機」を含む「チューリングマシン」の記事については、「チューリングマシン」の概要を参照ください。
「変換機」の例文・使い方・用例・文例
- 変換機のページへのリンク