Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages

Question

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where $\text{shrink}_a(w)$ is the string formed from $w$ by replacing every maximal substring of two or more $a$'s by a single a. For example, $\text{shrink}_a(baaab) = bab$.

So I was browsing around for other examples to study, and I came across the following proof for the prefix operation: Proving that recursively enumerable languages are closed against taking prefixes (the proof given by the user Wu Yin). I thought that this was a very cool way of proving something like this, instead of just directly building an alternate TM. I'm curious to know, can anyone come up with a proof that is of a similar style and flavor to the one pointed above? I would be very curious to see a similar bijective proof regarding countable/uncountable sets!!

This has reminded me that there can be many ways to prove something, so I wanted to see what kind of flavor other people's proofs might have to this sample problem. I find that too often, students (and myself included) get caught up in a single procedure for finding solutions to a particular type of problem and neglect to see other ways of showing the same result.

Answer 1

For any kind of a serious argument about computably enumerable sets, you need to free yourself of details concerning Turing machines. So you should look for general useful principles that allow you to prove properties of c.e. sets. Here is one:

If $A$ is computably enumerable and $f$ is computable then $f(A)$ is computably enumerable.

Using this, we immediately get:

The set $\mathrm{shrink}_a(L)$ is computably enumerable because it is the image of the computably enumerable set $L$ by the computable function $\mathrm{shrink}_a$.

Other such useful principles are (note that I am using the new terminology in which "recursive" is replaced by "computable"):

• computable sets are computably enumerable
• c.e. sets are closed under finite intersections
• c.e. sets are closed under inverse images by computable functions
• c.e. sets are closed under computably enumerable unions
• c.e. sets are closed under projection: if $E \subseteq \mathbb{N} \times \mathbb{N}$ is a c.e. set, then so is its projection $\lbrace n \in \mathbb{N} \mid \exists m \in \mathbb{N} . (n,m) \in E\rbrace$
• a set is c.e. if and only if, it is the domain of a computable (partial) function
• a set is c.e. if and only if, it is the image of a computable (partial) function

With these you can get pretty far.

Answer 2

The question actually is easy, provided you take the right definition. RE languages can be defined using a Turing Machine in two equvalent ways. As an acceptor which accepts words in the language and halts (and may halt or loop otherwise), or as an enumerator, which will write the elements of the language (probably in some weird order) onto the output tape (assuming there is a separate working tape).

Using the latter concept several closure operations of the type you mention are trivialities. If I want to shrink, I start my enumerator, and when it outputs a word of the language apply shrink.