Turing machine

turing machineは、物理的な機械を指すのではなく、計算可能性という概念を数学的に定義するための思考実験上のモデルです。無限に長いテープと、その上の記号を読み書きするヘッド、そして状態遷移表という極めてシンプルな構成でありながら、あらゆるアルゴリズムをシミュレートできる能力を持つことが証明されています。

計算理論における重要性

このモデルの最大の意義は、computable（計算可能）であることの定義を明確にした点にあります。ある問題がturing machineで解けるのであれば、それは理論的に計算可能であると見なされます。これは現代のコンピューターが動作する論理的な基盤となっており、プログラムの限界や、ある問題が原理的に解決不可能であること（停止問題など）を証明するための不可欠な道具となっています。

実機との概念的な違い

現代のコンピューターやノートパソコンは、このturing machineの概念を物理的に実装したものです。しかし、実際のハードウェアにはメモリ容量の限界があるため、厳密にはturing machineが前提とする無限のテープは存在しません。そのため、理論上のturing machineは理想的な計算能力を追求するモデルであり、現実のコンピューターはそれを近似した限定的な実装であるという区別が必要です。