Which formal 7-tuple defines a Deterministic Turing Machine (TM)?
Option A is correct. Which formal 7-tuple defines a Deterministic Turing Machine (TM)? Answer: (Q, \Sigma , Γ, \delta , q₀, q_{accept}, q_{reject}) where $\delta$: Q $\times Γ → Q \times Γ \times {L, R}$.
Which thesis asserts that any intuitively computable function can be computed by a Turing Machine?
Option C is correct. Which thesis asserts that any intuitively computable function can be computed by a Turing Machine? Answer: Church-Turing Thesis.
According to Post's Theorem, a language L is Recursive (Decidable) if and only if:
Option A is correct. According to Post's Theorem, a language L is Recursive (Decidable) if and only if: Answer: Both L and its complement L̄ are Recursively Enumerable (RE).
What is the Halting Problem (HALT_TM)?
Option D is correct. What is the Halting Problem (HALT_TM)? Answer: Determining whether a Turing Machine M halts on an input string w (Undecidable).
Which mathematical proof technique was used by Alan Turing to prove the undecidability of the Halting Problem?
Option C is correct. Which mathematical proof technique was used by Alan Turing to prove the undecidability of the Halting Problem? Answer: Cantor's Diagonalization Proof.