Question 39

Let $f: A^* \to B^*$ be a total function, and let $L_f = \{x \# f(x) \mid x \in A^*\}$.

Direction 1: If $f$ is computable, then $L_f$ is recursive (decidable).
Because $f$ is a computable total function, there exists a Turing machine $M_f$ that always halts and writes $f(x)$ for any input $x \in A^*$.
To decide whether a string $w$ belongs to $L_f$:

1. Check if $w$ matches the format $x \# y$ where $x \in A^*$ and $y \in B^*$. If not, reject.
2. Run $M_f$ on input $x$. Since $f$ is total, $M_f$ always halts with $f(x)$.
3. Compare $y$ with $f(x)$. If $y = f(x)$, accept; otherwise, reject.
   Because $M_f$ always halts, this decision procedure always halts. Thus, $L_f$ is recursive.

Direction 2: If $L_f$ is recursive, then $f$ is computable.
Suppose $L_f$ is recursive with decider $M_{\text{dec}}$. To compute $f(x)$ on input $x$:

1. Enumerate all strings $y \in B^*$ in standard lexicographic order: $y_1, y_2, y_3, \dots$
2. For each string $y_i$, run $M_{\text{dec}}$ on $x \# y_i$.
3. Because $f$ is a total function, there exists exactly one string $y = f(x)$. When $M_{\text{dec}}$ accepts $x \# y_i$, output $y_i$ and halt.
   Because a unique match is guaranteed to exist and testing each candidate halts, this algorithm always halts and produces $f(x)$. Thus, $f$ is computable.

Therefore, $f$ is computable if and only if $L_f$ is recursive.