GATE CS 2017 Set 1 — Question 39

We need to establish the relationship between the computability of a total function $f$ and the recursiveness of the language $L_f = \{ x \# f(x) \mid x \in A^* \}$.Since $f$ is computable, there exists a Turing Machine $M$ that, given $x$, halts with $f(x)$ on the tape. To decide $L_f$, we can construct a TM $D$ that takes input $w$. $D$ first checks if $w$ is of the form $x \# y$. If not, reject. If yes, it runs $M$ on $x$ to compute $f(x)$. Then it compares the computed $f(x)$ with $y$. If they are identical, accept; otherwise, reject. Since $f$ is total, $M$ always halts, so $D$ always halts. Thus, $L_f$ is recursive.Since $L_f$ is recursive, there is a decider TM $D$ for it. To compute $f(x)$, we can construct a TM $M'$ that takes $x$ as input. $M'$ enumerates all strings $y$ in $B^*$ (e.g., in lexicographical order). For each $y$, it runs $D$ on the string $x \# y$. Since $f$ is a total function, there exists exactly one $y$ such that $y = f(x)$, so $x \# y \in L_f$. Eventually, $D$ will accept for the correct $y$. When $D$ accepts, $M'$ outputs $y$ and halts. Thus, $f$ is computable.Therefore, $f$ is computable if and only if $L_f$ is recursive.