Yioop - PHP Search Engine

[ Prev ]

2020-05-12

-- Practice Final Thread

Group 6 : Prajesh , Nick, Tyler

Problem 10 :

To use Rice Theorem,

  1. Language  L  is non trivial 
  2. Assume  that whenever we have 2 machines M1 and M2 such that L(M1) = L(M2) meaning that both the language are either in L or they are both not in L.

Let A = {<M> | L(M) = set of strings written in ASCII as Professor Pollet would call solutions to this problem }

Since there exist some TM which’d accept strings that are solution to the problem and some which doesn’t accept the string that are solution to the problem. Hence condition 1 is satisfied. Suppose there exist M1 and M2 , both of which recognizes the language, then the two TMs either both are in the L or they are not in L.This satisfies the condition 2 .

Therefore , by Rice theorm , the TM which correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.

Group 6 : Prajesh , Nick, Tyler Problem 10 : To use Rice Theorem, 1. Language L is non trivial 2. Assume that whenever we have 2 machines M1 and M2 such that L(M1) = L(M2) meaning that both the language are either in L or they are both not in L. Let A = {<M> | L(M) = set of strings written in ASCII as Professor Pollet would call solutions to this problem } Since there exist some TM which’d accept strings that are solution to the problem and some which doesn’t accept the string that are solution to the problem. Hence condition 1 is satisfied. Suppose there exist M1 and M2 , both of which recognizes the language, then the two TMs either both are in the L or they are not in L.This satisfies the condition 2 . Therefore , by Rice theorm , the TM which correctly accepts the same strings written in ASCII as Professor Pollett would call solutions to this problem is undecidable.

-- Practice Final Thread

((resource:practice final 10.PNG|Resource Description for practice final 10.PNG))