458 views
0 votes
0 votes

1 Answer

Best answer
2 votes
2 votes
Rice's theorem 1:

Try to derive two sets of languages one of which wil follow the property and other will not. If you can do so it will be non trivial property of RE set which is undecidable.

set 1 : {01} set 2 : {0011,00001111,000000111111, }  equal 0's and 1's. So it is undecidable

Moreover the set which follow the property is subset of set which does not follow the property making it a non-monotonic property. Hence as per Rice's theorem part 2, it is not even partially decidable.
selected by

Related questions

0 votes
0 votes
0 answers
3
Na462 asked Jan 21, 2019
721 views
0 votes
0 votes
0 answers
4
Ayush Upadhyaya asked Jan 13, 2019
407 views
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...