|
|
=== 決定的と非決定的 ===
遷移函関数<math>\delta</math>において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値(すなわちその時にすべき動作)が、高々一つならば、そのチューリングマシンは「決定的」(deterministic)である。これに対し、動作が複数の場合は「非決定的」(non-deterministic)であり、受理の意味も再定義して、[[非決定性チューリングマシン]]や乱択チューリングマシンが定義される。
=== 神託つき機械 ===
|