Let \(A\) and \(B\) be finite alphabets and let # be a symbol outside both…
2017
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 47 students.
Show answer & explanation
Correct answer: A
Key insight: L_f is exactly the graph of the total function f, so membership tests and reconstruction of outputs are effective in both directions.
If f is computable then L_f is recursive: on input x#y compute f(x) (the machine halts) and accept iff y = f(x). This decides membership in L_f.
If L_f is recursive then f is computable: to compute f(x), enumerate all z in B* (e.g. by length-lexicographic order) and use the decider for L_f to test x#z; since f is total there exists z = f(x) and the search halts with that z.
If f is computable then L_f is recursively enumerable by enumerating x and outputting x#f(x). Conversely, if L_f is r.e. and f is total, dovetail the enumerator until it outputs some pair with first component x; that yields f(x). Therefore r.e. of L_f already suffices to compute f, and in this situation r.e. and decidability coincide for the graph.
Conclusion: f is computable if and only if L_f is recursive; equivalently, f is computable if and only if L_f is recursively enumerable (for graphs of total functions these two properties coincide).