(Solution)
(Solution)
Line 18: Line 18:
  
 
===Solution===
 
===Solution===
<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs <math>"yes"</math> for <math>"yes"</math> cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>A</math> is not Turing recognizable.  
+
<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for <math>"yes"</math> cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>A</math> is not Turing recognizable.  
  
Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs <math>"yes"</math> for <math>"yes"</math> cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use [http://www.xamuel.com/dovetailing/ dovetailing] technique so that even if some string causes TM to loop forever, we can continue progress).  If M is accepting more than 2 distinct inputs we are sure that we'll  encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence B is Turing recognizable.  
+
Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs <math>"yes"</math> for <math>"yes"</math> cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use [http://www.xamuel.com/dovetailing/ dovetailing] technique so that even if some string causes <math>TM</math> to loop forever, we can continue progress).  If <math>M</math> is accepting more than 2 distinct inputs we are sure that we'll  encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>B</math> is Turing recognizable.  
  
(It's easier to see that A and B are complement to each other. TM can say "yes" for "yes" cases of B means it can say "no" for "no" cases of A. But to make A Turing recognizable we need "yes" for " yes" cases of A, which is not the case here. )
+
(It's easier to see that <math>A</math> and <math>B</math> are complement to each other. <math>TM</math> can say "yes" for "yes" cases of <math>B</math> means it can say "no" for "no" cases of <math>A</math>. But to make <math>A</math> Turing recognizable we need "yes" for " yes" cases of <math>A</math>, which is not the case here. )
  
(Once we prove that B is Turing recognizable but not Turing acceptable (recursive), there is no need to check for A. The complement of a Turing recognizable but not Turing acceptable language is always not Turing recognizable.)
+
(Once we prove that <math>B</math> is Turing recognizable but not Turing acceptable (recursive), there is no need to check for <math>A</math>. The complement of a Turing recognizable but not Turing acceptable language is always not Turing recognizable.)
  
 
{{Template:FBD}}
 
{{Template:FBD}}

Revision as of 20:04, 19 February 2014

Consider the following languages

<math>A=\{M| TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>

<math>B=\{M|TM</math> <math> M</math> accepts more than 2 distinct inputs<math>\}</math>

Identify the correct statement from the following:

(A) <math>A</math> is Turing recognizable <math>B</math> is not Turing recognizable

(B) <math>B</math> is Turing recognizable <math>A</math> is not Turing recognizable

(C) Both <math>A</math> and <math>B</math> are Turing recognizable

(D) Neither <math>A</math> nor <math>B</math> is Turing recognizable


Solution

<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for <math>"yes"</math> cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>A</math> is not Turing recognizable.

Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs <math>"yes"</math> for <math>"yes"</math> cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use dovetailing technique so that even if some string causes <math>TM</math> to loop forever, we can continue progress). If <math>M</math> is accepting more than 2 distinct inputs we are sure that we'll encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>B</math> is Turing recognizable.

(It's easier to see that <math>A</math> and <math>B</math> are complement to each other. <math>TM</math> can say "yes" for "yes" cases of <math>B</math> means it can say "no" for "no" cases of <math>A</math>. But to make <math>A</math> Turing recognizable we need "yes" for " yes" cases of <math>A</math>, which is not the case here. )

(Once we prove that <math>B</math> is Turing recognizable but not Turing acceptable (recursive), there is no need to check for <math>A</math>. The complement of a Turing recognizable but not Turing acceptable language is always not Turing recognizable.)




blog comments powered by Disqus

Consider the following languages

<math>A=\{M| TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>

<math>B=\{M|TM</math> <math> M</math> accepts more than 2 distinct inputs<math>\}</math>

Identify the correct statement from the following:

(A) <math>A</math> is Turing recognizable <math>B</math> is not Turing recognizable

(B) <math>B</math> is Turing recognizable <math>A</math> is not Turing recognizable

(C) Both <math>A</math> and <math>B</math> are Turing recognizable

(D) Neither <math>A</math> nor <math>B</math> is Turing recognizable


Solution[edit]

<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for <math>"yes"</math> cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>A</math> is not Turing recognizable.

Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs <math>"yes"</math> for <math>"yes"</math> cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use dovetailing technique so that even if some string causes <math>TM</math> to loop forever, we can continue progress). If <math>M</math> is accepting more than 2 distinct inputs we are sure that we'll encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output <math>"yes"</math> for <math>"yes"</math> cases of the language and hence <math>B</math> is Turing recognizable.

(It's easier to see that <math>A</math> and <math>B</math> are complement to each other. <math>TM</math> can say "yes" for "yes" cases of <math>B</math> means it can say "no" for "no" cases of <math>A</math>. But to make <math>A</math> Turing recognizable we need "yes" for " yes" cases of <math>A</math>, which is not the case here. )

(Once we prove that <math>B</math> is Turing recognizable but not Turing acceptable (recursive), there is no need to check for <math>A</math>. The complement of a Turing recognizable but not Turing acceptable language is always not Turing recognizable.)




blog comments powered by Disqus