Can a Non-deterministic Turing Machine solve any problem that a Deterministic Turing Machine cannot compute?
Option A is correct. Can a Non-deterministic Turing Machine solve any problem that a Deterministic Turing Machine cannot compute? Answer: No, NDTMs and DTMs are equivalent in terms of computability (what can be computed), though NDTMs may solve in fewer steps.
Does adding multiple tapes to a Turing Machine increase its fundamental computability power?
Option C is correct. Does adding multiple tapes to a Turing Machine increase its fundamental computability power? Answer: No, a multi-tape TM can be simulated by a single-tape TM with a quadratic time overhead O(t²).
What is a reduction A \le ₘ B in computability theory used for?
Option B is correct. What is a reduction A \le ₘ B in computability theory used for? Answer: If A reduces to B and A is undecidable, then B MUST also be undecidable.
Which formal grammar type in the Chomsky Hierarchy allows production rules of the form \alpha → \beta where |$\alpha | \le |\beta |$?
Option A is correct. Which formal grammar type in the Chomsky Hierarchy allows production rules of the form \alpha → \beta where |$\alpha | \le |\beta |$? Answer: Type-1 Context-Sensitive Grammar.
Which formal grammar type in the Chomsky Hierarchy has NO restrictions on production rules \alpha → \beta (where \alpha ∈ (V ∪ \Sigma )⁺ and $\beta ∈ (V ∪ \Sigma )*)$?
Option B is correct. Which formal grammar type in the Chomsky Hierarchy has NO restrictions on production rules \alpha → \beta (where \alpha ∈ (V ∪ \Sigma )⁺ and $\beta ∈ (V ∪ \Sigma )*)$? Answer: Type-0 Unrestricted / Recursively Enumerable Grammar.