Undecidable languages and problems MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 23, 2024

MCQs on Undecidable Languages and Problems Which of the following statements about undecidable languages is true? A) Undecidable languages can be recognized by a Turing machine. B) Undecidable languages have a finite number of strings. C) Undecidable languages can be decided by a deterministic finite automaton. D) Undecidable languages cannot be recognized by any Turing machine. Answer: D) Undecidable languages cannot be recognized by any Turing machine. Which classical problem is known to be undecidable? A) The Halting Problem B) Sorting an array of integers C) Finding the shortest path in a graph D) Determining if a number is prime Answer: A) The Halting Problem True or False: Every recursively enumerable language is decidable. A) True B) False Answer: B) False Which theorem states that the Halting Problem is undecidable? A) Church-Turing thesis B) Rice’s theorem C) Gödel’s incompleteness theorem D) Myhill-Nerode theorem Answer: B) Rice’s theorem Which property distinguishes a decidable language from an undecidable one? A) The ability to be recognized by a Turing machine B) The finite number of strings it contains C) The lack of computational complexity D) The ability to determine membership in finite time Answer: D) The ability to determine membership in finite time In the context of formal languages, what does undecidability imply? A) The language is not context-free. B) The language cannot be recognized by any Turing machine. C) The language has an infinite number of strings. D) The language can only be recognized by a non-deterministic Turing machine. Answer: B) The language cannot be recognized by any Turing machine. Which approach is commonly used to prove undecidability of a problem? A) Constructing a deterministic Turing machine B) Showing that the problem has a finite number of solutions C) Reducing the problem to a known undecidable problem D) Using a non-deterministic finite automaton Answer: C) Reducing the problem to a known undecidable problem Which statement best describes the Church-Turing thesis in relation to undecidability? A) It states that every undecidable problem can be solved using a non-deterministic Turing machine. B) It asserts that there are no undecidable problems. C) It proposes that every computable function is decidable. D) It suggests that all decidable languages are recursively enumerable. Answer: C) It proposes that every computable function is decidable. Which of the following is an example of a problem that is undecidable but semi-decidable? A) Finding the shortest path in a graph B) Determining if two regular expressions are equivalent C) Recognizing if a Turing machine halts on all inputs D) Checking if a number is even Answer: C) Recognizing if a Turing machine halts on all inputs Which area of computer science heavily relies on understanding undecidability? A) Database management B) Artificial intelligence C) Network security D) Software engineering Answer: B) Artificial intelligence  

Related Posts:

All Copyrights Reserved 2025 Reserved by T4Tutorials