- CMS比較.com >
- インターネット用語辞典【チューリングマシンとは？】
チューリングマシンとは？
▼チューリングマシン▼
チューリングマシン (”Turing Machine”) とは、1936年にイギリスの数学者アラン・チューリングが、「計算可能数についての決定問題への応用」で考案した仮想機械。
コンピュータや計算理論 計算を数学的に議論するための道具であり、単純化・理想化された計算機モデルであると言える。
同様の考え方はチューリングと同じ1936年にエミール・ポスト（Emil Post）もチューリングと独立に発表している。なぜそういうことを考えたかについてはポストの論文の方が明確だが、仮想機械自体に関する記述はチューリングの論文の方が詳しい。
チューリングの仮想機械は、
無限に長いテープ
その中に格納された情報を読み書きするヘッド
【情報源】Wikipedia
【引用元URL】http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
▼チューリングマシンの停止問題▼
チューリングマシンの停止問題（チューリングマシンのていしもんだい）は、プログラムの停止問題、停止性問題とも呼ばれ、次のような問題である。
あるプログラム (コンピュータ) プログラム（アルゴリズム）と入力（問題のインスタンス）が与えられたときに、そのプログラムが有限実行時間内で停止するか？
1936年、アラン・チューリングは、停止問題を解くチューリングマシンが存在しないことを示した。証明の概要は、対角線論法を使用し、そのようなチューリングマシンが存在すると仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリングマシンを構成することができるという矛盾を導き出すものである。
【情報源】Wikipedia
【引用元URL】http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3
▼「チューリングマシン」以外の用語▼
