Difference between revisions of "Automata qn 4"

Revision as of 20:02, 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

Consider <math>A</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.

Now, consider <math>B</math>. <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 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.

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

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