## マシンの構成要素 - テープ：記憶装置となる無限長のテープ。セルに分割されており、セルはアドレスをもつ。 - 記号： - ヘッド：セルの記号を読み書きできる - 有限状態表 ある文字列を入力として受け付け，出力として「受理状態に入って停止」または「拒否状態に入って停止」を吐き出す部分関数 --- [Turing machine - Wikipedia](https://en.wikipedia.org/wiki/Turing_machine) チューリング機械は計算の数学的モデルであり、ルール表に従ってテープ上のシンボルを操作する抽象的な機械を定義する。 モデルは単純であるが、任意のコンピュータアルゴリズムがあれば、そのアルゴリズムの論理をシミュレートできるチューリング機械が構築可能である。 この機械は、「セル」に分割された無限のメモリテープの上で動作する。 機械は「ヘッド」をセルの上に置き、そこにある記号を「読み取り」または「スキャン」していく。そして、そのシンボルと、ユーザーが指定した命令の「有限の表」における機械自身の現在の状態に基づいて、機械はまずシンボル（例えば。を書き込み（記号の消去や書き込みを行わないモデルもある）、次にテープを1セル左または右に動かし（動かさないモデルもあるし、ヘッドを動かすモデルもある）、観測した記号とテーブル内の機械自身の状態に基づいて、別の命令に進むか計算を停止させる。 チューリング機械は1936年にアラン・チューリングによって発明され、彼はこれを「a-machine」（自動機械）と呼んだ。 このモデルによって、チューリングは2つの質問に否定的に答えることができた。 - テープ上の任意の機械が「循環」しているかどうか（例えば、フリーズしたり、計算タスクを継続できなかったり）を判断できる機械が存在するか？ - そのテープ上の任意の機械が与えられた記号を印刷したことがあるかどうかを決定できる機械は存在するか？ このように、任意の計算が可能な非常に単純な装置の数学的記述を提供することによって、彼は計算一般に関する性質、特にEntscheidungsproblem（「決定問題」）の計算不可能性を証明することができたのである。 チューリング機械は任意の計算を表現することができるが、その最小限の設計のため、実際の計算には適さない。現実のコンピュータはチューリング機械とは異なり、ランダムアクセスメモリを使用した異なる設計に基づいている。 ### Overview チューリング完全性とは、ある命令体系がチューリング機械をシミュレートする能力である。チューリング完全なプログラミング言語は、理論的にはコンピュータが達成できるすべてのタスクを表現することができる。有限メモリの制限を無視すれば、ほとんどすべてのプログラミング言語がチューリング完全である。 チューリング機械は、コンピュータが行うすべてのデータ操作を制御する中央処理装置（CPU）の一般的な例であり、正規の機械はデータを格納するためにシーケンシャルメモリを使用します。具体的には、アルファベットの有効な文字列の任意の部分集合を列挙できる機械（オートマトン）であり、これらの文字列は再帰的に列挙可能な集合の一部である。チューリング機械は無限長のテープを持ち、その上で読み取りと書き込みの操作を行うことができる。 ブラックボックスと仮定すると、チューリング機械は、与えられたプログラムによって、最終的に部分集合の中のある特定の文字列を列挙できるかどうかを知ることはできない。これは、ハルティング問題が解けないためであり、計算機の理論的限界に大きな影響を与える。 チューリングマシンは無制限の文法を処理することができ、それはさらに、一階論理を無限に頑強に評価することができることを意味している。このことは、ラムダ計算によって有名に示されている。 他のあらゆるチューリング機械をシミュレートできるチューリング機械は、普遍チューリング機械（UTM、または単に普遍機械）と呼ばれる。チャーチは、ラムダ計算の研究がチューリングの研究と結びつき、「チャーチ・チューリング論文」として知られる計算の形式的理論に発展した。この論文では、チューリング機械が論理学や数学における有効な方法の非公式な概念を実際に捉えており、アルゴリズムや「機械的手順」の正確な定義を提供していると述べている。チューリング機械の抽象的な性質を研究することで、コンピュータ科学や複雑性理論に多くの知見がもたらされる。 --- [チューリングマシンの定義とそれに関連する話 | 高校数学の美しい物語](https://manabitimes.jp/math/2128)