-
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 Lf denote the language {x #f(x)| x ∈ A*}. Which of the following statements is true:
-
- f is computable if and only if Lf is recursive.
- f is computable if and only if Lf is recursively enumerable.
- If f is computable then Lf is recursive, but not conversely.
- If f is computable then Lf is recursively enumerable, but not conversely.
- f is computable if and only if Lf is recursive.
Correct Option: A
A Turing Machine (M) is a recursive if F it halts for every input string either in accept or reject state. Here a computable function is defined in simple way such as { X # f(X) | X ∈ A * }
So, f is computable if and only if Lf is recursive. So, option (a) is correct.
