Question
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
a.
partial functions
b.
piecewise functions
c.
both a and b
d.
none of the mentioned
Posted under Formal Languages and Automata Theory
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. Fill in the blank with reference to Rice’s theorem. For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that...
Similar Questions
Discover Related MCQs
Q. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
View solution
Q. Which of the following set of computable functions are decidable?
View solution
Q. Which of the following statements are undecidable?
For a given Turing Machine M,
View solution
Q. Post Correspondence problem is
View solution
Q. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a solution is required to start with the first string on each list.
View solution
Q. PCP stands for?
View solution
Q. Can a Modified PCP problem be reduced to PCP?
View solution
Q. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
View solution
Q. If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:
View solution
Q. The value of constants like p and e can be calculated in:
View solution
Q. Which of the following cannot be solved using polynomial time?
View solution
Q. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.
View solution
Q. A generalization of P class can be:
View solution
Q. Which of the following options are correct with reference to P-complete problems?
View solution
Q. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
View solution
Q. Which of the following is a P-complete type of problem?
View solution
Q. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
View solution
Q. What does NP stands for in complexity classes theory?
View solution
Q. The hardest of NP problems can be:
View solution
Q. Which of the following contains NP?
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Formal Languages and Automata Theory? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!
