Awesome q2a theme
0 votes
52 views

Given a TM, M accepts a set of 100 Strings is decidable?

in Theory of Computation by (104 points) | 52 views
0
I think it is undecidable.
0
This question can be linked to Halting Problem ?

Why it is not Partially decidable??
0
Yes... partially/semi decidable case is considered as undecidable in GATE.

1 Answer

0 votes
U can have a T.M. which accepts a set of 100 strings and at the same time u can have a T.M. which accepts a set of 99 strings and not 100
This is in accordance with Rice’s 1st theorem. So, it is undecidable.

Now coming to the term partially decidable, we know it is also referred to as recursively enumerable ( refer : wiki definition of R.E. ).
So, to check whether the given T.M. accepts R.E. or is partially decidable, we need to check Rice’s 2nd theorem.

So, the question now is if there is a T.M. which accepts a set of 100 strings, then there must also be a T.M. which will accept a set of 101 strings. If it is so, then it means the 2nd TM is accepting 1st string, 2nd string, 3rd string ………. 100th string and 101st string. Look wait !!!!!  the second T.M. is also accepting the 100th string which the first T.M. has accepted . So, it can be visualized as the 2nd T.M. can do the work done by the first T.M. Thus, it follows Rice’s 2nd theorem and hence the language is not partially-decidable.

Thus, it is undecidable as well as not recursively enumerable / partially decidable .

Rice’s 2nd theorem can be compared like u have taken all the gate books from a library and ur friend took books for algo. and dbms from the same library.

So, in other words, u can also do the same thing which ur friend did. U r taking all the gate books means u r taking books for algos and dbms too.  Same goes with the Turing machines.

If a language cant be recognized by a halting turing machine, then it is undecidable. And if the language is accepted by the universal T.M. then the language is semi-decidable, partially decidable and recursively enumerable.
by (1.6k points)
edited by
0
Actually I don't have idea about Rice theorem, please provide me some link where I can have better understanding of the theorem.

In case of decidability it is like I don't have any thought process about decidability, what should I do, how to build it?
0

how did you related this problem to rice 1st theorem and 2nd theorem. can you please explain

+1

@vg653 https://gateoverflow.in/26675/understanding-rice-theorem

 

@vg653 and @satbir : See to prove something undecidable just like the case where T.M. is supposed to accept a set of 100 strings, we need Rice’s 1st theorem.

Informally,

Rice’s 1st theorem theorem deals with undecidability. So, we all knw that T.M. can do all the things for which there is an algo. ( Church’s hypothesis ). So, in order to prove the language’s undecidability, we take the help of complements. In other words, first we check is there a Turing machine T1 that accepts a set of 100 strings? We know there exist such Turing Machine.Now comes the complement part. We have to find a Turing machine that does not accept 100 strings. In other words, the new Turing machine should do the complement job of the original Turing machine. Is there any Complemented and Related Turing machine ? Oh yes ! there is. So, there is another Turing machine T2 that do not accept set of 100 strings. We can have that. Because T2 can be a turing machine which can accept set of 99 strings and not 100. In other words, we found a machine that will do the complement work of the required Turing machine in the question, If this happens then the original language, mean to say the one getting accepted by T1 is said to be undecidable.

 

Coming to Rice’s 2nd theorem, it is used to prove whether the language is recursively enumerable or not. It deals with the concept of subsets. So, in the given question, let there be a Turing machine T1 which accepts set of 100 strings. So, can there be any other COMPLEMENTED and RELATED Turing machine which performs something and also can do the job of T1 ? Regarding the language in the question, yes there is. So, we take another COMPLEMENTED and Related Turing machine T2 which accepts a set of 101 strings . But u see accepting set of 101 strings is also INCLUDING the job of Turing machine T1 because accepting 101 strings means T2 is also accepting 100 strings. So, job of T1 comes as a subset of job of T2. If it happens so, then the Turing machine T1 is said to accept a language that is not recursively enumerable.

For formal definition, u can go with the link.

 

P.S. : I have used the word RELATED Turing machine for comparison because u cant use a random T.M. for the comparison like T.M. accepting (a+b)*.

Remember another thing if a language is undecidable that does not mean the language is compusorily not semi-decidable.

0
What do we mean by trivial and non trivial property. can you please give an example.
+1

To check if a property is trivial, just check if there is a TM that satisfies it and if there is a TM that does not satisfy it. If both kinds exist, then the property is nontrivial.

A property is said to be trivial if it is satified by every RELATED turing machine.

 

We know that Finiteness of a Regular Language is decidable, so as from Rice’s 1st theorem, it should follow trivial property.

So, any related Turing machine is given and then it is given a regular language, then the turing machine can tell it is finite or infinite. It happens with the set of all related T.M.s . So, it is following trivial property.

 

Now coming to the example, given in the question : a T.M. accepting a set of 100 strings. So, I took a related T.M. and tested it. It is accepting 1 string, 2 strings , 3  strings ……. 99 strings but the T.M. is unable to accept 100 strings. Thus there exist a T.M. which is not satisfying the acceptance of 100 strings property. So, it becomes non-trivial.

 

But in case of finiteness, whatever regular language u give to a related T.M., every related T.M. will tell u either it is finite or infinite. None of the turing machines will tell u : sorry I cant tell u the finiteness of the regular language.

0
If the question was M accept atleast 100 strings then it would be decidable right ?
+2
It is not decidable.

See, if there is a T.M. T1 which is accepting atleast 100 strings, then there must be a T.M. T2 which is accepting atleast 200 strings. T1 and T2 are doing the same jobs but they are complement to each other, thus they are related. Here, complement is like what T1 can do T2 cant do, so T2 cant accept a set of atleast 100 strings.  So, it is undecidable ( Rice’s 1st theorem ).

Even if u cant understand the Rice’s theorem part, u can go with the definition of REC and R.E. languages. See, we know for REC languages, the halting turing machine would say yes or no to a problem and for R.E. languages we know that the T.M. will say yes, no or loop. Recursive languages are like the honest ppl who say yes or no after getting proposed and Recursively enumerable languages are like the unpredictable people who can say yes, no or keep u in a loop after getting proposed.

So, for T1 ( paragraph after first lyn), it is accepting atleast 100 strings. But suppose I make the value very large to make it realistic, suppose the turing machine is accepting set of  atleast k strings. So, we give a related T.M., then one string, it wont accept, then 2 strings it wont accept  and so on……… moral of the story is it is not halting and it wd go on and on. Because the value of k can be 10^10000000. So, the testing wd go on and on. Here u r taking the value 100 but I am taking a large value for making it realistic. In other words, we should be concerned abt the language and not the value.

So, as per definition it is undecidable.


Now for Rice's 2nd theorem to check semidecidability.

Suppose there is a TM 1 dat accepts atleast 100 strings and there is TM 2 dat accepts atleast 50 strings. Accepting atleast 50 strings is doing da job of accepting atleast 100 strings. Thus subset work is done here. So it is not semi decidable.

It is lyk as I told previously u r borrowing gate books from library and ur frnd is borrowing algo and db books frm library. Both of u r doing 2 different work so u both r doing complentary work. But  while focussing on ur own work u r doing ur frnd's work too becoz borrowing gatee books is including books for algo and db. Thus the situation becomes not even semi decidable.
0
Why do u think it is decidable? I want to know the thought process about decidability because i could never get whatever i think about decidability is right or not..

Please share your view @Satbir.
0
user2525 is correct.

If a language is recursive → it is decidable. you can say YES or NO for each input.

eg:- everyone who are appearing in GATE will get admission in IISC. You can say NO by directly looking at the sentence.

if a language is recursively enumerable language → it is semi decidable and thus undecidable. You  can say YES for the input but can’t say NO.

eg:- Atleast 1 person will read this example. this is semi decidable because you are reading this and so YES but you can’t say NO because you don’t know whether anyone else will read it or not.

if a language is not recursively enumerable language  → it is undecidable. You can’t say either YES or NO for the given input.

eg :- you will get a AIR 1 in GATE. it is undecidable and not even semidecidable. since you can’t say either YES or NO.
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
932 questions
596 answers
1,885 comments
81,474 users