Independencia del alfabeto

3.4 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.12. Sean $Σ$ y $Γ$ alfabetos cualesquiera. Supongamos una funcion $f$ es $Σ$ -mixta y $Γ$ -mixta, entonces $f$ es $Σ$ -efectivamente computable sii $f$ es $Γ$ -efectivamente computable.

3.13. Sean $Σ$ y $Γ$ alfabetos cualesquiera. Supongamos un conjunto $S$ es $Σ$ -mixto y $Γ$ -mixto, entonces $S$ es $Σ$ -efectivamente computable (resp. $Σ$ -efectivamente enumerable) sii $S$ es $Γ$ -efectivamente computable (resp. $Γ$ -efectivamente enumerable).

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