チャーチ＝チューリングの提唱

チャーチ＝チューリングの提唱は、あらゆる有効な手続きによって計算可能なすべての関数はチューリングマシンによって計算可能であると主張し、アルゴリズムという非形式的な概念を厳密な数学的モデルと等価であると見なします。

Definition

チャーチ＝チューリングの提唱は、直感的に計算可能な関数が、チューリングマシン、あるいはラムダ計算、または一般再帰関数によって計算可能な関数と正確に一致するという主張です。直感的な概念が形式的に定義されていないため、これは定理ではなく提唱とされています。

Scope

このトピックでは、提唱の声明、独立して提案されたモデルからの収束的証拠、有効な計算可能性に関する元の提唱と、より強力な物理的または計算複雑性理論的な変種との区別、および計算可能性理論における直感と形式的証明の間の橋渡しとしての提唱の役割について扱います。

Core questions

• アルゴリズムという非形式的な概念を形式的なモデルと同一視するとはどういう意味ですか？
• 独立したモデルの収束が、なぜこの提唱の強力な証拠と見なされるのですか？
• この提唱は数学的な定理、定義、それとも経験的な主張ですか？
• 物理的および計算複雑性理論的なバージョンは、元の声明をどのように超えていますか？

Key theories

計算モデルの収束

チューリングマシン、チャーチのラムダ計算、ゲーデルとヘルブランドの再帰関数は、まったく同じクラスの関数を定義することが示されており、この独立した一致が提唱の主要な証拠として提示されています。

定理ではなく提唱としての位置づけ

有効な手続きという直感的な概念は形式化されていないため、この主張は証明できません。これは、非形式的なアルゴリズム的議論が形式的なチューリングマシン構成の代わりとなることを可能にする、基礎的な同一視として受け入れられています。

Clinical relevance

この提唱は、有効な手続きの合理的な概念はチューリング等価であると仮定されているため、チューリングマシンとしてではなく、高水準の擬似コードでアルゴリズムを記述するという日常的な実践を正当化します。また、物理的または量子のデバイスがチューリング計算可能な範囲を超えて計算できるかどうかについての議論の枠組みも提供します。

History

1936年、チャーチは有効な計算可能性をラムダ定義可能性と同一視することを提案し、チューリングは独立して自身の機械モデルを主張しました。その後、チューリング、クリーネらは、これらと再帰関数が等価であることを証明しました。当初懐疑的だったゲーデルは、チューリングの分析を決定的なものと見なすようになり、この結合された主張はチャーチ＝チューリングの提唱として知られるようになりました。

Debates

物理的な計算はチューリングの限界を超えることができますか？

元の提唱は有効な手続きに関するものですが、より強力な物理的バージョンは、物理的に実現可能なデバイスがチューリング計算不可能な関数を計算することはできないと主張しています。ハイパーコンピュテーションの提案や量子力学の含意は、この拡張された主張を論争の的にしていますが、古典的な提唱は本質的に異論なく受け入れられています。

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

なぜ定理ではなく提唱と呼ばれるのですか？

これは形式的なモデルと有効な手続きという非形式的な概念を結びつけるものであり、その非形式的な概念には証明すべき数学的な定義がありません。強力な証拠は、計算を形式化しようとするすべての独立した試みが同じクラスの関数を生み出してきたことですが、この支持は概念的なものであり、証明ではありません。

量子コンピュータはチャーチ＝チューリングの提唱を否定しますか？

いいえ。量子コンピュータは一部の問題をより速く解決できるかもしれませんが、チューリングマシンとまったく同じクラスの関数を計算するため、計算可能性に関する元の提唱は変わりません。これらは、計算可能性ではなく効率性に関わる、より強力な計算複雑性理論的なバージョンに関係しています。