The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 votes

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
asked in Theory of Computation by Boss (18k points)
edited by | 2.4k views
Answer is B

1 Answer

+25 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.)

answered by Veteran (349k points)
edited by

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?

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

Please help me out!

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


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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,204 questions
43,662 answers
42,948 users