0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is the question about definition of computable functions ? $\endgroup$ – user80502 Nov 27 '17 at 16:00
  • 3
    $\begingroup$ 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. $\endgroup$ – chi Nov 27 '17 at 18:43
  • $\begingroup$ 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 $\endgroup$ – venkat Nov 28 '17 at 9:48
  • $\begingroup$ @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 $\endgroup$ – venkat Nov 28 '17 at 9:53
  • $\begingroup$ @venkat Your post doesn't reflect your actual question. Please update it. (Don't use the word "edit" in your edit.) $\endgroup$ – Yuval Filmus Dec 1 '17 at 16:12
1
$\begingroup$

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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.