2 added 604 characters in body
source | link

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 a correctedan 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.

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.

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.

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.

1
source | link

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.