計算可能の定義をした

提唱であり命題ではない

なので証明されたわけではない

「チャーチ」と「チューリング」は、それぞれAlonzo ChurchとAlan Turingのことだが、実際にこのテーゼ自体を誰が言い出したのかはわからん

テーゼが提唱されるまで「計算可能」の概念が定まっていなかった

チューリングマシンやラムダ計算、帰納的関数などその他いくつもの計算モデルで計算可能/不能の境界が一致してた

それまでは、↑この辺の計算モデルは独立に考えられていた

それぞれの定義は全く違って見えるのに、なぜか一致していた

そこでこれらのモデルが

できることを「計算可能」とし、

できないことを「計算不能」としよう

と提唱された

計算可能な関数の計算手続きの満たすべき性質

by Herbert B. Enderton

その手続きには、有限長の明確な命令列がなければならない

命令列とはプログラムのこと

その手続きに、 f の定義域にある k-タプル x が与えられるとき、有限個の離散ステップを実行後にその手続きは完了し、 f(x) を生成する

その手続きに f の定義域にない k-タプル x が与えられるとき、

手続きは永久に続き、停止しない

あるいは停止したとしても、 x についての f の値を返さない

これらの3性質を全て満たすような関数を「計算可能」とする

これらの性質は形式的に表現できないため、チャーチ・チューリングのテーゼは証明できない

この辺のクラスの計算可能性が、同一

Churchのテーゼ

計算可能な関数のクラス = 部分帰納的関数のクラスP

つまり、チューリングマシンで計算可能な関数のクラスは、部分帰納関数のクラスを全く一致するということを言っている

チューリングのテーゼ

\Sigmaをアルファベット、

\Sigma^\astを\Sigmaの記号列の集合とする

\Sigma^\ast上の任意のn項部分関数f:(\Sigma^\ast)^n\rightarrow\Sigma^\astは計算可能である

\Leftrightarrowfは\Sigma上のチューリングマシンによって計算可能である

↑コレ自体は恐らくAlan Turingによる提唱

参考

『(理論)12 計算モデルの基礎理論』 p.27

良い本らしい

良い本らしい