The Gateway to Computer Science Excellence

+21 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

+38 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

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

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

+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

@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.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,733 answers

199,457 comments

107,887 users