Awesome q2a theme
0 votes

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

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

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

1 Answer

+1 vote
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)
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.
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.
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.

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

M accepts  a set of 100 strings may either mean that $|L(M)| = 100,$ Or it may mean that $|L(M)| \geq 100.$

Just like when we say that M accepts $\in$ then we don't mean that $L(M) =  \{\in \}$ But we mean that  $L(M) \supseteq  \{\in \}$  

Now, the property "containing at least 100 strings" is a Non-trivial and Monotonic property of RE languages, hence, Undecidable.

But it is recognizable because using Dovetailing technique, we can say Yes for members...

Since M accepts some 100 strings, hence, we will run M on strings in $\Sigma^*$ in Dovetailing fashion and it will accept some 100 strings in finite time, hence, it will halt in finite time on members.

But the property "containing exactly100 strings" is a Non-trivial and Non-Monotonic property of RE languages, hence, Undecidable and unrecognizable.

If the question was M accept atleast 100 strings then it would be decidable right ?

Above argument. Semi-decidable. 

@user2525 , I have gone through every line on this page and there are many mistakes and wrong understanding of the concept in your arguments.

Even though I like your Proposal/Honest people analogy. 

Thank u for explaining.
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jan 2020
  1. shashin

    1262 Points

  2. Deepakk Poonia (Dee)

    346 Points

  3. Vimal Patel

    343 Points

  4. Debapaul

    265 Points

  5. Satbir

    194 Points

  6. Pratyush Priyam Kuan

    158 Points

  7. tp21

    151 Points

  8. SuvasishDutta

    151 Points

  9. pranay562

    142 Points

  10. DukeThunders

    97 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,085 questions
1,538 answers
89,827 users