Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and where $\mathrm{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, $\mathrm{shrink}_a(baaab) = bab$.

So I was browsing around for other examples to study, and I came across the following proof for the $\mathrm{prefix}$ operation: (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.

share|cite|improve this question
Crossposted to cs.SE. – Raphael Nov 26 '12 at 11:47
up vote 1 down vote accepted

Isn't it clear that the image of an RE language $\def\L{\mathscr L}\L$ under any computable operation $f$ on its elements is also RE? Because by hypothesis, there was a machine $M_\L$ which enumerated the elements of $\L$, and so one can easily build a machine which uses $M_\L$ as a subroutine, and which, for each string $s$ output by $M_\L$, transforms $s$ to $f(s)$ and outputs that instead.

Since $shrink_a$ is just such a computable function $f$, it follows that $shrink_a(\L)$ is RE whenever $\L$ is.

share|cite|improve this answer
I see that the accepted answer on se.cs by Andrej Bauer says precisely the same thing I said: "If $A$ is computably enumerable and $f$ is computable then $f(A)$ is computably enumerable." – MJD Jan 24 '13 at 23:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.