Independencia del alfabeto

3.5 Independencia del alfabeto

Una observacion importante es que los conceptos de funcion $Σ$ -efectivamente computable, de conjunto $Σ$ -efectivamente computable y de conjunto $Σ$ -efectivamente enumerable, no dependen del alfabeto $Σ$ . Esto lo establecemos formalmente en los dos siguientes lemas.

3.13. Sean $Σ$ y $Γ$ alfabetos cualesquiera. Supongamos una funcion $f$ es $Σ$ -mixta y $Γ$ -mixta, entonces $f$ es $Σ$ -efectivamente computable sii $f$ es $Γ$ -efectivamente computable.

3.14. Sean $Σ$ y $Γ$ alfabetos cualesquiera y supongamos $S$ es un conjunto $Σ$ -mixto y $Γ$ -mixto. Entonces

(a) $S$ es $Σ$ -efectivamente computable sii $S$ es $Γ$ -efectivamente computable.
(b) $S$ es $Σ$ -efectivamente enumerable sii $S$ es $Γ$ -efectivamente enumerable.

Dejamos al lector los detalles de las rutinarias pruebas de estos dos lemas.