Computability of a function and decidability [closed]

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 ∈ A^∗$, always halts with $f(x)$ on its tape.

Let $L_f$ denote the language $\{x\#f(x)∣x∈A^*\}$.

This is a part of the question and the answer says that if $L_f$ is recursive then $f$ is computable. If $L_f$ is recursive then we can accept all the string in the language but we have to reject the strings not in the language. A function is said to be computable when it has a halting Turing machine which computes the value for $f(x)$ for every $x$ in the domain and HALTS.
Then what about the values outside the domain?

Answer 1

Since $L_f = \{x\#f(x);x ∈ A^*\}$, $f$ must be total, otherwise $L_f$ isn't defined at all. So, we suppose that $f$ is total.

Let's prove : $L_f$ is recursively enumerable $=> f$ is computable. We will use a technic called dovetailing. For the need of the proof, suppose that $c_i$ denotes the $i^{th}$ element of $A^*$ (it's a function, we write $c_i$ instead of $c(i)$ for clarity). We use the lexicographic order to define the $i^{th}$ element of $A^*$.

$L_f$ is recursively enumerable, there exists so a Turing machine $M_{L_f}$ that, for each input $x ∈ (A \cup\{\#\}\cup B)^*$, halts if and only if $x ∈ L_f$. Let's try to define a Turing machine $M$ that computes $f(x)$ foreach $x∈A^*$. We will just describe this machine, we won't give a formal definition. Let $x$ be the input of $M$, the machine will proceed by this way :

• Execute one step of $M_{L_f}$ with input : $x\#c_0$. If $M_{L_f}$ halts, then $f(x) = c_0$. Else, continue.
• Execute two steps of $M_{L_f}$ on both inputs : $x\#c_0$ and $x\#c_1$ sequentially. If $M_{L_f}$ halts on one of them, let's call it $x\#c_i$, then $f(x) = c_i$. Else, continue.
• Go by this way, at step $i$, $M$ executes $i$ steps of $M_{L_f}$ with inputs : $x\#c_0, x\#c_1 ... x\#c_i$. If $M_{L_f}$ halts on one of them, suppose it's $x\#c_k$, then $f(x) = c_k$.

Since $f$ is total, $x\#f(x)$ exists for each $x$. In addition, $L_f$ is recursively enumerable, so, when $M$ arrives to $x\#f(x)$, $M_{L_f}$ will halt after $k$ steps because $x\#f(x) ∈ L_f$. $M$ then computes $f(x)$ for every $x∈A^*$.

I hope i have explain it well.

To complete the proof, $c_i$ must be proved to be computable, it's somewhat easy to do.