The GATE Grind

GATE 2017 CS – Question 49

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

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 $\{x \# f(x) \mid x \in A^*\}$. 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.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $f$ is computable if and only if $L_f$ is recursive.

Explanation

If $f$ is computable, a machine can compute $f(x)$ from the part before $\#$ and compare it with the part after, so $L_f$ is recursive. Conversely, if $L_f$ is recursive, we can try each string $y$ in turn until $x \# y$ is accepted, and since $f$ is total this always ends, so $f$ is computable. So the two are equivalent.