$f$ being computable, given $x$, we get $f(x)$.
$L_f$ is recursive - given any string we get to know if the string is in $L$ or not.
Now lets see the two cases:
- Does $f$ being computable implies $L_f$ is recursive?
We are given $x$ and we need to know if $x\#f(x)$ belongs to $L_f$. Since $f$ being computable we can calculate $f(x)$ and our problem reduces to $3$ string comparisons - first $x$, followed by # and then f(x) which can be done by a TM. So, $L_f$ must be recursive.
- Does $L_f$ being recursive implies $f$ be computable?
If $L_f$ is recursive, given any string we can say whether it belongs to $L_f$ or not. Now, to compute $f(x)$, we can do a dovetailing approach starting with strings in lexicographic (or any other order) as follows $s1, s2, s3, \dots$ and forming inputs to the TM as
$x\#s_1, x\#s_2, x\#s_3, \dots $
By dovetailing it means to simulation TM for one step in first iteration, $2$ steps in second iteration, $3$ steps in third iteration etc., and in each iteration adding a new string to the simulation (TM is parallelly simulating all strings).
https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf
Now, for any $x$, we should have an $f(x)$ since $f$ is a total function. So, in our simulation we are sure that sometime we will add the string $x\#f(x)$ to the simulation and then the TM will halt for it. And whenever it does halt, we can just take the part of the input string after #, and that is $f(x)$. We have a way to compute $f(x)$ for any $x$. So, $f$ is computable. The same method would work even if $L_f$ is recursively enumerable and not necessarily recursive.
So, the correct statements are
- If $L_f$ is recursively enumerable $f$ is computable
- If $f$ is computable $L_f$ is recursive
So, option B is TRUE but official key was only A.
Option A is false because $f$ is computable even when $L_f$ is recursively enumerable and not necessarily recursive.
https://cs.stackexchange.com/questions/70626/recursive-language-and-computable-function