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$
    – Idonotknow
    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$
    – xskxzr
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.