「チューリングマシン」の版間の差分
編集の要約なし |
|||
2行目: | 2行目: | ||
== 歴史 == |
== 歴史 == |
||
[[1936年]]に[[イギリス]]の数学者[[アラン・チューリング]]の論文「計算可能数について──[[決定問題]]への応用」で発表された。同様の考え方は同年に[[エミール・ポスト]] (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。 |
[[1936年]]に[[イギリス]]の数学者[[アラン・チューリング]]の論文「計算可能数について──[[決定問題]]への応用」で発表された。同様の考え方は同年に[[エミール・ポスト]] (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。 |
||
== 概要 == |
== 概要 == |
||
[[Image:Turing Machine.png|right|300px|thumb|'''チューリングマシンの模式図''' 無限に長い節からできたテープと、テープの節を読み書きするヘッドから構成されている。ヘッドは読み取った節の内容を記憶できる。]] |
[[Image:Turing Machine.png|right|300px|thumb|'''チューリングマシンの模式図''' 無限に長い節からできたテープと、テープの節を読み書きするヘッドから構成されている。ヘッドは読み取った節の内容を記憶できる。]] |
||
チューリングの仮想機械は、 |
チューリングの仮想機械は、 |
||
19行目: | 17行目: | ||
== 現実の計算との関係 == |
== 現実の計算との関係 == |
||
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、[[アルゴリズム|算法]]あるいは[[算譜]]をチューリング機械と同一視する([[チャーチ=チューリングのテーゼ]])。 |
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、[[アルゴリズム|算法]]あるいは[[算譜]]をチューリング機械と同一視する([[チャーチ=チューリングのテーゼ]])。 |
||
25行目: | 22行目: | ||
== 形式的定義 == |
== 形式的定義 == |
||
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。 |
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。 |
||
* Q は[[有限集合]]であり、その元を'''状態'''という。 |
* Q は[[有限集合]]であり、その元を'''状態'''という。 |
||
41行目: | 37行目: | ||
== 変種 == |
== 変種 == |
||
=== 細かい相違 === |
=== 細かい相違 === |
||
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。 |
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。 |
||
* 字母<math>\mathit\Gamma</math>の大きさ(それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり)。 |
* 字母<math>\mathit\Gamma</math>の大きさ(それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり)。 |
||
54行目: | 48行目: | ||
=== 変換機 === |
=== 変換機 === |
||
言語を認識するだけでなく、<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>\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>の定義を変えて非決定的にする。さらに受理の意味を変えて、[[非決定性チューリング機械]]や乱択チューリング機械が定義される。 |
<math>\delta</math>の定義を変えて非決定的にする。さらに受理の意味を変えて、[[非決定性チューリング機械]]や乱択チューリング機械が定義される。 |
||
66行目: | 58行目: | ||
== 万能チューリングマシン == |
== 万能チューリングマシン == |
||
遷移規則をうまく構成することで、驚くべきことにすべてのチューリングマシンの動作を再現するチューリングマシン('''万能チューリングマシン''')を組み立てることが可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。([[エミュレータ (コンピュータ)|エミュレータ]]の原理) |
遷移規則をうまく構成することで、驚くべきことにすべてのチューリングマシンの動作を再現するチューリングマシン('''万能チューリングマシン''')を組み立てることが可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。([[エミュレータ (コンピュータ)|エミュレータ]]の原理) |
||
<!--また全てのチューリングマシンは万能チューリングマシンであることも証明されている。すなわち究極的にはひとつのコンピュータアーキテクチャだけで事足りるということである。 |
<!--また全てのチューリングマシンは万能チューリングマシンであることも証明されている。すなわち究極的にはひとつのコンピュータアーキテクチャだけで事足りるということである。 |
||
72行目: | 63行目: | ||
しばしば誤って説明されがちであるが、万能チューリングマシンとはコンピュータで別のコンピュータをシミュレートできる原理であって、[[ノイマン型|ノイマンコンピュータ]]の原理とは無関係である。 |
しばしば誤って説明されがちであるが、万能チューリングマシンとはコンピュータで別のコンピュータをシミュレートできる原理であって、[[ノイマン型|ノイマンコンピュータ]]の原理とは無関係である。 |
||
ノイマンコンピュータとは本来のチューリングマシンのあらゆる計算を可能にする能力を生かすために、あらゆるコンピュータプログラムを入れ替え可能なストアードプログラムとして次々にメモリに入れ替えて実行させ、実際に、あらゆる計算可能性に近づける工夫である。--><!-- とりあえずコメントアウトしておくが多分チューリング完全についてわかってない奴が書いたように思う --> |
ノイマンコンピュータとは本来のチューリングマシンのあらゆる計算を可能にする能力を生かすために、あらゆるコンピュータプログラムを入れ替え可能なストアードプログラムとして次々にメモリに入れ替えて実行させ、実際に、あらゆる計算可能性に近づける工夫である。--><!-- とりあえずコメントアウトしておくが多分チューリング完全についてわかってない奴が書いたように思う --> |
||
==関連項目== |
==関連項目== |
||
{{commons|Category:Turing machine}} |
{{commons|Category:Turing machine}} |
2011年3月3日 (木) 11:49時点における版
チューリングマシン (英: Turing Machine) は計算模型のひとつで計算機を数学的に議論するための、単純化・理想化された仮想機械である。
歴史
1936年にイギリスの数学者アラン・チューリングの論文「計算可能数について──決定問題への応用」で発表された。同様の考え方は同年にエミール・ポスト (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。
概要
チューリングの仮想機械は、
- 無限に長いテープ
- その中に格納された情報を読み書きするヘッド
- 機械の内部状態を記憶するメモリ
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。
- ヘッド位置のテープに情報を書き込む
- 機械の内部状態を変える
- ヘッドを右か左に一つ移動する
上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。
現実の計算との関係
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する(チャーチ=チューリングのテーゼ)。
数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない(停止性問題)。これはゲーデルの不完全性定理の別表現とみなすことができる。
形式的定義
チューリング機械とは次のつ組である。
- Q は有限集合であり、その元を状態という。
- Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
- b は Γ の元であり、空白記号とよばれる。
- Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
- δ は Q × Γ から Q × Γ × {left, right} への写像であり、遷移函数とよばれる。δ(q, a) = (q', a', m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
- qinit は Q の元であり、初期状態とよばれる。
- qacc は Q の元であり、受理状態とよばれる。
M の状況とは、上の(片側)無限列のうち、Q の元がちょうど1度現れ、また b 以外の記号が有限回しか現れないものをいう。遷移函数 δ は、状況から状況への写像を自然に定める。M が文字列を受理するとは、状況にこの写像を有限回施すことで状況が得られることをいう。その最小回数を M の x に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。
M が言語を認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙(recursively enumerable)あるいは計算可枚挙(computably enumerable)であるという。L とがともに帰納可枚挙であるとき、Lは帰納的(recursive)あるいは決定可能(decidable)であるという。
より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量[ないし空間計算量]t で認識するとは、M が L を認識し、かつ各に対するの実行時間[ないし記憶領域量]が以下であることをいう。ここでは文字列 x の長さを表す。
変種
細かい相違
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
- 字母の大きさ(それがを含む有限集合であるかぎり)。
- 遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
- 文字列を受理するさい、テープ上の記号をすべてにする必要があるか、受理状態へ移るだけでよいか。
- テープが両方向に無限であるか、片側に終端があるか。
- さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
- テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数をからへの写像とし、状況の定義も適切に変更する。
変換機
言語を認識するだけでなく、からへの部分函数を計算する機械を考えることもできる。すなわち機械は、各に対しては文字列をテープに書いてから初めて受理状態へ移り、に対しては決して受理状態へ移らない。このようなが存在するとき、は部分帰納的あるいは計算可能(computable)であるという。
決定性と非決定性
の定義を変えて非決定的にする。さらに受理の意味を変えて、非決定性チューリング機械や乱択チューリング機械が定義される。
神託つき機械
質問状態を加える。
万能チューリングマシン
遷移規則をうまく構成することで、驚くべきことにすべてのチューリングマシンの動作を再現するチューリングマシン(万能チューリングマシン)を組み立てることが可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。(エミュレータの原理)
関連項目
外部リンク
解説
- Turing machine (英語) - スカラーペディア百科事典「チューリングマシン」の項目。
- Turing Machines (英語) - スタンフォード哲学百科事典「チューリングマシン」の項目。
- Weisstein, Eric W. "Turing Machine". mathworld.wolfram.com (英語).