Difference between revisions of "Automata qn 4"

Revision as of 19:20, 19 February 2014

Consider the following languages:

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

<math>B=\{M|</math> TM <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