I have seen this question here, Closure of Turing-recognizable languages under homomorphism But actually this question answers the question of "What is the relation between homomorphism and concatenation?", so I still have a problem of how to show that the collection of Turing-recognizable languages is closed under homomorphism. Could anyone help me in doing so please?

In my opinion closure under homomorphism is very similar to closure under Kleene Star, but I am convinced that I have to put marks on any number of tape cells because my language $f(L)$ may contain many strings, am I right?

Many thanks!

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 10 '18 at 20:57
  • $\begingroup$ @D.W. I know that I have to build a Turing machine that recognizes $f(L)$ but I do not know what will be the relation of $f(w_1)$ and $w_1$ in my constructed machine..... could you give me a hint in doing so? $\endgroup$ – Idonotknow Mar 11 '18 at 2:08
  • 1
    $\begingroup$ What about decoding the input to multiple possible $w$s then running the Turing machine corresponding to $L$ on these $w$s? $\endgroup$ – xskxzr Mar 11 '18 at 8:55
  • $\begingroup$ you mean like the proof of closure under Kleene star as I asked in my question?@xskxzr $\endgroup$ – Idonotknow Mar 11 '18 at 10:33
  • $\begingroup$ @D.W. That question asks two questions, one (in the title) is "is the class of Turing-recognizable languages closed under homomorphism", and the other is "is my proof correct". This is my opinion. $\endgroup$ – xskxzr Mar 11 '18 at 15:55

The proof is posted by Anwar Saiah on this post. I quote it here (with its formatting improved).

Given a language $L$ that is Turing recognizable and a TM $M$ that recognizes it and a homomorphism $f$, we build a NTM $M'$ that recognizes $f(L)$.

$M'$ looks like this:

On input $w$ :

  • Non-deterministicly feed words from $\Sigma^∗$ to $f$ until you obtain $w$.

  • Run $M$ on $f^{−1}(w)$, if $M$ accepts accept, otherwise reject.

This works because $M'$ is a non-deterministic Turing machine. A NTM accepts $w$ if there is at least one branch accepting $w$, so if there is any word $x$ such that $f(x)=w$ and $M(x)$ accepts, this will find it and accept.

| cite | improve this answer | |
  • $\begingroup$ @D.W. I disagree with chi. I left a comment on his answer to show my point. $\endgroup$ – xskxzr Mar 11 '18 at 17:31
  • $\begingroup$ why we run M on $f^{-1}$ and not $f$? $\endgroup$ – Idonotknow Mar 11 '18 at 17:56
  • $\begingroup$ That makes sense. Thanks for the explanation! I have posted what I think is a clearer version of this proof on the other page. $\endgroup$ – D.W. Mar 11 '18 at 18:02

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