GATE CS 2017 (Forenoon) — Question 39

Theory of Computation (TOC)Turing Machines & UndecidabilityMCQ2 marks · −2/3 if wrongMedium

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) \mid x \in A^*\}\). Which of the following statements is true:
  1. A
    \(f\) is computable if and only if \(L_f\) is recursive.
  2. B
    \(f\) is computable if and only if \(L_f\) is recursively enumerable.
  3. C
    If \(f\) is computable then \(L_f\) is recursive, but not conversely.
  4. D
    If \(f\) is computable then \(L_f\) is recursively enumerable, but not conversely.
Practise the full 2017-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group