En virtud de los teoremas ya probados tenemos el siguiente teorema que asegura que los tres paradigmas son equivalentes.
4.8. Sea \(\Sigma\) un alfabeto finito. Dada una función \(f\), las siguientes son equivalentes:
adhocprefix(1)adhocsufix \(f\) es \(\Sigma\)-Turing computable
adhocprefix(2)adhocsufix \(f\) es \(\Sigma\)-recursiva
adhocprefix(3)adhocsufix \(f\) es \(\Sigma\)-computable
Proof. (1)\(\Rightarrow\)(2) es probado en el Teorema 4.6. (2)\(\Rightarrow\)(3) es probado en el Teorema 4.3. (3)\(\Rightarrow\)(1) es probado en el Teorema 4.7.
También los tres paradigmas son equivalentes con respecto a los dos tipos de conjuntos estudiados, es decir:
4.9. Sea \(\Sigma\) un alfabeto finito y sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Las siguientes son equivalentes:
adhocprefix(1)adhocsufix \(S\) es \(\Sigma\)-Turing enumerable
adhocprefix(2)adhocsufix \(S\) es \(\Sigma\)-recursivamente enumerable
adhocprefix(3)adhocsufix \(S\) es \(\Sigma\)-enumerable
Proof. Directo de las definiciones y el teorema anterior.
4.10. Sea \(\Sigma\) un alfabeto finito y sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Las siguientes son equivalentes:
adhocprefix(1)adhocsufix \(S\) es \(\Sigma\)-Turing computable
adhocprefix(2)adhocsufix \(S\) es \(\Sigma\)-recursivo
adhocprefix(3)adhocsufix \(S\) es \(\Sigma\)-computable
Proof. Directo de las definiciones y el teorema anterior.
Otro modelo matemático de computabilidad efectiva es el llamado lambda calculus, introducido por Church, el cual también resulta equivalente a los estudiados por nosotros. El hecho de que tan distintos paradigmas computacionales hayan resultado equivalentes hace pensar que en realidad los mismos han tenido éxito en capturar la totalidad de las funciones \(\Sigma\)-efectivamente computables. Esta aseveración es conocida como la
Tesis de Church: Toda función \(\Sigma\)-efectivamente computable es \(\Sigma\)-recursiva.
Y por supuesto puede ser sintetizada diciendo que Godel vence a Leibniz (y por lo tanto los cuatro próceres empatan!). Si bien no se ha podido dar una prueba estrictamente matemática de la Tesis de Church, es un sentimiento común de los investigadores del área que la misma es verdadera.