Computer Science Asked by se718 on January 2, 2022

Let $Ain RE$, and define$f(A) = {y | y= f(x), xin 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 $xin A$, and $f$ is not necessarily injection so idk if you can get $x$.

Another idea I had was:

Given that $Ain 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 $fin RE$.

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

Thanks in advance.

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP