Conclusiones: La tesis de Church

4.5 Conclusiones: La tesis de Church

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 $f$ , las siguientes son equivalentes:

(1) $f$ es $Σ$ -Turing computable
(2) $f$ es $Σ$ -recursiva
(3) $f$ es $Σ$ -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 $Σ$ un alfabeto finito y sea $S \subseteq ω^{n} \times Σ^{* m}$ . Las siguientes son equivalentes:

(1) $S$ es $Σ$ -Turing enumerable
(2) $S$ es $Σ$ -recursivamente enumerable
(3) $S$ es $Σ$ -enumerable

Proof. Directo de las definiciones y el teorema anterior.

4.10. Sea $Σ$ un alfabeto finito y sea $S \subseteq ω^{n} \times Σ^{* m}$ . Las siguientes son equivalentes:

(1) $S$ es $Σ$ -Turing computable
(2) $S$ es $Σ$ -recursivo
(3) $S$ 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.