# recursive language and computable function

Question:

Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{*}$ to $B^{*}$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x \in A^{*}$, always halts with $f(x)$ on its tape. Let $L_{f}$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$. Which of the following statements is true:

(A) $f$ is computable if and only if $L_{f}$ is recursive.

(B) $f$ is computable if and only if $L_{f}$ is recursively enumerable.

(C) If $f$ is computable then $L_{f}$ is recursive, but not conversely.

(D) If $f$ is computable then $L_f$ is recursively enumerable, but not conversely.

My Attempt:

if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.

$L_f$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$, which means $L_f$ strings of type which has image and pre image to left and right of $\#$.

• Now consider a function $f(x)$ is computable and its corresponding language $L_f$, will $L_f$  be recursive ? (given that $f(x)$ is computable )

Yes, $L_f$ wil be recursive if $f(x)$ is computable. Because if $x\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\# f(x)$ on table and i just left to match left strings to the right string of $\#$ .

• Now consider a function $L_f$  is recursive, will $f(x)$ be computable ?
• (i need exlanation of this part)
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Commented Feb 21, 2017 at 22:08
• What exactly is your question? This is a question-and-answer site, so you need to articulate the question that you want answered. Rather than copying the entire multiple-choice problem (or multiple problems) and your attempt at all of the pieces, please try to isolate one aspect that you are unsure about, and ask only about that. Remove all the other material that isn't relevant to that specific question. Also, we want you to ask only one question per post here on this site. This will help improve the chances that you get useful and relevant answers.
– D.W.
Commented Feb 21, 2017 at 22:10
• What's the source of this problem? Please make sure to credit the source of material you obtain from others.
– D.W.
Commented Feb 21, 2017 at 22:10
• Related: cs.stackexchange.com/q/70460/755.
– D.W.
Commented Feb 21, 2017 at 22:11
• what ? i also discourage ur comment like that, sorry. that was question in one of my recent exam "GATE". and I tried my best before posting here, i also have shown my work there. but i stuck at 2nd part. whats wrong with this ? Commented Feb 22, 2017 at 6:10

The question is about the relation between a computable function $f$ and its graph (here denoted by $L_f$). Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).
So, your guess is right, and the correct answer is A. To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.