チューリングマシン - Wikipediaチューリングの「計算可能数について──決定問題への応用」（1936年）において提示された[2]。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している[3]。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデルも計算可能性の理論からは同等であることが確認され、チューリング＝チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。 ここでは非形式的（直感的）に述べる。理論的には形式的に述べる必要がある。 チューリングマシンには、いわゆるハードウェアに相当するものとして、 その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる[注 1]）とする テープに記号を読み書きするヘッド ヘッドによる読み書きと、テープの左右へのシークを
