Prove decidability or undecidability of a language accepted by a turing machine.

56 Views Asked by At

consider this problem:

"Given a TM $X$, determine if the language accepted by $X$ contains more than $100$ strings"

Is this problem decidable or not?

Opinion 1: (mine)

I derived my proof by using Rice's Theorem. Let P be the property "The language has more than 100 words" this is a non trivial propriety as long as I can find a language that has less than 100 words, so we can conclude that the given problem is not decidable.

Opinion 2: (friend of mine)

We know that the language is accepted by the TM so by definition it's a semi-decidable language, but we know that a language is semi-decidable iff it is enumerable so we can use the enumeration algorithm and check if it produces at least 100 strings, so it is decidable.

Which one is right?

1

There are 1 best solutions below

2
On

Your friend's idea only shows that this problem is recursively enumerable : you can check that the language has at least 100 words when it does, but you'll be left trying indefinitely if it does not.