2 votes 2 votes Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable?? Theory of Computation decidability theory-of-computation turing-machine + – Vegeta asked Jul 24, 2018 Vegeta 666 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply abhishekmehta4u commented Jul 24, 2018 reply Follow Share Semi-decidable 1 votes 1 votes Vegeta commented Jul 24, 2018 reply Follow Share please explain 0 votes 0 votes Shubham Shukla 6 commented Jul 24, 2018 reply Follow Share @vegeta its semi decidable becz you can say YES and stop your algo when you reach 100 strings..but for saying NO you dont have any definite algo you cant say when machine will stop there may be case in hope that machine will accept more string you will be continously giving strings and may hope that this may get accept if not than you will give another and this process goes on and on...there may be times when machine could fall in a loop..and in hope that will accept you are waiting indefinitely..so for saying NO ,you dont have any algo..so its Semi decidable..! 0 votes 0 votes Vegeta commented Jul 24, 2018 reply Follow Share thnk u, what if it would be M accepts exactly 100 strings- it should be totally undecidable, am i correct? 0 votes 0 votes Arjun commented Jul 24, 2018 reply Follow Share @Vegeta Yes. 0 votes 0 votes Peach commented Jul 31, 2018 i edited by Peach Aug 8, 2018 reply Follow Share Why..M accepts exactly 100 strings is undecidable, not even semi decidable?? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes What if the problem is like, Given a TM, M accepts a set of 100 strings. Is it decidable, semidecidable or partially decidable?? vg653 answered Aug 13, 2019 vg653 comment Share Follow See all 0 reply Please log in or register to add a comment.