Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
1 of 2

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.