Gate CS-2017-1 Question Paper With Solutions

Q. 62 Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in
A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

(A) f if computable if and only if Lf is recursive.

(B) f if computable if and only if Lf is recursive enumerable.

(C) if f is computable then Lf is recursive, but not conversely.

(D) if f is computable then Lf is recursively enumerable, but not conversely.

Answer: (A)

Explanation:

Gate CS-2017-1 Question Paper With Solutions

Learn More:   Gate EE-2004 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here