チューリングマシンとは、1936年にアラン・チューリングが提唱した、計算とは何かを数学的に定義するための仮想的な計算モデルです。無限に続くテープと読み書きヘッド、状態遷移規則から構成され、現代のコンピュータの理論的基礎となっています。アルゴリズムで解決可能な問題の限界を示す計算可能性理論において中心的な役割を果たします。
チューリングマシンとは
チューリングマシンとは、計算の手順（アルゴリズム）やコンピュータが実行できる処理の限界を数学的に厳密に定義するために考案された仮想的な計算機モデルです。
詳しく解説
1936年に数学者アラン・チューリングによって提案されたこのモデルは、区切られたマス目を持つ無限のテープ、テープ上の記号を読み書きするヘッド、内部状態、そして状態と記号に応じた行動を決める遷移規則（プログラム）から構成されます。物理的に実在するハードウェアではなく、どのような処理が計算可能であるかという原理を解明するための思考実験です。プログラム自体をデータとしてテープに記録して実行する汎用チューリングマシンの概念は、現代のソフトウェアで動作するコンピュータの設計思想に決定的な影響を与え、人工知能や計算可能性理論の基盤を築きました。
具体例・使われ方
抽象的な概念であるため、テープを「無限の長さを持つノート」、ヘッドを「ペンを持った作業者」、状態遷移規則を「マニュアル」と見なすことでイメージできます。作業者がマニュアルに従ってノートの文字を書き換えたりページをめくったりする一連の動作が、コンピュータによるプログラム実行に相当します。このシンプルな仕組みにより、あらゆる複雑なアルゴリズムの計算プロセスを再現できます。
似た用語との違い
現代の一般的なパソコンなどの「ノイマン型コンピュータ」は、チューリングマシンの理論を物理的な電子回路として実用化したハードウェア構成です。また、人間のような知能を持つかを判定する対話実験である「チューリングテスト」は同じアラン・チューリングが提唱した別概念であり、チューリングマシンは計算の理論モデルを指す点で明確に異なります。
注意点
チューリングマシンは理論上のモデルであり、無限のテープを必要とするため現実の物理装置として完全に作成することはできません。また、原理的にどんなに高性能なコンピュータであっても解決できない問題（例えばプログラムが永遠に止まらないか判定する停止性問題）が存在することを示すものであり、すべての問題が計算可能になるわけではない点に注意が必要です。