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) |x ∈ A*}. Which of the following statements is true:

Question

Examsnet · Accepted Answer

Correct Answer is : f is computable if and only if Lf is recursive.

GATE Computer Science (CS) 2017 Shift 1 Solved Paper