チューリングマシンの能力
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/17 08:19 UTC 版)
「計算可能性理論」の記事における「チューリングマシンの能力」の解説
チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語（例えば素数の集合からなる言語）も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。 チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え（言語と入力の判定）を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。 チューリングマシンは非常に強力な計算モデルである。チューリングマシンの定義を修正してより強力なモデルを作ろうとしても失敗する。例えば、1次元だったテープを2次元や3次元に拡張したチューリングマシンや、複数のテープを持つチューリングマシンなどが考えられるが、いずれも1次元の1個のテープを持つチューリングマシンでシミュレート可能であることが判っている。つまり、それらのモデルの能力は通常のチューリングマシンと同じである。実際、チャーチ＝チューリングのテーゼでは、チューリングマシンで判定できない言語を判定可能な計算モデルはないと推定されている。様々な人々がチューリングマシンよりも強力だという計算モデルを提案してきた。しかし、それらは非現実的であるか不合理である（下記参照）。 従ってチューリングマシンは計算可能性の限界に関する広範囲な問題を解析する強力な手法である。そこで次の疑問が生まれる。「帰納的可算だが帰納でない言語はあるのか？」である。また、「帰納的可算でもない言語はあるのか？」という疑問も生まれる。
※この「チューリングマシンの能力」の解説は、「計算可能性理論」の解説の一部です。
「チューリングマシンの能力」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。
- チューリングマシンの能力のページへのリンク
