+1-315-636-4485
+91 98151-74050 
This quiz contains multiple-choice problems on diagonalization, universal languages, Rice’s theorem and properties.
According to Rice’s theorem, If P is a non-trivial property, Lp is
Infinite
Decidable
Undecidable
None of the above
For any non-trivial property of __, no general or effective method can decide whether an algorithm computes it with that property.
Partial functions
Piecewise functions
All of the above
None of the above
Which of the following sets are decidable computable functions?
The class of computable functions that are constant, and its complement
The class of indices for computable functions that are total
The class of indices for recursively enumerable sets that are cofinite
All of the above
Which of the following statements are undecidable for a given Turing machine M?
Does M halt on an empty input tape?
Does M halt for any input at all?
Is L(M) regular? Context-free? Turing decidable?
All of the above
The post correspondence problem is
A decidable decision problem
An undecidable decision problem
Not a decision problem
None of the above
According to Rice's theorem, which of the following options is incorrect?: “Let S be a set of language that is non-trivial such that __”
There exists a TM that recognizes the language in S
There exists a TM that recognizes the language not in S
It is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S or not
All of the above
The difference between PCP and MPCP is that MPCP requires a solution to start with the first string on each list. True or false?
True
False
What does PCP stand for?
Post-correspondence problem
Post-corresponding problem
Pre-correspondence problem
None of the above
Can a modified PCP problem be reduced to PCP?
Yes
No
Consider three decision problems A, B, and C. A is decidable and B is not. Which of the following is a correct option?
C is undecidable if C is reducible to B
C is undecidable if B is reducible to C
C is decidable if A is reducible to C
C is decidable if C is reducible to B’s complement
Decidable is synonymous to
Recursive
Non-recursive
Recognizable
None of the above
Rec-DFA = { | M is a DFA and M recognizes input w}. Rec-DFA is
Undecidable
Decidable
Non finite
None of the above
Which among the following are semi-decidable?
Empty-DFA
Rec-NFA
Infinite-DFA
All of the above
The languages accepted by a Turing machine are called
Recursively enumerable
Recursive
Recursively enumerable and recursive
None of the above
Which among the following are undecidable theories?
The first order theory of Boolean algebra
The first order theory of Euclidean geomentry
The first order theory of hyperbolic geometry
The first order theory of the natural number with addition, multiplication, and equality
