According to the rice’s theorem, If P is a non trivial property, Lp is :
Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
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 property.
A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
Which of the following set of computable functions are decidable?
According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
Which of the following statements are undecidable?
For a given Turing Machine M,
All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
Post Correspondence problem is
Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.
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.
Explanation: The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?
PCP stands for?
PCP or Post Correspondence problem is an undecidable decision problem.
Can a Modified PCP problem be reduced to PCP?
Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
As B is undecidable and it can be reduced to C, C is also an undecidable problem.