2 added 604 characters in body edited Mar 11 '18 at 18:17 D.W.♦ 106k1414 gold badges135135 silver badges315315 bronze badges The problem with your proof is where you say "until you obtain $$w$$". That makes it sound to me like you stop the search as soon as you find a single $$x$$ such that $$f(x)=w$$. If that is what your machine $$M'$$ does, then your proof is faulty, for the reasons chi explains. Also, there is an additional step that is worth explaining: it's worth mentioning that any language that's recognizable by a NTM is also recognizable by a standard deterministic TM. This is a standard fact that probably doesn't need to be proven here. Fortunately, there is a simple fix. Here is a correctedan improved proof: 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 guess a word $$x \in \Sigma^*$$. If $$f(x)=w$$ and $$M$$ accepts on input $$x$$, 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. Moreover, any language that can be recognized by a nondeterministic TM, can be recognized by a deterministic TM. It follows that $$f(L)$$ is Turing recognizable. 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. Credit: thanks to xskxzr for explaining the idea of the proof and for the improved formatting. The problem with your proof is where you say "until you obtain $$w$$". That makes it sound to me like you stop the search as soon as you find a single $$x$$ such that $$f(x)=w$$. If that is what your machine $$M'$$ does, then your proof is faulty, for the reasons chi explains. Fortunately, there is a simple fix. Here is a corrected proof: 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 guess a word $$x \in \Sigma^*$$. If $$f(x)=w$$ and $$M$$ accepts on input $$x$$, 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. Credit: thanks to xskxzr for explaining the idea of the proof and for the improved formatting. The problem with your proof is where you say "until you obtain $$w$$". That makes it sound to me like you stop the search as soon as you find a single $$x$$ such that $$f(x)=w$$. If that is what your machine $$M'$$ does, then your proof is faulty, for the reasons chi explains. Also, there is an additional step that is worth explaining: it's worth mentioning that any language that's recognizable by a NTM is also recognizable by a standard deterministic TM. This is a standard fact that probably doesn't need to be proven here. Fortunately, there is a simple fix. Here is an improved proof: 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 guess a word $$x \in \Sigma^*$$. If $$f(x)=w$$ and $$M$$ accepts on input $$x$$, 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. Moreover, any language that can be recognized by a nondeterministic TM, can be recognized by a deterministic TM. It follows that $$f(L)$$ is Turing recognizable. Credit: thanks to xskxzr for explaining the idea of the proof and for the improved formatting. 1 answered Mar 11 '18 at 18:01 D.W.♦ 106k1414 gold badges135135 silver badges315315 bronze badges The problem with your proof is where you say "until you obtain $$w$$". That makes it sound to me like you stop the search as soon as you find a single $$x$$ such that $$f(x)=w$$. If that is what your machine $$M'$$ does, then your proof is faulty, for the reasons chi explains. Fortunately, there is a simple fix. Here is a corrected proof: 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 guess a word $$x \in \Sigma^*$$. If $$f(x)=w$$ and $$M$$ accepts on input $$x$$, 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. Credit: thanks to xskxzr for explaining the idea of the proof and for the improved formatting.