ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: 41d89162
A Deterministic Turing Machine (DTM) differs from a Non-Deterministic Turing Machine (NTM) in that:
A Deterministic Turing Machine (DTM) differs from a Non-Deterministic Turing Machine (NTM) in that:
Multiple Choice Options
- A✓ Correct Option
A DTM has unambiguous, unique state transitions for each configuration
- B
A DTM recognizes a strictly larger class of languages than an NTM
- C
An NTM cannot be simulated by any DTM
- D
A DTM does not use a read/write head
Detailed Technical Solution & Explanation
For any given state and tape symbol, a Deterministic Turing Machine specifies at most one next move (). Hence, its computational path is unambiguous and single-branched.
Option Analysis:
•
Option A (A DTM has unambiguous, unique state t...): Correct. Every configuration has at most one successor.
•
Option B (A DTM recognizes a strictly larger cl...): Incorrect; both recognize the exact same class of languages (recursively enumerable).
•
Option C (An NTM cannot be simulated by any DTM): Incorrect; a DTM can simulate an NTM using breadth-first search of the computation tree.
•
Option D (A DTM does not use a read/write head): Both models utilize tape heads.
Reference: Mock Test 06NEC Licensure Syllabus