Difference between revisions of "Automata qn 4"

Revision as of 10:15, 6 August 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 by Arjun Suresh

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