決定的と非決定的
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/26 07:11 UTC 版)
「チューリングマシン」の記事における「決定的と非決定的」の解説
遷移関数 δ {\displaystyle \delta } において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値（すなわちその時にすべき動作）が、高々一つならば、そのチューリングマシンは「決定的」（deterministic）である。これに対し、動作が複数の場合は「非決定的」（non-deterministic）であり、受理の意味も再定義して、非決定的チューリングマシンや乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが可逆チューリングマシンである。
※この「決定的と非決定的」の解説は、「チューリングマシン」の解説の一部です。
「決定的と非決定的」を含む「チューリングマシン」の記事については、「チューリングマシン」の概要を参照ください。
ウィキペディア小見出し辞書の「決定的と非決定的」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 決定的と非決定的のページへのリンク
