Arjun Suresh (talk | contribs) (→Solution) |
Arjun Suresh (talk | contribs) (→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> | + | <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}} | ||
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
<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.)
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
<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.)
GATECSE