El lenguaje sobre un alfabeto finito es "estable" con respecto a la recursividad primitiva ( & etc.) bajo diferentes enumeraciones

Question

Intento demostrar la siguiente proposición: El hecho de que un lenguaje $L$ sobre un alfabeto finito $A$ es primitivo recursivo, recursivo o recursivamente enumerable no depende de la enumeración del alfabeto.

Mis primeras preguntas son:

1) ¿He entendido bien esto: Si mi lenguaje es recursivamente enumerable bajo la biyección $\alpha: A \rightarrow \left\{1,2,\ldots, |A| \right\}$ (es decir, el conjunto $\alpha^\star (L)$ es recursivamente enumerable, donde $\alpha^\star$ es la extensión de $\alpha$ al conjunto $A^\star = \cup_{k \in \mathbb{N}} A^k$ asignando cada tupel de elementos de $A$ los números correspondientes mediante la función $\alpha$ y el uso de una función de codificación para codificar el tupel en un único número natural ) entonces para cualquier otra biyección cada $\beta: A \rightarrow \left\{1,2,\ldots, |A| \right\}$ , $\beta^\star (L)$ tiene que ser recursivamente enumerable también? Me pregunto si no podría ocurrir, porque $A$ es finito, que si $\alpha^\star (L)$ es recursivamente enumerable, que también lo es, por ejemplo, la primitiva recursiva ? (Si no, ¿hay algún contraejemplo?)

2) ¿Cómo puedo demostrar esto? Porque cualquier codificación no es por definición recursiva porque su dominio es $\mathbb{N}^\star = \cup_{k \in \mathbb{N}} \mathbb{N}^k$ pero creo que tengo que usarlo de alguna manera.

Answer 1

Tu pregunta está básicamente respondida por el comentario del usuario6312. La cuestión es que la función de traducción--traducir la codificación de una palabra en una enumeración a su codificación en otra enumeración--es una permutación recursiva primitiva (y nótese también que la función inversa es también recursiva primitiva). Así, aplicando esta función o su inversa según el caso, vemos que el lenguaje original es recursivo primitivo, computable, o c.e., respectivamente, si y sólo si el lenguaje variante está en esta clase, ya que cada una de estas clases se cierra por composición con una función recursiva primitiva.

Mientras tanto, permítanme señalar que el resultado no es cierto cuando el alfabeto es infinito. Por ejemplo, imaginemos un alfabeto con símbolos $a_n$ para $n\in\mathbb{N}$ y una lengua $L$ que consiste en las palabras de una sola letra $a_{2n}$ Utilizando sólo las letras pares. Este lenguaje es recursivo primitivo, y trivial en una variedad de formas. Sin embargo, permutando el alfabeto, podríamos realizar cualquier lenguaje consistente en un conjunto infinito co-infinito de palabras de una sola letra. Como hay un número continuo de ellos, la mayoría no son ni recursivos primitivos, ni computables, ni siquiera c.e., violando la propiedad correspondiente para los alfabetos infinitos.

Pero si se insiste en las re-enumeraciones recursivas primitivas del alfabeto, entonces el resultado vuelve a ser verdadero. Tal vez una forma de pensar en ello es que toda permutación de un conjunto finito es recursiva primitiva, por lo que el caso del alfabeto finito es un caso especial del hecho más general.