ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: c836f5b0
What is the defining capability of a Universal Turing Machine (UTM)?
What is the defining capability of a Universal Turing Machine (UTM)?
Multiple Choice Options
- A
It runs in strictly constant memory space
- B
It operates using only a single finite state
- C✓ Correct Option
It can simulate the execution of any arbitrary Turing Machine given its description and input string
- D
It is restricted to recognizing regular expressions only
Detailed Technical Solution & Explanation
A Universal Turing Machine (UTM, conceived by Alan Turing in 1936) is an abstract programmable computer. It takes an encoded description of any target Turing machine and an input string on its tape, and faithfully simulates the step-by-step execution of on .
Option Analysis:
•
Option A (It runs in strictly constant memory s...): Constant memory characterizes finite automata, not UTMs.
•
Option B (It operates using only a single finit...): UTMs have multiple states.
•
Option C (It can simulate the execution of any ...): Correct. Foundational definition of a Universal Turing Machine.
•
Option D (It is restricted to recognizing regul...): UTMs compute all Turing-computable functions.
Reference: Demo2 · Set 1NEC Licensure Syllabus