「チューリングマシン」の版間の差分

編集の要約なし
 
== 歴史 ==
 
[[1936年]]に[[イギリス]]の数学者[[アラン・チューリング]]の論文「計算可能数について──[[決定問題]]への応用」で発表された。同様の考え方は同年に[[エミール・ポスト]] (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。
 
== 概要 ==
 
[[Image:Turing Machine.png|right|300px|thumb|'''チューリングマシンの模式図''' 無限に長い節からできたテープと、テープの節を読み書きするヘッドから構成されている。ヘッドは読み取った節の内容を記憶できる。]]
チューリングの仮想機械は、
 
== 現実の計算との関係 ==
 
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、[[アルゴリズム|算法]]あるいは[[算譜]]をチューリング機械と同一視する([[チャーチ=チューリングのテーゼ]])。
 
 
== 形式的定義 ==
 
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。
* Q は[[有限集合]]であり、その元を'''状態'''という。
 
== 変種 ==
 
=== 細かい相違 ===
 
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
* 字母<math>\mathit\Gamma</math>の大きさ(それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり)。
 
=== 変換機 ===
 
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分函数<math>f</math>を'''計算'''する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は'''部分帰納的'''あるいは'''[[計算可能性理論|計算可能]]'''(computable)であるという。
 
=== 決定性と非決定性 ===
 
<math>\delta</math>の定義を変えて非決定的にする。さらに受理の意味を変えて、[[非決定性チューリング機械]]や乱択チューリング機械が定義される。
 
 
== 万能チューリングマシン ==
 
遷移規則をうまく構成することで、驚くべきことにすべてのチューリングマシンの動作を再現するチューリングマシン('''万能チューリングマシン''')を組み立てることが可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。([[エミュレータ (コンピュータ)|エミュレータ]]の原理)
<!--また全てのチューリングマシンは万能チューリングマシンであることも証明されている。すなわち究極的にはひとつのコンピュータアーキテクチャだけで事足りるということである。
しばしば誤って説明されがちであるが、万能チューリングマシンとはコンピュータで別のコンピュータをシミュレートできる原理であって、[[ノイマン型|ノイマンコンピュータ]]の原理とは無関係である。
ノイマンコンピュータとは本来のチューリングマシンのあらゆる計算を可能にする能力を生かすために、あらゆるコンピュータプログラムを入れ替え可能なストアードプログラムとして次々にメモリに入れ替えて実行させ、実際に、あらゆる計算可能性に近づける工夫である。--><!-- とりあえずコメントアウトしておくが多分チューリング完全についてわかってない奴が書いたように思う -->
 
==関連項目==
{{commons|Category:Turing machine}}
匿名利用者