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)
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Feb 21 '17 at 22:08
  • 1
    $\begingroup$ What exactly is your question? This is a question-and-answer site, so you need to articulate the question that you want answered. Rather than copying the entire multiple-choice problem (or multiple problems) and your attempt at all of the pieces, please try to isolate one aspect that you are unsure about, and ask only about that. Remove all the other material that isn't relevant to that specific question. Also, we want you to ask only one question per post here on this site. This will help improve the chances that you get useful and relevant answers. $\endgroup$ – D.W. Feb 21 '17 at 22:10
  • 1
    $\begingroup$ What's the source of this problem? Please make sure to credit the source of material you obtain from others. $\endgroup$ – D.W. Feb 21 '17 at 22:10
  • 1
    $\begingroup$ Related: cs.stackexchange.com/q/70460/755. $\endgroup$ – D.W. Feb 21 '17 at 22:11
  • 1
    $\begingroup$ what ? i also discourage ur comment like that, sorry. that was question in one of my recent exam "GATE". and I tried my best before posting here, i also have shown my work there. but i stuck at 2nd part. whats wrong with this ? $\endgroup$ – user3699192 Feb 22 '17 at 6:10

The question is about the relation between a computable function $f$ and its graph (here denoted by $L_f$). Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).

So, your guess is right, and the correct answer is A. To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.

| cite | improve this answer | |
  • 1
    $\begingroup$ This is fine but if Lf is recursively enumerable, still f can be computed right? Do we really need Lf to be recursive here? $\endgroup$ – Arjun Suresh Apr 28 '17 at 13:46
  • 1
    $\begingroup$ @ArjunSuresh Yes, you can still use a "generate and test" technique, taking into consideration the possible divergence of the tester (since Lf is only r.e. in this case) So, you need dovetailing between inputs and time. $\endgroup$ – Andrea Asperti Apr 30 '17 at 5:23
  • 1
    $\begingroup$ Exactly, so the correct answer to this question is "f is computable if Lf is recursively enumerable; Lf is recursive if f is computable" Which is satisfied by option A. $\endgroup$ – Arjun Suresh May 1 '17 at 3:13
  • 1
    $\begingroup$ Actually by both options A and B right? $\endgroup$ – Arjun Suresh May 1 '17 at 3:27
  • $\begingroup$ @ArjunSuresh yep $\endgroup$ – Andrea Asperti May 1 '17 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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