The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $A$ is Turing recognizable $B$ is not Turing recognizable
- $B$ is Turing recognizable $A$ is not Turing recognizable
- Both $A$ and $B$ are Turing recognizable
- Neither $A$ nor $B$ is Turing recognizable

+31 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/

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/

0

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

Please help me out!

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,815 users