search
Log In
23 votes
4.8k views

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:

  1. $A$ is Turing recognizable $B$ is not Turing recognizable
  2. $B$ is Turing recognizable $A$ is not Turing recognizable
  3. Both $A$ and $B$ are Turing recognizable
  4. Neither $A$ nor $B$ is Turing recognizable
in Theory of Computation
edited by
4.8k views
0
Answer is B
0
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?

1 Answer

40 votes
 
Best answer
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/

edited by
0
Arjun sir,please clear doubts on last two comments
0

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

0
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.
2
All right, understood. Thank you for your efforts on this website.
1

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

0

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

2
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.
0
Yes, Apply it and you will get most of these questions correct.
4

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

0
The link is not working
1
@sourav yes you're correct.
0

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

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

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:-

0

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'?

0
Both will be some languages - nothing more than that.
0
ok sir
0
if want to write Tyes nad Tno for A then what would it be?....i know that we cannot apply rice theorem but silll??
0
@ Arjun Sir, Can we apply here Rice theorem 2 here or not and if how?
Answer:

Related questions

20 votes
1 answer
1
2k views
Which of the following languages are Recursively Enumerable language? $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ $\{\langle M \rangle \mid M \text{ is a TM and }L(M) = \{00, 11\} \}$ $\{ \langle M1, M2, M3 \rangle \mid L(M1) = L(M2) \cup L(M3) \}$ All of these
asked Jan 27, 2015 in Theory of Computation Vikrant Singh 2k views
5 votes
2 answers
2
556 views
Which of the following languages are CFL? $L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$
asked Sep 12, 2014 in Theory of Computation gatecse 556 views
2 votes
1 answer
4
...