(Examples)
(Examples)
Line 15: Line 15:
 
===Examples===
 
===Examples===
  
<math>L(M)</math> is finite
+
(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> is not Turing recognizable (not recursively enumerable)
 
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> is not Turing recognizable (not recursively enumerable)
  
<math>L(M) = {0}</math>
+
(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)
 
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)
  
<math>L(M)</math> is regular
+
(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)
 
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)
  
<math>L(M)</math> is not regular
+
(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)
+
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)
  
<math>L(M)</math> is infinite
+
(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)
 
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)

Revision as of 00:34, 23 February 2014

Rice's Theorem

Reference

Part 1

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)

Part 2

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

(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> 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)






blog comments powered by Disqus

Rice's Theorem[edit]

Reference

Part 1[edit]

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)

Part 2[edit]

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[edit]

<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> is not Turing recognizable (not recursively enumerable)

<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)

<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)

<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)

<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)






blog comments powered by Disqus