Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$.

I can't figure out why this is true.

Since $f$ is computable there is a Turing machine that computes it, denote it by $M_f$.

Since $A \in RE$, we get another machine that accepts $A$, and obviously $f(A)$ is reducible from $A$, but given only that an input $f(x)$ for $f(A)$, is accepted iff $x\in A$, and $f$ is not necessarily injection so idk if you can get $x$.

Another idea I had was:

Given that $A\in RE $, there is a counter machine for it, and since $f$ is computable then there is a Turing machine that prints $f(x)$ for a given $x \in A$, so what we could do is count each word in $A$ one by one, and for each one simulate $f$ on that word and that would result in a counter machine for $f$, i.e. $f$ is recursively enumerable, so we get $f\in RE$.

Any idea if this is true? if not, how can this be proved?

Thanks in advance.

  • 1
    $\begingroup$ For convenience apply two equivalent definitions of RE. To prove that $f(A)$ is RE use the definition that there is a Turing machine that halts exactly for the elements of $f(A)$. However, translate that $A$ is RE using the equivalent definition that there is a Turing machine that lists $A$. To construct the machine that halts at the elements of $f(A)$, you can do the following: Given a $y$, run the machine that lists the elements of $A$. For each output $x_i\in A$ give them to the machine that computes $f(x_i)$ and check if $f(x_i)=y$. If it is true, halt. If not, continue to the next $x_i$. $\endgroup$
    – plop
    Commented Jul 24, 2020 at 18:32
  • $\begingroup$ That’s exactly what I did I think, only difference was that I called that machine that lists $A$ a counter. $\endgroup$
    – giorgioh
    Commented Jul 24, 2020 at 18:47


Your Answer

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