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

can you please provide some link for the same i am unable to understand the concept used here...thanks!!

---

Actually there isn't any concept used in the answer other than the definition of recursive and recursively enumerable languages.

Recursive language: TM for it should be able to say "yes" for any word in L and say "no" for any word not in L. Such languages describe decidable problems.

Recursively enumerable language: TM for it must be able to say "yes" for any word in L but may or may not say "no" for any word not in L. (Obviously it should never say "yes" for any word not in L, it can only loop forever or say "no"). Such languages decide partially decidable problems.

You can see here for Rice's theorem which is useful for many such questions:

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

---

Is the following explanation correct ??

For A,

T_yes = ∅

T_no = Σ^∗ and T_yes ⊂ T_no

_{So A is not Turing recognizable.} 

_{And as B is complement of A, So we can say B is turing recognizable.}

---

For A it is fine- not Turing recognizable. But complement of not Turing recognizable can be either Turing recognizable or not.

---

Sir can we use Rice Theorem for Machine B? If yes then how?

Cant we use dovetailing in machine A as we used in B?

---

@Arjun sir so B is under loop until it gets 2 distinct string.

After getting 2 distinct string it can say "yes" for all "yes" cases of input string. right?

But why cannot say "no" answer for "no" cases

---

yes, that is correct. Because there are inifnite possible strings and there is no way we can reduce this, we can never be sure, when to say "no".

---

then we could say "no" for first two string for which it is under loop

---

No. Because the TM is in infinite loop and even it doesn't know that its in infinite loop. i.e., it is hoping the loop will eventually exist- which may or may not happen. It is this reason why we cannot decide if a TM can accept any given word $w$.

---

if A say yes on Yes then it is Turing recognizable

if not pls explain @Arjun sir

http://math.stackexchange.com/questions/25802/recognizable-vs-decidable

---

If a TM says "yes" for every "yes" instance of the problem, then the problem is Turing recognizable.

---

What is dovetailing method ? The above link is not working for me

---

@Arjun Sir ur last paragraph of your ans contradicts with this

Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable.

means in gatecse u mentioned Turing acceptable as REL but ur ans here saying that Turing Acceptable is Recursive...Which one is correct??

reference:-http://gatecse.in/identify-the-class-of-a-given-language/

---

yes, "acceptable" is not the correct word. Corrected now..

---

@Arjun Sir,

Please if A can hang while checking for 2 distinct inputs,then why cant B machine hang?

Why cant we use same enumeration procedure for A so that it will not hang?

---

"We should use [ dovetailing][1] technique so that even if some string causes TM to loop forever, we can continue progress".Will this not work for A??

if yes then A should be R.E language.

if not then WHY??

---

Arjun sir,please clear doubts on last two comments

---

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

How will the TM halt after some finite steps for a string that comes infinitely long after strings of small length such as 1 or 100?

---

infinity means never ending- given a string length say $k$, there are only finite number of strings which are of lower length, however large $k$ is.

---

All right, understood. Thank you for your efforts on this website.

---

@Arjun sir.

1. For Turing Machine A

 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

Even if machine does not hang,still we can't say yes.Beccause to say yes i need to check all the strings and that would be infinite and so it is NOT RE. Is it correct understanding?

2.I have not read dovetailing method but if we can continue progress with this method in hang case,then why cant we apply in this case?Is this because that hanged string might get accepted?Because this would not hurt B machine but it will hurt A.

---

Even if machine does not hang,still we can't say yes.Beccause to say yes i need to check all the strings and that would be infinite and so it is NOT RE. Is it correct understanding?

yes

2.I have not read dovetailing method but if we can continue progress with this method in hang case,then why cant we apply in this case?

dovetailing ensures progress but some problems can continue without end as the number of possible strings are infinite

Is this because that hanged string might get accepted?Because this would not hurt B machine but it will hurt A.

I guess you meant it different: for A, there is no particular string or a set of FINITE strings which can be used to say "yes" even after using dovetailing. So, even if we have progress and uses many strings as input we can never say "yes". 

---

Got it.Because we have infinite strings and we can never say yes,because even if  it is less than 2 strings right now,in future it may accept more.

---

Yes, Apply it and you will get most of these questions correct.

---

@Arjun sir: $B$ will be Turing Recognizable .But i want to know that $B$ is Turing Decidable or not i.e Recursive .For this i have to use Rice theorem $1$and have to prove that $B$ is a trivial property or  a non trivial.I Think it is non trivial .How ? i can have 2 TM for both $T_{yes}$ and $T_{no}$

---

$T_{yes}$-:T.M accepting atleast 6 string.

$T_{No}$-:T.M accepting  $\phi$.

Hence it is non trival $\Rightarrow$B is Turing  undecidable i.e not recursive.

---

For $A$, as $A$ is not even Turing recognizable , there is no question about its turing decidablity.

Am i correct @arjun sir?

---

The link is not working

---

see this https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_24.pdf

---

@sourav yes you're correct.

---

@arjun sir , thanks a lot for your clarification.But sir sometimes i get comfused in Rice theorem  part-:2,

like here https://gateoverflow.in/151057/langle-rangle-there-exist-input-whose-length-than-which-halts%24#c151084

Please help me out!

---

Can somebody please explain the second part, that how B is turing recognizable?

---

@ Sumaiya23

you can analyse this question like this:- 

given that A,B are the encoding of machine ....means collection different Turing Machine in 0/1 form...

for A. let consider a turing machine M'....taken a input from A(i.e a TM) and placed in M'...now if u given any input string then you can not gauranteed of haulting (becoz every M not accept more than 2)....

for B. same ...but in this case if you put any string input then it will hault....(becoz accept more than two)

Turing recognizable:- for which you can build a TM which hault on all input from that language but for string out of that languge it may or may not:-

---

@ Arjun  Sir ,if i have L1=NOT RE and L2=RE and L= L1 intersects L2,, than what can we say about the behavior of L and L'?

---

Both will be some languages - nothing more than that.

---

ok sir

---

if want to write Tyes nad Tno for A then what would it be?....i know that we cannot apply rice theorem but silll??

---

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