# チューリングマシン ## 定義 チューリングマシン（Turing machine）とは、Alan Turing が1936年に導入した、計算の概念を数学的に形式化するための仮想的な計算機械モデルである。無限の長さを持つマス目に区切られたテープ、テープ上の記号を読み書きし左右に移動できるヘッド、および有限個の内部状態（m-configuration）と遷移規則から構成される。任意のアルゴリズムによって実行可能な計算はチューリングマシンによって模倣可能であるという主張は「チャーチ＝チューリングのテーゼ」として広く受け入れられている。 ## 未解決の問い - 物理的実世界における計算可能性（量子計算や超計算など）は、古典的チューリングマシンの枠組みを真に拡張しうるか（拡張チャーチ＝チューリングのテーゼの妥当性）。 - 神経回路網モデル（リカレントニューラルネットや Neural Turing Machine など）におけるチューリング完全性の実用的な実現条件と学習可能性の限界。 ## 未編纂の観察 - Alan Turingの原論文(1936)は、人間の計算プロセスの有限性（有限の記憶・識別限界）から機械モデルを導出し、他のマシンの動作記述を入力として実行する「普遍チューリングマシン（Universal Machine）」を構成して、現代の蓄積プログラム型コンピュータの理論モデルを確立した(Source: [[@1936__LMS__On Computable Numbers, with an Application to the Entscheidungsproblem]])。 ## 関連 - ソース: [[@1936__LMS__On Computable Numbers, with an Application to the Entscheidungsproblem]] - 人物: [[Alan Turing]] - 概念: [[停止性問題]] ## 出典 - [[@1936__LMS__On Computable Numbers, with an Application to the Entscheidungsproblem]]