Let $A$ and $B$ be finite alphabets and let # be a symbol outside both…

GATE · 2017 · CS · Set 1 · Computer Science & IT

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 $\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.

Attempted by 72 students.

Explore the full course: Gate Guidance By Sanchit Sir

Let \(A\) and \(B\) be finite alphabets and let # be a symbol outside both…