Undecidable languages and problems MCQs

By: Prof. Dr. Fazal Rehman Shamil | 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