【ちゅーりんぐましん】
チューリングマシン とは？
最終更新:
💡 テープと規則で計算を考える理論モデル
アラン・チューリングが1936年の論文で示した計算の理論モデル。必要なだけ使えるテープ、記号を読み書きするヘッド、有限個の状態と規則で動き、計算できる問題やその限界を数学的に考える。
📌 このページのポイント
- 必要なだけ使えるテープ、読み書きヘッド、有限個の状態と遷移規則からなる
- 現在の状態と読んだ記号に従い、記号を書き、ヘッドを動かし、次の状態へ進む
- 万能チューリングマシンは、符号化された別のマシンと入力を読み、その動作を模倣する
- 停止問題では、あらゆるマシンと入力について停止の有無を必ず判定する手続きが存在しない
ひよこ 実際にある機械なの？
ペンギン先生 計算を考えるための抽象的なモデルだよ。記号を並べるテープを必要なだけ使えると仮定し、ヘッドが読み書きする。状態と規則の数は有限なんだ。
ひよこ 1回の動作では何をするの？
ペンギン先生 状態q0で0を読んだら、1を書き、右へ1マス動き、状態q1になる、という規則を決められるよ。図はこの1ステップの例で、すべてのマシンがこの規則を使うわけではないんだ。
ひよこ いつも1つの計算しかできない？
ペンギン先生 万能チューリングマシンなら、別のマシンの規則と入力を符号化して読み込み、その動作を模倣できるよ。プログラムをデータとして渡す考え方につながるんだ。
ひよこ 今のパソコンと同じ能力なの？
ペンギン先生 理論上の計算を比較する際は、記憶領域を必要なだけ増やせるといった仮定を置く。実物のPCはメモリーも時間も有限なので、そのまま無制限のテープを持つわけではないよ。
ひよこ 停止するかどうかも調べられる？
まとめ：ざっくりこれだけ覚えればOK！
「チューリングマシン」って出てきたら「コンピュータの理論的な原型」と思えればだいたいOK！
📖 おまけ：英語の意味
「Turing Machine」 ＝ チューリング機械
💬 考案者アラン・チューリングにちなむ呼び名だよ。実機の製品名ではなく、計算を数学的に扱うためのモデルなんだ。