1
$\begingroup$

Would this proof work?

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

Your proof has a flaw.

Assume $L=\{b\}$, and $f(a)=f(b)=w$ for some word $w$. We have $f(L)=\{w\}$.

TM $M'$ on $w$ finds the preimage $a$, then checks $a\not\in L$, and rejects. This is wrong, since $w$ should be accepted.

The point is, we should not reject $w$ just because we found a preimage of $w$ which is not in $L$. We should continue checking all such preimages.

Above, doing that we would consider $b$ as well, and cause $w$ to be accepted.

$\endgroup$
2
  • $\begingroup$ So what is the correct proof ? $\endgroup$ Commented Mar 11, 2018 at 10:31
  • 1
    $\begingroup$ It seems the original proof is correct because a NTM accepts $w$ if there is at least one branch accepting $w$. Here the $a$ branch rejects but the $b$ branch accepts, so the NTM accepts as a result. @Idonotknow $\endgroup$ Commented Mar 11, 2018 at 16:12
2
$\begingroup$

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.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.