Test: Rice’s Theorem, Properties & PCP - Computer Science Engineering (CSE) MCQ

 Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.

 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.

 According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.

 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.

All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.

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.

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 or Post Correspondence problem is an undecidable decision problem.

 Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.

As B is undecidable and it can be reduced to C, C is also an undecidable problem.