Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
Consider the following languages | Consider the following languages | ||
| − | <math>A=\{M | + | <math>A=\{M \mid TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math> |
| − | <math>B=\{M | + | <math>B=\{M \mid TM</math> <math> M</math> accepts more than 2 distinct inputs<math>\}</math> |
Identify the correct statement from the following: | Identify the correct statement from the following: | ||
Consider the following languages
<math>A=\{M \mid TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>
<math>B=\{M \mid 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. Thus, <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 "<math>yes</math>" for "<math>yes</math>" 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 the output "<math>yes</math>" for "<math>yes</math>" 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 \mid TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>
<math>B=\{M \mid 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. Thus, <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 "<math>yes</math>" for "<math>yes</math>" 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 the output "<math>yes</math>" for "<math>yes</math>" 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