チャーチ・チューリングのテーゼ

Church-Turing thesis

計算可能の定義をした

提唱であり命題ではない

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

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

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

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

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

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

そこでこれらのモデルが

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

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

と提唱された

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

by Herbert B. Enderton

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

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

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

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

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

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

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

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

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

Churchのテーゼ

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

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

チューリングのテーゼ

$ \Sigmaをアルファベット、

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

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

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

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

ラムダ計算の計算可能性

参考

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

チャーチ＝チューリングのテーゼ - Wikipedia

計算可能関数 - Wikipedia

https://en.wikipedia.org/wiki/Church–Turing_thesis

オートマトン言語理論計算論 I

良い本らしいmrsekut.icon

オートマトン言語理論計算論 II

良い本らしいmrsekut.icon