計算可能関数とチャーチ＝チューリングの提唱

計算可能関数とは、機械的な手続きによって評価できる関数であり、チャーチ＝チューリングの提唱は、この非形式的な概念を、すべて同じクラスを定義するいくつかの厳密な数学的モデルと同一視するものです。

Definition

ある関数が計算可能であるとは、その関数が定義されているすべての入力に対して、何らかのチューリングマシン、あるいは同等に何らかの部分再帰的定義がその出力を生成する場合を指します。チャーチ＝チューリングの提唱は、この数学的に厳密なクラスが、直感的な有効計算可能関数のクラスと一致すると主張します。

Scope

このトピックでは、チューリングマシン、基本関数から合成、原始再帰、最小化によって構築される部分再帰関数、ラムダ計算とレジスタマシン、これらのモデルが同等であることの証明、ユニバーサルマシン、そしてそれらがすべての有効な計算を捉えるというチャーチ＝チューリングの提唱について扱います。

Core questions

• チューリングマシンとは何か、そしてそれはどのように計算を定義するのか？
• 部分再帰関数はどのように基本操作から生成されるのか？
• なぜすべての妥当な計算モデルは同じ関数を定義するのか？
• チャーチ＝チューリングの提唱の現状と意義は何か？

Key theories

チューリングマシンモデル

チューリングマシンは、無限のテープ上で動作する有限状態の装置であり、それが計算する関数は、初歩的な記号操作の観点からアルゴリズムの概念を形式化します。

モデルの等価性

チューリングマシン、部分再帰関数、ラムダ計算、レジスタマシンはすべて、まったく同じクラスの関数を計算し、計算可能性の概念の堅牢性を示しています。

ユニバーサルマシンと列挙

コードが与えられれば任意の機械をシミュレートするユニバーサルチューリングマシンが存在するため、計算可能関数は効果的に列挙され、データとして扱われることができ、これは自己参照の結果の基礎となります。

Clinical relevance

計算可能関数の概念は、理論計算機科学の基礎をなすものです。ユニバーサルマシンは、プログラム内蔵型コンピュータの先駆けであり、モデルの等価性は、アルゴリズムの単一で堅牢な定義を正当化し、この枠組みは、決定不能性や複雑性が研究される厳密な設定を提供します。

History

1936年、チャーチはラムダ計算を通じて、チューリングは自身のマシンを通じて有効計算可能性を定義し、これら2つの概念はすぐにクリーネの再帰関数と同等であることが証明されました。結果として生まれたチャーチ＝チューリングの提唱は、アルゴリズムの確立された定義となり、チューリングのユニバーサルマシンは汎用コンピュータの概念的な祖先となりました。

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

計算可能ではない関数もあるのか？

はい、あります。プログラムは列挙可能ですが、関数は列挙できないため、数え上げ論証により、ほとんどの関数は計算可能ではないことが示され、停止関数のような具体的な例は、計算不能であることが証明されています。計算可能性は、アルゴリズムが評価できる関数に真の制約を課します。

チャーチ＝チューリングの提唱は、コンピュータができることを制限するのか？

それは、有効計算のいかなるモデルも、チューリングマシンを超える計算可能関数のクラスを拡張しないことを示唆しています。より高速なハードウェアや異なるアーキテクチャは効率を変えるものであり、原理的に計算可能なものの境界を変えるものではないため、この提唱はアルゴリズムによる解決可能性に絶対的な限界を設定します。