出典: チューリングマシン 『通信用語の基礎知識』 更新年月日 2010/06/17,URL: https://www.wdic.org/ イギリスの数学者、アラン・マティソン・チューリングが1936(昭和11)年に発表した論文「計算可能数についての決定問題への応用」に書かれている仮想機械(計算機模型)のこと。 [概要] チューリングマシンはすなわち、計算機を数学的に検証、議論する上で必要となる、理想化、単純化された仮想的な計算機である。 この理論では、無限に長いテープと、そのテープに情報を読み書きするヘッドとを持った、いくつかの簡単な基本操作によって動く機械が想定されており、その機械の有限回の操作で数学の形式体系と等価な働きをすることを導いた。 [特徴] つまりチューリングマシンは、少なくとも次のような装置を持つ。 1. 無限に長いテープ 2. そのテープに情報を読み書きするヘッド 3. 計算機内の状態を保持するメモリー そして、計算機内の状態と、ヘッドで読み取った情報の組み合わせに応じて、次のいずれかの動作を行なう。 ● ヘッドの位置の情報を読み取る ● ヘッドの位置に情報を書き込む ● 計算機内の状態を変更する ● ヘッドを左右のいずれかに一つ分移動する 以上の動作を、計算機内の状態が停止になるまで繰り返して実行する。 [電子計算機] チャーチの定立 現在使われている電子計算機(コンピューター)、つまりノイマン型電子計算機は、理論的にはチューリングマシンの原理に準じていると言える。 チューリングマシンが持つ記憶媒体の容量は無限なのに対して現実の計算機のそれは有限ではあるが、理論上はチューリングマシンが解ける問題と、計算機が解ける問題はほぼ同等である、とされている。これはチャーチの定立(Charch's thesis、チャーチのテーゼ)という考えによる。 |
出典: チューリングマシン 『フリー百科事典 ウィキペディア日本語版(Wikipedia)』 最終更新 2017年7月25日 (火) 07:25 UTC、URL: https://ja.wikipedia.org/ チューリングマシン (英: Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。 [概要] チューリングの仮想機械は、1.無限に長いテープ 2.その中に格納された情報を読み書きするヘッド 3.機械の内部状態を記憶するメモリで構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。 ● ヘッド位置のテープに情報を書き込む ● 機械の内部状態を変える ● ヘッドを右か左に一つ移動する 上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。 ・・・ |
同義語・類義語 | 関連語・その他 |
---|---|
Turing Machine | Turing |
チューリング・マシン | チューリング |
チューリングマシン | アラン・チューリング |
チューリング機械 | Alan Mathison Turing |
仮想機械 | アラン・マティソン・チューリング |
かそう きかい | ・ |
計算模型 | Emil Post |
けいさん もけい | エミール・ポスト |
・ | |
計算可能数 | |
更新日:2024年 3月29日 |