チューリング完全性とは

チューリング完全性とは、プログラミング言語がチューリングマシンの機能を実行できる場合です。 これは非常に基本的な機械式コンピューターの概念であり、コンピューターと見なすことができる最も単純な機械と呼ばれることもあります。 現在使用されているほぼすべてのプログラミング言語、および理論的にはそれらを実行するコンピューターは、チューリング完全性を備えています。

チューリングの完全性の概念は、第二次世界大戦中にコード化されたメッセージを解読する作業を含む英国のコンピューター科学者であるアラン・チューリングに由来しています。 コンピューティングに関する彼の仕事には、コンピューターが実際にできることの哲学の開発がありました。 これには、アルゴリズムを実行するだけでコンピューターが機能するという概念が含まれていました。 つまり、固定された一連のルールに従ってデータを処理し、問題を解決します。 これは、コンピューターが人のように「考え」たり、決定を下したりしないことを意味します。

コンセプトを説明するために、チューリングは、「a」が自動を意味する「a-machine」と呼ばれる仮想マシンについて説明しました。 他の人は後にチューリングマシンと呼びました。 マシンは、テープのリールを処理します。このテープは、前後に移動でき、シンボルのラインを含んでいます。 マシンはいつでも1つのシンボルを処理し、必要に応じてシンボルを変更できます。 コンセプトの目的上、テープのリールは無限に長くなる可能性があります。つまり、コンピューターのメモリは本質的に制限されていません。 これは、コンピューターが従うべき一連の命令を取得すると、それらの命令を適用できるデータの量は物理的な制限のみに依存するという考え方に類似しています。

皮肉なことに、今日のほとんどのコンピューターにはチューリングの完全性はありません。 これは、使用可能なストレージスペース、したがって処理できるデータに制限があるためです。 また、物理的な制限もあり、特に顕著なのは、最終的には摩耗することです。 チューリングの完全性を備えているのは、実際にはプログラミング言語です。 このため、このようなプログラムを実行しているコンピューターはチューリングコンピューターではありませんが、チューリングコンピューターをシミュレートするために使用できます。

チューリングの完全性をチューリングテストと混同しないでください。 これは、コンピューターが自然言語で会話できるかどうかを確認するためにチューリングによって設計された実験でした。 テストの原理は、人間がコンピューターとのテキストのみの会話と別の人間との違いを認識できない場合、コンピューターはテストに合格するということです。 会話の件名の範囲が制限されている場合、一部のコンピューターはテストに合格していますが、無制限の会話ではテストに合格していません。