self doubt

Question

Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??

Comments

Semi-decidable

---

please explain

---

@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..!

---

thnk u, what if it would be M accepts exactly 100 strings- it should be totally undecidable, am i correct?

---

@Vegeta Yes.

---

Why..M accepts exactly 100 strings is undecidable, not even semi decidable??

Answer 1

What if the problem is like,

Given a TM, M accepts a set of 100 strings.

Is it decidable, semidecidable or partially decidable??