チューリングマシン

チューリングマシンは、有限の制御部と無限のテープを持つ抽象的な装置であり、アルゴリズムの直感的な概念を捉え、計算可能なものの標準的な参照モデルとして機能します。

Definition

チューリングマシンは、有限の状態集合と、セルからなる両方向無限テープで構成されます。各ステップで、ヘッドの下にある記号を読み取り、記号を書き込み、左右に移動し、遷移関数に従って状態を変化させ、受理状態または拒否状態に入ると停止します。

Scope

このトピックでは、チューリングマシンの定義と操作、構成と計算、多テープや非決定性などのバリアントにおけるモデルの堅牢性、他のあらゆるマシンをシミュレートできるユニバーサルチューリングマシン、そして自己参照と決定不能性の議論を可能にするデータとしてのマシンのエンコーディングについて扱います。

Core questions

• 単純な読み書き移動装置が、アルゴリズムの完全な概念をどのように捉えるのでしょうか？
• なぜ、モデルの多くのバリアントが全く同じ関数を計算するのでしょうか？
• ユニバーサルマシンとは何であり、その存在がなぜ重要なのでしょうか？
• マシンを文字列としてエンコードすることが、それら自身の振る舞いに関する証明をどのように可能にするのでしょうか？

Key theories

普遍性

単一のユニバーサルチューリングマシンが存在し、任意のマシンとその入力のエンコーディングが与えられると、そのマシンの計算をシミュレートします。これは、プログラム自体がデータである記憶プログラムコンピュータを予見するものです。

モデルの堅牢性

テープの追加、複数のヘッド、二次元テープ、または非決定性を加えても、計算可能な関数のクラスは変化しません。したがって、チューリングマシンは、そのような詳細に影響されない計算の概念を捉えています。

Clinical relevance

チューリングマシンは、プログラミング言語やコンピュータアーキテクチャの能力を測る尺度であり、ユニバーサルマシンは、現代のあらゆるコンピューティングの基盤となっている汎用記憶プログラムコンピュータの概念的な祖先です。

History

チューリングは、数が計算可能であることの意味を正確にし、ヒルベルトの決定問題を解決するために、1936年に自身のマシンを導入しました。格納された記述が汎用デバイスを制御するというユニバーサルマシンのアイデアは、10年後のフォン・ノイマンによる記憶プログラムコンピュータの設計に影響を与えました。

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

チューリングマシンは実際のコンピュータですか？

いいえ、それは無限のテープを持ち、速度やメモリコストを考慮しない数学的な抽象化です。その価値は概念的なものです。それは、原理的に何が計算可能であるかを正確に特定し、実際のコンピュータが実行できるあらゆるタスクを、十分なテープと時間があればチューリングマシンも実行できます。

ユニバーサルチューリングマシンが重要なのはなぜですか？

それは、ある固定されたマシンが、他のマシンの記述を入力として与えられると、そのマシンの振る舞いを実行できることを示しています。これは、ソフトウェアが各タスクのために配線を変更するのではなく、単一の解釈装置に供給されるデータである汎用プログラマブルコンピュータの理論的基盤です。