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)
