決定的チューリングマシン
雑に理解する場合、メモリが無限にあるコンピュータだと思えばいい
GPU 積んでも、人工知能作っても、量子コンピューティングしても決定的チューリングマシンの範囲内
イメージで理解する場合
チューリングマシンは無限長のテープと有限オートマトンを持つ
以下の機能を持つ
テープ上の文字を1文字読み取る機能
テープ上に文字を1文字書き込む機能
テープを右に1つ動かす機能
テープを左に1つ動かす機能
状態を決定的に遷移させる機能
丁寧に理解する場合
チューリングマシンについて学習する
実際は数学的に厳密な定義が存在する
$ M=(Q,\Gamma,b,\Sigma,\delta,q_0,q_F)
$ \{q_0, q_F\}\subset Q
$ b\in\Gamma
$ \Sigma=\Gamma-b
$ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}
各記号の意味付け
$ M: チューリングマシン
$ Q: 状態集合
$ q_0: 初期状態
$ q_F: 受理状態
$ \Gamma: 出力字母
$ b: 空白記号
$ \Sigma: 入力字母
$ L: テープを左に動かす
$ R: テープを右に動かす
状態遷移関数がプログラム本体のようなもので、この関数を定義することでチューリングマシンの動作が決定される
入力字母がなくなり かつ 状態が受理状態になっていれば「計算が停止した」となる
入力字母がなくなって状態が受理状態でない場合は「不受理」
入力字母が一向に無くならない場合は「停止しない」