Question

Consider the following languages

$A=\left\{ \langle M\rangle \mid \text{ TM M accepts at most 2 distinct inputs} \right\}$

$B=\left\{\langle M \rangle \mid \text{ TM M accepts more than 2 distinct inputs} \right\}$

Identify the correct statement from the following:

• A. $A$ is Turing recognizable $B$ is not Turing recognizable
• B. $B$ is Turing recognizable $A$ is not Turing recognizable
• C. Both $A$ and $B$ are Turing recognizable
• D. Neither $A$ nor $B$ is Turing recognizable

Comments

Answer is B

---

Why cant we use dovetailing method so that machine doesnt go to infinite loop and check until atmost two distinct strings are there in the language?

---

@Umair You need to check whether the TM accepts at most two distinct strings i.e., at max two distinct strings. Since there are infinite no. of strings possible, how will you say that the TM doesn’t accept all these and it only accepts at max two distinct strings and not more than that. Dovetailing ensures progress, but here it will continue without end   

Answer 1

B is the answer- A is not Turing recognizable while B is Turing recognizable.

A is Turing recognizable if TM for A, say $T_A$ outputs "yes" for "yes" cases of A- i.e.; when M accepts at most 2 distinct inputs. But M 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, $T_A$ may not output "yes" for "yes" cases of the language and hence A is  not Turing recognizable.

Similarly, B is Turing recognizable if TM for B, say $T_B$ outputs "yes" for "yes" cases of B- i.e.; when M accepts more than 2 distinct inputs. If M 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 M. (We should use [ dovetailing][1] 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 TM. Thus $T_B$ can always output "yes" for "yes" 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 the output "yes" for "yes" cases of A, which is not the case here. )

(Once we prove that B is Turing recognizable but not Turing decidable (recursive), there is no need to check for A. The complement of a Turing recognizable but not Turing decidable language is always not Turing recognizable.)

  [1]: http://www.xamuel.com/dovetailing/

Comments

@ Arjun Sir, Can we apply here Rice theorem 2 here or not and if how?

---

You said that A is complement of B.

A is the Encoding of TM in form of 0`s and 1's and B is also Encoding of TM in 0's and 1's

Complete of B contain two things:

1. Encoding of TM equal to or less than 2 inputs.

2. 0`s ans 1`s that do not represent any TM

Clearly A(Encoding of TM equal to or less than 2 inputs) is not complement of B

---

But M can loop forever without accepting more than 2 distinct inputs 

@Arjun sir, in 4^th line of the answer shouldn’t it be “without accepting at most 2 distinct inputs” instead of “without accepting more than 2 distinct inputs?. Please correct me if i misunderstood this.