Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Copy at math.SE. –  Hendrik Jan Nov 26 '12 at 9:18
    
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. –  Nizbel99 Nov 26 '12 at 9:54
    
@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. –  Raphael Nov 26 '12 at 11:48
    
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. –  Raphael Nov 26 '12 at 11:49
    
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. –  Nizbel99 Nov 26 '12 at 14:33

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Nizbel99 Nov 26 '12 at 14:58
    
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/… –  Andrej Bauer Nov 26 '12 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.

share|improve this answer

Your Answer

 
discard

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.