Line 1: Line 1:
Consider the following languages:
+
Consider the following languages
  
<math>A=\{M|</math> TM <math>M</math> accepts at most 2 distinct inputs<math>\}</math>
+
<math>A=\{M| TM 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>
+
<math>B=\{M|TM M</math> accepts more than 2 distinct inputs<math>\}</math>
  
 
Identify the correct statement from the following:
 
Identify the correct statement from the following:

Revision as of 19:21, 19 February 2014

Consider the following languages

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

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



blog comments powered by Disqus

Consider the following languages

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

<math>B=\{M|TM 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[edit]



blog comments powered by Disqus