Rice’s theorem MCQs

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

Rice’s Theorem MCQs
Rice’s theorem states that any non-trivial property of a language accepted by a Turing machine is:

A) Decidable
B) Recognizable
C) Undecidable
D) Context-free
Answer: C

A non-trivial property of Turing machines means that it holds for:

A) All Turing machines
B) No Turing machines
C) Some Turing machines
D) Regular languages
Answer: C

Which of the following is a consequence of Rice’s theorem?

A) Every Turing machine accepts a regular language.
B) Every Turing machine halts on every input.
C) No algorithm can decide whether a Turing machine accepts a non-trivial property.
D) Every Turing machine can be simulated by a finite automaton.
Answer: C

Rice’s theorem implies that the problem of determining whether a Turing machine has a property that applies to some Turing machines and not to others is:

A) Decidable
B) Undecidable
C) Context-free
D) Regular
Answer: B

The set of all Turing machines that accept the same language forms a:

A) Context-free language
B) Regular language
C) Decidable set
D) Non-trivial property
Answer: C

According to Rice’s theorem, the problem of determining whether a Turing machine accepts a language that contains at least one string is:

A) Decidable
B) Undecidable
C) Context-free
D) Regular
Answer: B

Which of the following is an example of a non-trivial property of Turing machines?

A) Having a specific number of states
B) Halting on all inputs
C) Having a finite tape alphabet
D) Having a specific transition function
Answer: A

The set of Turing machines that accept all strings is:

A) Finite
B) Decidable
C) Context-free
D) Not closed under complement
Answer: B

Rice’s theorem applies to:

A) Deterministic finite automata
B) Context-free grammars
C) Turing machines
D) Regular expressions
Answer: C

A Turing machine that accepts all strings forms a:

A) Regular language
B) Context-free language
C) Decidable set
D) Trivial property
Answer: D

 

Related Posts: