Computability of a function and decidability [closed]

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?

closed as unclear what you're asking by Evil, chi, David Richerby, fade2black, Yuval FilmusDec 1 '17 at 11:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Is the question about definition of computable functions ? – Abdous Kamel Nov 27 '17 at 16:00
• What is the question? Also note that if $f$ is taken to be total (as you do above), then "the values outside the domain" do not exist. – chi Nov 27 '17 at 18:43
• the question is about determining what is true among the following options sir: option a: Lf is recursive iff f(x) is a computable function option b: Lf is recursively enumerable iff f(x) is computable @chi – venkat Nov 28 '17 at 9:48
• @dylan61 the question is not alone about computable functions the in the above mentioned options both were given correct i dont know how to prove if Lf is recursively enumberable then f is computable please help – venkat Nov 28 '17 at 9:53
• @venkat Your post doesn't reflect your actual question. Please update it. (Don't use the word "edit" in your edit.) – Yuval Filmus Dec 1 '17 at 16:12

1 Answer

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.

• please have a look at this brother cs.stackexchange.com/questions/84610/… – venkat Nov 29 '17 at 6:36
• I'm not sure this answers the question, but otherwise it's a good post. – Yuval Filmus Dec 1 '17 at 11:33
• @YuvalFilmus Thank you. The author has clarified the question in comments, it is : does $L_f$ recursively enumerable imply $f$ computable. – Abdous Kamel Dec 1 '17 at 16:11