GATE CS 2017 Set 1 Q39 — Undecidability

To determine the correct statement, we need to analyze the relationship between the computability of the total function $f: A^* \to B^*$ and the decidability (recursiveness) of the language $L_f = \{x \# f(x) \mid x \in A^*\}$.

1. If $f$ is computable, then $L_f$ is recursive (decidable)

If $f$ is computable, there exists a Turing machine $M_f$ that, when given any input $x \in A^*$, always halts with $f(x)$ on its tape.

We can construct a decider $M$ for $L_f$ as follows:

1. Given an input string $w$, first check if it is of the form $x \# y$ where $x \in A^*$ and $y \in B^*$. If not, reject.
2. Run $M_f$ on $x$ to compute $f(x)$. Since $f$ is a total computable function, $M_f$ is guaranteed to halt and produce $f(x)$.
3. Compare the computed $f(x)$ with $y$.
4. If they are identical, accept; otherwise, reject.

Since $M_f$ always halts, the decider $M$ always halts and correctly decides $L_f$. Thus, $L_f$ is recursive.

2. If $L_f$ is recursive, then $f$ is computable

If $L_f$ is recursive, there exists a Turing machine (decider) $M_L$ that halts on all inputs and decides $L_f$.

We can construct a Turing machine $M_f$ to compute $f(x)$ for any input $x \in A^*$ as follows:

1. Given input $x$, systematically generate all strings $y \in B^*$ in lexicographical order ($y_1, y_2, y_3, \dots$).
2. For each generated string $y_i$, run the decider $M_L$ on the input $x \# y_i$.
3. Since $M_L$ is a decider, it always halts and returns either accept or reject.
4. Because $f$ is a total function, there is exactly one unique string $y \in B^*$ such that $y = f(x)$. Thus, $M_L$ is guaranteed to accept $x \# y_i$ for exactly one $y_i$.
5. As soon as $M_L$ accepts $x \# y_i$, halt the process and output $y_i$ on the tape.

Since the correct $y_i$ is guaranteed to be found in finite steps, $M_f$ always halts and correctly computes $f(x)$. Thus, $f$ is computable.

Conclusion

Since both directions hold, $f$ is computable if and only if $L_f$ is recursive.

Therefore, the correct option is A.