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

2 of 2 added 604 characters in body

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.