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

edited | 3.6k views
0

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] 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.)

: http://www.xamuel.com/dovetailing/
by Veteran (418k points)
edited by
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,

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

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