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.

  • $\begingroup$ Copy at math.SE. $\endgroup$ Nov 26, 2012 at 9:18
  • $\begingroup$ Yeah - I had originally posted this in the math.stackexchange website, but then thought that I would likely get better responses here, since this seems much more of a CS question than a Math question. $\endgroup$
    – user4734
    Nov 26, 2012 at 9:54
  • $\begingroup$ @Nizbel99 In that case, you should have flagged there for migration and/or linked both questions to each other. Crossposting is generally frowned upon, especially so if it happens in rapid succession. You should each community their shot before anybody wastes time. $\endgroup$
    – Raphael
    Nov 26, 2012 at 11:48
  • $\begingroup$ Regarding the question: what exactly do you want here; a proof for RE being closed against shrink similar Wu Yin's, or any proof? If the latter, you should post the proof(s) you have as answer(s) so people don't waste their time. $\endgroup$
    – Raphael
    Nov 26, 2012 at 11:49
  • $\begingroup$ Yes, I would like to see a proof similar to Wu Yin's proof. The last part of my comment might not have been the clearest. $\endgroup$
    – user4734
    Nov 26, 2012 at 14:33

2 Answers 2


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.

  • $\begingroup$ Is there a name to this particular theorem that I can look up? We haven't talked about the notation of computablility enumerable in class. This is just something I had noticed in Wu Yin's proof. I liked the idea of enumerating strings in a certain way and then simulating them on the UTM using the original TM provided. EDIT: I hadn't noticed your edit as I was typing up my reply. $\endgroup$
    – user4734
    Nov 26, 2012 at 14:58
  • $\begingroup$ These are basic properties of c.e. sets which would be covered in any standard textbook on computability theory. Maybe have a look at Enderton's "Computability theory", books.google.com/books/about/… $\endgroup$ Nov 26, 2012 at 18:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.