Back to the 2022 paper

Module 4: Turing Machines (TM)

20222m

A language LL is Turing decidable if:

(i) recursive
(ii) TM recognizes LL
(iii) TM accepts LL
(iv) None of the above

Worked SolutionAI Assisted

Answer

Correct Option: (i) recursive (Turing decidable = recursive)

Explanation

Turing decidable ≡ Recursive language ≡ Decided by a TM that always halts (decider).

Definitions:

  • Recursively Enumerable (RE): TM recognizes LL (accepts if w∈Lw\in L, may loop if $w
    otin L$). Options (ii) “TM recognizes” and (iii) “TM accepts” describe RE, not decidable.
  • Recursive: TM decides LL : for every ww, TM halts and says accept/reject.

So LL is Turing decidable iff LL is recursive.

Decider vs Recognizer distinction is key: recognizer may not halt on rejection.

Final Answer

Decidable = recursive → Option (i).

Similar questions

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.