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 funcion \(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.
Tambien 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 matematico de computabilidad efectiva es el llamado lamda calculus, introducido por Church, el cual tambien 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 exito en capturar la totalidad de las funciones \(\Sigma\)-efectivamente computables. Esta aseveracion es conocida como la
Tesis de Church: Toda funcion \(\Sigma\)-efectivamente computable es \(\Sigma\)-recursiva.
Si bien no se ha podido dar una prueba estrictamente matematica de la Tesis de Church, es un sentimiento comun de los investigadores del area que la misma es verdadera.