「チューリングマシン」の版間の差分

m (ボット: 言語間リンク 50 件をウィキデータ上の d:q163310 に転記)
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分函数<math>f</math>を'''計算'''する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は'''部分帰納的'''あるいは'''[[計算可能性理論|計算可能]]'''(computable)であるという。
 
=== 決定と非決定 ===
遷移函数<math>\delta</math>の定義を変えにおい、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値(すなわちその時にすべき動作)が、高々一つならば、そのチューリングマシンは「決定的にす」(deterministic)である。さらこれ対し、動作が複数の場合は「非決定的」(non-deterministic)であり、受理の意味を変えも再定義して、[[非決定性チューリング機械マシン]]や乱択チューリング機械マシンが定義される。
 
=== 神託つき機械 ===