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.