En virtud de los teoremas ya probados tenemos el siguiente teorema que asegura que los tres paradigmas son equivalentes.
4.8. Sea un alfabeto finito. Dada una funcion , las siguientes son equivalentes:
(1) es -Turing computable
(2) es -recursiva
(3) es -computable
Proof. (1)(2) es probado en el Teorema 4.6. (2)(3) es probado en el Teorema 4.3. (3)(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 un alfabeto finito y sea . Las siguientes son equivalentes:
(1) es -Turing enumerable
(2) es -recursivamente enumerable
(3) es -enumerable
Proof. Directo de las definiciones y el teorema anterior.
4.10. Sea un alfabeto finito y sea . Las siguientes son equivalentes:
(1) es -Turing computable
(2) es -recursivo
(3) es -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 -efectivamente computables. Esta aseveracion es conocida como la
Tesis de Church: Toda funcion -efectivamente computable es -recursiva.
Y por supuesto puede ser sintetizada diciendo que Godel vence a Leibniz (y por lo tanto los cuatro proceres empatan!). 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.