「チューリングマシン」の版間の差分
削除された内容 追加された内容
51行目:
言語を認識するだけでなく、<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>
=== 神託つき機械 ===
|