# Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable?

I have two questions as in the title:

1. TM M accepts some string of length greater than 100
2. TM M accepts some string of length at most 100

Since 1. is infinite, we can rephrase question as "does TM accept a string", which is clearly undecidable and there are many proofs for that.

2nd question on the other hand is finite and all finite languages are decidable.

Is my reasoning correct? I can't find any confirmation of my theories.

• For starters yes if you know a language is finite it's decidable. But the problem of given a turing machine description telling whether the size of the language it accepts is finite, is an undecidable problem. So your reasoning is flawed. Nov 13 '15 at 20:36
• As for hint: see Rice theorem. Nov 13 '15 at 20:41
• With Rice's Theorem we can e.g. prove that L(M) contains only even (or odd) length strings. String of length at most 100 are the sum of those two (even and odd strings) which leads that in similar way we can prove 2nd question. What about the 1st one? Is the reasoning the same as for the 2nd question (proof with Rice's theorem) Nov 13 '15 at 20:58

Coming to your case, the languages are $L_1=\{\langle M \rangle \;| \; \text{M accepts some string of length greater than 100} \}$ and $L_2=\{\langle M \rangle \;| \; \text{M accepts some string of length less than equal to 100} \}$
It is not difficult to see that in both the cases you are trying to decide non-trivial properties and thus both $L_1$ and $L_2$ are undecidable. As for your reasoning it is flawed as I commented, because knowing that size of a language is finite and being able to construct a Turing machine deciding it, is different from being able to decide whether an arbitrary Turing machine recognizes a language of finite size.