2
$\begingroup$

I'm trying to prove the following proposition: The fact that a language $L$ over a finite alphabet $A$ is primitive recursive, recursive or recursively enumerable does not depend upon the enumeration of the alphabet.

My first questions are:

1) Did I understand this right: If my language is recursively enumerable under the bijection $\alpha: A \rightarrow \left\{1,2,\ldots, |A| \right\}$ (meaning the set $\alpha^\star (L)$ is recursively enumerable, where $\alpha^\star$ is the extension of $\alpha$ to the set $A^\star = \cup_{k \in \mathbb{N}} A^k$, assigning every tupel of elements from $A$ the corresponding numbers by the function $\alpha$ and the using a coding function to code the tupel into a single natural number ) then for every other bijection every $\beta: A \rightarrow \left\{1,2,\ldots, |A| \right\}$, $\beta^\star (L)$ has to be recursively enumerable as well ? I wonder, couldn't it happen, because $A$ is finite, that if $\alpha^\star (L)$ is recursively enumerable, that it is also , for example, primitive recursive ? (If not, is there a counterexample ?)

2) How can I prove this ? Because any coding isn't by definition recursive because its domain is $\mathbb{N}^\star = \cup_{k \in \mathbb{N}} \mathbb{N}^k$, but I think I have to use that somehow.

  • 2
    At t$h$e informal, or semi-formal level, t$h$e result is, to use an overused word, obvious. Take any algorit$h$m that enumerates the code numbers of the words under one encoding. A tiny post-processor can turn these code numbers into code numbers under the other encoding.2011-07-02

1 Answers 1

2

Your question is basically answered by the comment of user6312. The point is that the translation function---translating the encoding of a word in one enumeration to its encoding in another enumeration---is a primitive recursive permutation (and note also that the inverse function is also primitive recursive). Thus, by applying this function or its inverse as appropriate, we see that the original language is primitive recursive, computable, or c.e., respectively, if and only if the variant lanaguage is in this class, since each of these classes is closed under composition with a primitive recursive function.

Meanwhile, allow me to point out that the result is not true when the alphabet is infinite. For example, imagine an alphabet with symbols $a_n$ for $n\in\mathbb{N}$, and a language $L$ consisting of the one-letter words $a_{2n}$, using the even letters only. This language is primitive recursive, and trivial in a variety of ways. By permuting the alphabet, however, we could realize any language consisting of an infinite co-infinite set of the one-letter words. Since there are continuum many of these, most of them are neither primitive recursive, computable nor even c.e., violating the corresponding property for infinite alphabets.

But if you insist on primitive recursive re-enumerations of the alphabet, then the result becomes true again. Perhaps one way to think about it is that every permutation of a finite set is primitive recursive, and so the finite alphabet case is a special case of the more general fact.

  • 0
    Your way is also fine. What I meant is that given a word in the new encoding, you first translate it into the old encoding, and then apply the characteristic function (restricted to affirmative values). This process will accept the word iff it is in the desired language.2011-07-03