Which formal 7-tuple defines a Deterministic Turing Machine (TM)?
Option C 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}$.
What is the key difference between a Turing-Decidable language (Recursive) and a Turing-Recognizable language (Recursively Enumerable)?
Option A is correct. What is the key difference between a Turing-Decidable language (Recursive) and a Turing-Recognizable language (Recursively Enumerable)? Answer: For a Decidable language, the TM must HALT on all input strings (both accepted and rejected); for a Recognizable language, it may loop infinitely on rejected inputs.
What does the Church-Turing Thesis state?
Option E is correct. None of the options A, B, or C represent the correct answer.
According to Post's Theorem, a language L is Recursive (Decidable) if and only if:
Option B 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).
Alan Turing proved that the Halting Problem (HALT_TM) is UNDECIDABLE using which mathematical proof technique?
Option A is correct. Alan Turing proved that the Halting Problem (HALT_TM) is UNDECIDABLE using which mathematical proof technique? Answer: Cantor's Diagonalization Method.