Loading AI tools
アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械 ウィキペディアから
チューリングマシン (英: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である[1]。
チューリングの「計算可能数について──決定問題への応用」(1936年)において提示された[2]。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している[3]。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデルも計算可能性の理論からは同等であることが確認され、チューリング=チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。
ここでは非形式的(直感的)に述べる。理論的には形式的に述べる必要がある。
チューリングマシンには、いわゆるハードウェアに相当するものとして、
がある。
また、ソフトウェアに相当するものとして、以下がある。
この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」(内部状態)と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。
さらに、この有限オートマトンには(一般的な有限オートマトンの「受理状態」と同様な)「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である[注 2]。
実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、アルゴリズムをチューリング機械上の手続きと同一視して議論することができる(チャーチ=チューリングのテーゼ)。
数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない(停止性問題)。これはゲーデルの不完全性定理の別の表現の形とみなすことができる。
この節では、チューリングマシンを形式的(formal)に記述する。
M が言語 を認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙(recursively enumerable)あるいは計算可枚挙(computably enumerable)であるという。L と がともに帰納可枚挙であるとき、Lは帰納的(recursive)あるいは決定可能(decidable)であるという。
より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量[ないし空間計算量]t で認識するとは、M が L を認識し、かつ各 に対する の実行時間[ないし記憶領域量]が 以下であることをいう。ここで は文字列 x の長さを表す。
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数をからへの写像とし、状況の定義も適切に変更する。
言語を認識するだけでなく、からへの部分函数を計算する機械を考えることもできる。すなわち機械は、各に対しては文字列をテープに書いてから初めて受理状態へ移り、に対しては決して受理状態へ移らない。このようなが存在するとき、は部分帰納的あるいは計算可能(computable)であるという。
遷移関数において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値(すなわちその時にすべき動作)が、高々一つならば、そのチューリングマシンは「決定的」(deterministic)である。これに対し、動作が複数の場合は「非決定的」(non-deterministic)であり、受理の意味も再定義して、非決定的チューリングマシンや乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが可逆チューリングマシンである。
質問状態を加える。
遷移規則をうまく構成することで、「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン(万能チューリングマシン)」が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。(エミュレータの原理)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.