(Examples)
(Examples)
 
(47 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Rice's Theorem=
+
<metadesc>Rice's theorem examples, Examples of undecidable and unrecognizable languages</metadesc>
 +
 
 +
==Some Confusing Terms==
 +
===Language Decided===
 +
We say a TM decide a language L if it accepts all strings in L and rejects all strings not in L.
 +
 
 +
===Language Recognized===
 +
We say a TM recognizes language L if it accepts all strings in L. It may or may not reject any string not in L- i.e., it might go into an infinite loop in case of non-acceptance. (It will never accept a string not in L)
 +
<!--
 +
===Language Accepted (Not a standard one)===
 +
We say a TM accepts a language (i.e., a set of strings) L, if all strings in L are accepted. For strings not in L, they can either be accepted or rejected or can cause infinite loop. (It might accept a string not in L).
 +
 
 +
(This definition is not standard but just using it to explain cases where we say TM M accepts {0,00} etc. You shouldn't define Turing acceptable language like this as this definition makes any language Turing acceptable)-->
 +
 
 +
==Rice's Theorem==
 
[http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Reference]
 
[http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Reference]
==Part 1==
+
==Part 1 (For some undecidable languages)==
  Any non-trivial property about the language recognized by a Turing machine is undecidable
+
  Any non-trivial property of the LANGUAGE recognizable 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>).
 
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>).
Line 8: Line 22:
 
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)
  
==Part 2==
+
===Examples===
  Any non-monotonic property about the language recognized by a Turing machine is unrecognizable
+
(1) <math>L(M)</math> has at least 10 strings
 +
 
 +
We can have <math>T_{yes}</math> for <math>\Sigma^*</math> and <math>T_{no}</math> for <math>\phi</math>. Hence, $L = \left\{M \mid L(M) \text{ has at least 10 strings}\right\}$ is not Turing decidable (not recursive). (Any other $T_{yes}$ and $T_{no}$ would also do. $T_{yes}$ can be any TM which accepts at least 10 strings and $T_{no}$ any TM which doesn't accept at least 10 strings )
 +
 
 +
(2) <math>L(M)</math> has at most 10 strings
 +
 
 +
We can have <math>T_{yes}</math> for <math>\phi</math>  and <math>T_{no}</math> for <math>\Sigma^*</math>. Hence, <math>L = \{M\mid  L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursive).
 +
 
 +
(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>
  
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>.
+
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 (For some unrecognizable languages)==
 +
Any non-monotonic property of the LANGUAGE recognizable 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 <math>T_{yes}</math> must be a proper subset of the language of <math>T_{no}</math>.
  
 
===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> (<math>\phi \subset \Sigma^*</math>). Hence, <math>L = \{M\mid 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>  (<math>\{0\} \subset \Sigma^*</math>). Hence, <math>L = \{M\mid L(M) = \{0\}\}</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)
+
(3) <math>L(M)</math> is regular
  
<math>L(M) = {0}</math>
+
We can have <math>T_{yes}</math> for <math>\phi</math> and  <math>T_{no}</math> for any non-regular language. Hence, <math>L = \{M\mid  L(M)</math> is regular<math>\}</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)
+
(4) <math>L(M)</math> is not regular
  
<math>L(M)</math> is regular
+
We can have <math>T_{yes}</math> for <math>\{a^nb^n\mid n\ge0\}</math> and  <math>T_{no}</math> for <math>\Sigma^*</math> (<math>\{a^nb^n\mid n\ge0\}\subset \Sigma^*</math>). Hence, <math>L = \{M\mid  L(M)</math> is not 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)
+
(5) <math>L(M)</math> is infinite
  
<math>L(M)</math> is not regular
+
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\mid  L(M)</math> is infinite <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)
+
(6) <math>L(M)</math> has at least 10 strings
  
<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.
 +
 
 +
This language is in fact Turing recognizable. [[Automata_qn_4| See here]]
 +
 
 +
(7) <math>L(M)</math> has at most 10 strings
 +
 
 +
We can have <math>T_{yes}</math> for <math>\phi</math>  and <math>T_{no}</math> for <math>\Sigma^*</math>(<math>\phi \subset \Sigma^*</math>). Hence, <math>L = \{M\mid  L(M)</math> has at most 10 strings<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)
 
  
  
Line 42: Line 84:
 
{{Template:FBD}}
 
{{Template:FBD}}
  
[[Category: Automata Theory]]
+
[[Category: Automata Theory Notes]]
 +
 
  
[[Category:Notes & Ebooks for GATE Preparation]]
+
[[Category: Compact Notes for Reference of Understanding]]

Latest revision as of 09:58, 24 August 2015


Some Confusing Terms

Language Decided

We say a TM decide a language L if it accepts all strings in L and rejects all strings not in L.

Language Recognized

We say a TM recognizes language L if it accepts all strings in L. It may or may not reject any string not in L- i.e., it might go into an infinite loop in case of non-acceptance. (It will never accept a string not in L)

Rice's Theorem

Reference

Part 1 (For some undecidable languages)

Any non-trivial property of the LANGUAGE recognizable 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)

Examples

(1) <math>L(M)</math> has at least 10 strings

We can have <math>T_{yes}</math> for <math>\Sigma^*</math> and <math>T_{no}</math> for <math>\phi</math>. Hence, $L = \left\{M \mid L(M) \text{ has at least 10 strings}\right\}$ is not Turing decidable (not recursive). (Any other $T_{yes}$ and $T_{no}$ would also do. $T_{yes}$ can be any TM which accepts at least 10 strings and $T_{no}$ any TM which doesn't accept at least 10 strings )

(2) <math>L(M)</math> has at most 10 strings

We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>. Hence, <math>L = \{M\mid L(M)</math> has at most 10 strings<math>\}</math> is not Turing decidable (not recursive).

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

Part 2 (For some unrecognizable languages)

Any non-monotonic property of the LANGUAGE recognizable 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 <math>T_{yes}</math> must be 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> (<math>\phi \subset \Sigma^*</math>). Hence, <math>L = \{M\mid 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> (<math>\{0\} \subset \Sigma^*</math>). Hence, <math>L = \{M\mid 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 any non-regular language. Hence, <math>L = \{M\mid 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\mid n\ge0\}</math> and <math>T_{no}</math> for <math>\Sigma^*</math> (<math>\{a^nb^n\mid n\ge0\}\subset \Sigma^*</math>). Hence, <math>L = \{M\mid 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\mid L(M)</math> is infinite <math>\}</math> is not Turing recognizable (not recursively enumerable)

(6) <math>L(M)</math> has at least 10 strings

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.

This language is in fact Turing recognizable. See here

(7) <math>L(M)</math> has at most 10 strings

We can have <math>T_{yes}</math> for <math>\phi</math> and <math>T_{no}</math> for <math>\Sigma^*</math>(<math>\phi \subset \Sigma^*</math>). Hence, <math>L = \{M\mid L(M)</math> has at most 10 strings<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