Arjun Suresh (talk | contribs) (Created page with "==Rice's Theorem== [http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Reference] ===Part 1=== Any non-trivial property about the language recognized by a Turing machine ...") |
Arjun Suresh (talk | contribs) |
||
| Line 4: | Line 4: | ||
Any non-trivial property about the language recognized by a Turing machine is undecidable | Any non-trivial property about the language recognized by a Turing machine is undecidable | ||
| − | For a property to be non-trivial, there should exist at least two Turing machines, the property holding for the language of one (T_{yes}) and not holding for the language of other (T_{no}). | + | For a property to be non-trivial, there should exist at least two Turing machines, the property holding for the language of one (<math>T_{yes}</math>) and not holding for the language of other (<math>T_{no}</math>). |
Thus, as per Rice's theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive) | Thus, as per Rice's theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive) | ||
| Line 11: | Line 11: | ||
Any non-monotonic property about the language recognized by a Turing machine is unrecognizable | Any non-monotonic property about the language recognized by a Turing machine is unrecognizable | ||
| − | For a property to be non-monotonic, there should exist at least two Turing machines, the property holding for the language of one (T_{yes}) and not holding for the language of other (T_{no}) and the language of the T_{yes} a proper subset of the language of | + | For a property to be non-monotonic, there should exist at least two Turing machines, the property holding for the language of one (<math>T_{yes}</math>) and not holding for the language of other (<math>T_{no}</math>) and the language of the <math>T_{yes}</math> a proper subset of the language of <math>T_{no}</math>. |
Examples: | Examples: | ||
| − | L(M) is finite | + | <math>L(M)</math> is finite |
| − | We can have T_{yes} for \phi and T_{no} for \Sigma^*. | + | We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>. |
| − | L(M) = {0} | + | <math>L(M) = {0}</math> |
| − | We can have T_{yes} for {0} and T_{no} for \Sigma^*. | + | We can have <math>T_{yes}</math> for <math>{0}</math> and <math>T_{no}</math> for <math>\Sigma^*</math>. |
| − | L(M) is regular | + | <math>L(M)</math> is regular |
| − | We can have T_{yes} for \phi and T_{no} for \Sigma^*. | + | We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>. |
| − | L(M) is not regular | + | <math>L(M)</math> is not regular |
| − | We can have T_{yes} for {a^nb^n|n\ge0} and T_{no} for \Sigma^*. | + | We can have <math>T_{yes}</math> for <math>{a^nb^n|n\ge0}</math> and <math>T_{no}</math> for <math>\Sigma^*</math>. |
| − | L(M) is infinite | + | <math>L(M)</math> is infinite |
| − | We cannot have T_{yes} and T_{no} such that L(T_{yes}) \subset L(T_{no}). Hence, this is not a non-monotonic property and Rice's 2^{nd} theorem is not applicable. Still this language is not recursively enumerable. | + | We cannot have <math>T_{yes}</math> and <math>T_{no}</math> such that <math>L(T_{yes}) \subset L(T_{no})</math>. Hence, this is not a non-monotonic property and Rice's <math>2^{nd}</math> theorem is not applicable. Still this language is not recursively enumerable. |
Any non-trivial property about the language recognized by a Turing machine is undecidable
For a property to be non-trivial, there should exist at least two Turing machines, the property holding for the language of one (<math>T_{yes}</math>) and not holding for the language of other (<math>T_{no}</math>).
Thus, as per Rice's theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive)
Any non-monotonic property about the language recognized by a Turing machine is unrecognizable
For a property to be non-monotonic, there should exist at least two Turing machines, the property holding for the language of one (<math>T_{yes}</math>) and not holding for the language of other (<math>T_{no}</math>) and the language of the <math>T_{yes}</math> a proper subset of the language of <math>T_{no}</math>.
Examples:
<math>L(M)</math> is finite
We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>.
GATECSE<math>L(M) = {0}</math>
We can have <math>T_{yes}</math> for <math>{0}</math> and <math>T_{no}</math> for <math>\Sigma^*</math>.
<math>L(M)</math> is regular
We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>.
<math>L(M)</math> is not regular
We can have <math>T_{yes}</math> for <math>{a^nb^n|n\ge0}</math> and <math>T_{no}</math> for <math>\Sigma^*</math>.
<math>L(M)</math> is infinite
We cannot have <math>T_{yes}</math> and <math>T_{no}</math> such that <math>L(T_{yes}) \subset L(T_{no})</math>. Hence, this is not a non-monotonic property and Rice's <math>2^{nd}</math> theorem is not applicable. Still this language is not recursively enumerable.
Any non-trivial property about the language recognized by a Turing machine is undecidable
For a property to be non-trivial, there should exist at least two Turing machines, the property holding for the language of one (T_{yes}) and not holding for the language of other (T_{no}).
Thus, as per Rice's theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. (Obviously there are also other languages which are not recursive)
Any non-monotonic property about the language recognized by a Turing machine is unrecognizable
For a property to be non-monotonic, there should exist at least two Turing machines, the property holding for the language of one (T_{yes}) and not holding for the language of other (T_{no}) and the language of the T_{yes} a proper subset of the language of (T_{no}).
Examples:
L(M) is finite
We can have T_{yes} for \phi and T_{no} for \Sigma^*.
L(M) = {0}
We can have T_{yes} for {0} and T_{no} for \Sigma^*.
L(M) is regular
We can have T_{yes} for \phi and T_{no} for \Sigma^*.
L(M) is not regular
We can have T_{yes} for {a^nb^n|n\ge0} and T_{no} for \Sigma^*.
L(M) is infinite
We cannot have T_{yes} and T_{no} such that L(T_{yes}) \subset L(T_{no}). Hence, this is not a non-monotonic property and Rice's 2^{nd} theorem is not applicable. Still this language is not recursively enumerable.