edited by
18,269 views
86 votes
86 votes

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:

  1. $f$ is computable if and only if $L_{f}$ is recursive.
  2. $f$ is computable if and only if $L_{f}$ is recursively enumerable.
  3. If $f$ is computable then $L_{f}$ is recursive, but not conversely.
  4. If $f$ is computable then $L_{f}$ is recursively enumerable, but not conversely.
edited by

4 Answers

82 votes
82 votes

$f$ being computable, given $x$, we get $f(x)$.

$L_f$ is recursive - given any string we get to know if the string is in $L$ or not. 

Now lets see the two cases:

  • Does $f$ being computable implies $L_f$ is recursive?

We are given $x$ and we need to know if $x\#f(x)$ belongs to $L_f$. Since $f$ being computable we can calculate $f(x)$ and our problem reduces to $3$ string comparisons - first $x$, followed by # and then f(x) which can be done by a TM. So, $L_f$ must be recursive. 

  • Does $L_f$ being recursive implies $f$ be computable?

If $L_f$ is recursive, given any string we can say whether it belongs to $L_f$ or not. Now, to compute $f(x)$, we can do a dovetailing approach starting with strings in lexicographic (or any other order) as follows $s1, s2, s3, \dots$ and forming inputs to the TM as

$x\#s_1, x\#s_2, x\#s_3, \dots $

By dovetailing it means to simulation TM for one step in first iteration, $2$ steps in second iteration, $3$ steps in third iteration etc., and in each iteration adding a new string to the  simulation (TM is parallelly simulating all strings).

https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf

Now, for any $x$, we should have an $f(x)$ since $f$ is a total function. So, in our simulation we are sure that sometime we will add the string $x\#f(x)$ to the simulation and then the TM will halt for it. And whenever it does halt, we can just take the part of the input string after #, and that is $f(x)$. We have a way to compute $f(x)$ for any $x$. So, $f$ is computable. The same method would work even if $L_f$ is recursively enumerable and not necessarily recursive. 

So, the correct statements are

  1. If $L_f$ is recursively enumerable $f$ is computable
  2. If $f$ is computable $L_f$ is recursive

So, option B is TRUE but official key was only A. 

Option A is false because $f$ is computable even when $L_f$ is recursively enumerable and not necessarily recursive.

https://cs.stackexchange.com/questions/70626/recursive-language-and-computable-function

edited by
8 votes
8 votes
The question asks what is the reason being f computable.
Since x belongs to A* is a total function, therefore, every alphabet in x will yield some alphabet from B*(in simple words f(x)) if given to a Turing machine.
The question itself says that f is computable if there exists a Turing machine which always halts with output f(x). If any Turing machine has to be always halting that means the language accepted by the Turing machine must be recursive.
In other words A) f is computable if and only if L(f) is recursive.

Option C would have been correct "If f is computable then L(f) is recursive" but due to "but not conversely" sentence it became false.
edited by
4 votes
4 votes
Option A is correct

f is computable if and only if Lf is recursive.

because recursive language have membership algorithm which proves that f is computable while  membership algorithm  not present in recursive enumerable language.
0 votes
0 votes

Its mentioned in the question that f(x) is computable if it halts.

Option A states that f(x) is computable if and only if L(f) is recursive. This means f(x)----→ L(f). And its given that f(x) will halt thus string x#f(x) will be accepted and halted. But now consider the scenario where there is a string x belonging to A* concatenated to any random string of B* , but not to its f(x). In this the TM will either stop or goes infinite loop on rejection. Thus L(x) is recursive enumerable.

edited by
Answer:

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
3