ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 3781e00a
A language is recognized by a Turing Machine (recursively enumerable), but what guarantees that a Turing Machine will halt on every input string?
A language is recognized by a Turing Machine (recursively enumerable), but what guarantees that a Turing Machine will halt on every input string?
Multiple Choice Options
- A
If the language is non-recursively enumerable
- B✓ Correct Option
If the language is recursive (decidable)
- C
If the language is context-sensitive only
- D
If the language cannot be enumerated
Detailed Technical Solution & Explanation
A language is 'recursive' (or decidable) if and only if there exists a Turing Machine (a decider) that halts on all inputs, accepting strings in and rejecting strings not in . If a language is merely recursively enumerable (Turing-recognizable), the TM is only guaranteed to halt on strings in ; it may loop indefinitely on strings not in .
Option Analysis:
•
Option A (If the language is non-recursively en...): Such languages cannot even be recognized by any TM.
•
Option B (If the language is recursive (decidable)): Correct. A recursive language guarantees a halt on all input strings.
•
Option C (If the language is context-sensitive ...): While CSLs are decidable, the broader formal class guaranteeing halting is the recursive languages.
•
Option D (If the language cannot be enumerated): Uncountable/unrecognizable languages have no TM.
Reference: Mock Test 03NEC Licensure Syllabus