Theory of Computation (Automata)
Identify the correct definition of Universal Turing machine.
- A. A class of languages for which a Turing machine will accept and halt on strings in the language, but may not halt on strings outside it.
- B. A Turing machine capable of simulating any other Turing machine given its description and input. ✓
- C. The process of reducing a deterministic finite automaton to the smallest possible number of states while preserving its language.
- D. A set of strings composed of symbols from a defined alphabet.
Correct answer
B. A Turing machine capable of simulating any other Turing machine given its description and input.
Explanation
Universal Turing machine refers to a Turing machine capable of simulating any other Turing machine given its description and input.