Question

Let A and B be finte 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_1$ denote the language {x # f(x) | x $ϵ$ A*}. Which of the following statements is true:

• A. If f is computable then L_f is recursively enumerable, but not conversely.
• B. f is computable if and only if L_f is recursive.
• C. If f is computable then L_f is recursive, but not conversely.
• D. f is computable if and only if L_f is recursively enumerable.

Answer 1

The correct option is B

f is computable if and only if L_f is recursive.

Since the way computable is defined based on halting TM,it means computable is same as Recursive.
So,clearly f is computable iff $L_f$ is recursive.

Since the way computable is defined based on halting TM, it means computable is same as Recursive.
So, clearly f is computable iff L_f is recursive.