Q39

MCQ2 marks, −0.67

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.

Loading…