Arjun Suresh (talk | contribs) (→Examples) |
Arjun Suresh (talk | contribs) |
||
| Line 11: | Line 11: | ||
(1) <math>L(M)</math> has at least 10 strings | (1) <math>L(M)</math> has at least 10 strings | ||
| − | This is a non-trivial property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. | + | This is a non-trivial property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively) |
(2) <math>L(M)</math> has at most 10 strings | (2) <math>L(M)</math> has at most 10 strings | ||
| − | This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. | + | This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively) |
(3) <math>L(M)</math> is recognized by a <math>TM</math> having even number of states | (3) <math>L(M)</math> is recognized by a <math>TM</math> having even number of states | ||
| Line 23: | Line 23: | ||
(4) <math>L(M)</math> is a subset of <math>\Sigma^{*}</math> | (4) <math>L(M)</math> is a subset of <math>\Sigma^{*}</math> | ||
| − | This is a trivial property. All languages are subset of <math>\Sigma^{*}</math> and hence this set | + | This is a trivial property. All languages are subset of <math>\Sigma^{*}</math> and hence this set contains all languages including all recursively enumerable languages. |
==Part 2== | ==Part 2== | ||
| Line 51: | Line 51: | ||
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 <math>L = \{M| L(M)</math> is infinite <math>\}</math> is not Turing recognizable (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 <math>L = \{M| L(M)</math> is infinite <math>\}</math> is not Turing recognizable (not recursively enumerable) | ||
| + | |||
| + | (6) <math>L(M)</math> has at least 10 strings | ||
| + | |||
| + | This is a non-monotonic property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively) | ||
| + | |||
| + | (7) <math>L(M)</math> has at most 10 strings | ||
| + | |||
| + | This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively) | ||
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)
(1) <math>L(M)</math> has at least 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively)
(2) <math>L(M)</math> has at most 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively)
(3) <math>L(M)</math> is recognized by a <math>TM</math> having even number of states
This is a trivial property. This set equals the set of recursively enumerable languages.
(4) <math>L(M)</math> is a subset of <math>\Sigma^{*}</math>
This is a trivial property. All languages are subset of <math>\Sigma^{*}</math> and hence this set contains all languages including all recursively enumerable languages.
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> must be a proper subset of the language of <math>T_{no}</math>.
(1) <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>. Hence, <math>L = \{M| L(M)</math> is finite<math>\}</math> is not Turing recognizable (not recursively enumerable)
(2) <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>. Hence, <math>L = \{M| L(M) = \{0\}\}</math> is not Turing recognizable (not recursively enumerable)
(3) <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>. Hence, <math>L = \{M| L(M)</math> is regular <math>\}</math> is not Turing recognizable (not recursively enumerable)
(4) <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>. Hence, <math>L = \{M| L(M)</math> is not regular<math>\}</math> is not Turing recognizable (not recursively enumerable)
(5) <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 <math>L = \{M| L(M)</math> is infinite <math>\}</math> is not Turing recognizable (not recursively enumerable)
(6) <math>L(M)</math> has at least 10 strings
This is a non-monotonic property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively)
(7) <math>L(M)</math> has at most 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively)
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)
(1) <math>L(M)</math> has at least 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively)
(2) <math>L(M)</math> has at most 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively)
(3) <math>L(M)</math> is recognized by a <math>TM</math> having even number of states
This is a trivial property. This set equals the set of recursively enumerable languages.
(4) <math>L(M)</math> is a subset of <math>\Sigma^{*}</math>
This is a trivial property. All languages are subset of <math>\Sigma^{*}</math> and hence this set contains all languages including all recursively enumerable languages.
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> must be a proper subset of the language of <math>T_{no}</math>.
(1) <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>. Hence, <math>L = \{M| L(M)</math> is finite<math>\}</math> is not Turing recognizable (not recursively enumerable)
(2) <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>. Hence, <math>L = \{M| L(M) = \{0\}\}</math> is not Turing recognizable (not recursively enumerable)
(3) <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>. Hence, <math>L = \{M| L(M)</math> is regular <math>\}</math> is not Turing recognizable (not recursively enumerable)
(4) <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>. Hence, <math>L = \{M| L(M)</math> is not regular<math>\}</math> is not Turing recognizable (not recursively enumerable)
(5) <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 <math>L = \{M| L(M)</math> is infinite <math>\}</math> is not Turing recognizable (not recursively enumerable)
(6) <math>L(M)</math> has at least 10 strings
This is a non-monotonic property. We can have <math>T_{yes} = \Sigma^*</math> and <math>T_{no} = \phi</math>. Hence, <math>L = \{M| L(M)</math> has at least 10 strings<math>\}</math> is not Turing decidable (not recursively)
(7) <math>L(M)</math> has at most 10 strings
This is a non-trivial property. We can have <math>T_{yes} = \phi</math> and <math>T_{no} = \Sigma^*</math>. Hence, <math>L = \{M| L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursively)
GATECSE