チューリング完全

チューリング完全とは

チューリング完全（英語: Turing-complete）は、計算理論において特定の計算モデルが万能チューリングマシンと同等の計算能力を持つことを示す概念です。この概念は、計算可能な関数がどのような計算モデルによって実行できるかを理解するための基盤となります。特に、あるモデルがチューリング完全であれば、任意の計算可能な関数を実行できることが保障されます。

チューリング完全性の基準

チャーチ＝チューリングのテーゼによれば、計算可能関数はチューリング完全な計算モデルによって計算できます。一般的に、さまざまなプログラミング言語はこの基準を満たすものが多く、例えば、見た目は単純でも実際にはチューリング完全である言語として、Lazy KやBrainfuckなどが挙げられます。特筆すべきは、スティーブン・ウルフラムが提唱した2状態3記号のチューリングマシンであり、これはその単純さにも関わらずチューリング完全であることが示されています。

チューリング完全な計算モデルの例

チューリングマシン以外にも、ラムダ計算やμ再帰関数、マルコフアルゴリズムなどがチューリング完全な計算モデルとして知られています。特にラムダ計算は、Yコンビネータを利用することで再帰を可能にし、ループの機能を持つ点が重要です。

また、計算可能性理論の中で、チューリング完全性に関する問題は非常に重要で、計算複雑性理論との関連も深いです。ただし、注目すべきは計算時間やメモリの使用量など、計算の効率に関する問題はこの概念には含まれません。

停止性問題

チューリングマシンの性質には停止性問題が含まれます。これは特定の計算が必ずしも完了するわけではないことを示しています。特に、ループに入って計算が止まらないケースがあり、これにより計算が終わるかどうかを決定する方法が存在しないという点が停止性問題の核心です。この問題の存在は、全ての計算可能性に対する限界を示しています。

たとえば、「特定の条件を満たす自然数は存在しない」といった数学的命題に対するプログラムを考えると、全てのコンピュータプログラムに対して停止条件を確定できるなら、このプログラムの停止を判断することで、その数学的問題を解決できてしまうことになります。したがって、停止性問題の否定的な結論は、自明な結果であると言えます。

実例

チューリング完全性に関する具体例として、Rule 110が挙げられます。これはMatthew Cookによってそのチューリング完全性が証明されており、単純なルールでありながら非常に複雑な振る舞いを示します。

まとめ

チューリング完全性は計算理論の基礎となる概念であり、計算の理解やプログラミング言語設計において重要な役割を果たしています。この理解は、理論的な問題や実用的な応用の両方に対する洞察を提供します。

もう一度検索