Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

Question

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$.

My idea: It is co-semi-decidable since as soon as i find an $x\in T(M_v)$ with $|x|\geq |w|$ I have shown that this sepcific w is not in the set. I think it aint semi-decidable, since there can always be an $x\in T(M_v)$ which is longer than w. Therefor i also think the problem ist undecidable.

Do i oversee something ?

Answer 1

Yes, you are missing something.

The first argument that this language is co-semi-decidable is correct. However, the second one is wrong (and not formally written. A formal proof could not consist of such arguments, they are only for intuition usually).

Now to show why it is fully decidable: We know that $|T(M_v)|=c<\infty$. Now, since this is a constant smaller than infinity, there must be an $x_0\in T(M_v)$ for which $|x_0|$ is the longest from the words in $T(M_v).$

Now, build the turing machine that accepts $w$ iff $|w|>|x_0|$.

Since $x_0$ is the longest, then if $|w|>|x_0|$ we will have that $\forall x\in T(M_v):|w|>|x_0|\ge|x|$ and thus $w$ is in your language. Now, if $|w| \le |x_0|$, then obviously $w$ is not in your language.

Thus $w$ is in your language iff $w$ is accepted by the turing machine we built.