The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.6k 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
asked in Theory of Computation by Boss (18.1k points)
edited by | 2.6k views
0
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.)

  [1]: http://www.xamuel.com/dovetailing/
answered by Veteran (355k points)
edited by
+2

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

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


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

38,017 questions
45,509 answers
131,694 comments
48,737 users