Rice's Theorem with Examples - Revision history

Arjun Suresh: /* Examples */

2015-08-24T09:58:04Z

‎Examples

2015-05-25T16:23:27Z

‎Language Decided

2015-05-25T16:21:55Z

2015-05-25T15:58:27Z

‎Language Accepted (Not a standard one)

2015-05-25T15:53:07Z

‎Language Accepted

2015-05-25T15:22:48Z

‎Language Accepted

2015-05-05T12:20:40Z

‎Part 2 (For some unrecognizable languages

2015-05-05T12:20:01Z

‎Part 1 (For some undecidable languages)

2015-03-09T13:50:53Z

‎Examples

2015-03-09T13:47:00Z

‎Examples

← Older revision		Revision as of 09:58, 24 August 2015
Line 74:		Line 74:
	(7) <math>L(M)</math> has at most 10 strings		(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 ~~decidable~~ (not ~~recursive~~)	+	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)
		+

@@ Line 3: / Line 3: @@
 ==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
+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)

@@ Line 6: / Line 6: @@
 ===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)
+(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==

@@ Line 9: / Line 9: @@
 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. )
+(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==

@@ Line 6: / Line 6: @@
 ===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===
+===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).
 ==Rice's Theorem==

@@ Line 35: / Line 35: @@
 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==
+==Part 2 (For some unrecognizable languages)==
-  Any non-monotonic property about the LANGUAGE recognized by a Turing machine is unrecognizable
+  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>.

@@ Line 12: / Line 12: @@
 [http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Reference]
 ==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>).

@@ Line 21: / Line 21: @@
 (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)
+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