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

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 ?

• What is your precise intentions by "random but fixed". I believe that what you meant was whether the statement holds for all $v$ (so the word is arbitrary, not random. upon inserting randomness the question changes to with what probability is the following language decidable). – Ariel Aug 10 at 20:48
• As written, your language contains all words of a large enough length (namely, larger than the longest word in $L(M_v)$), which is decidable – Ariel Aug 10 at 20:49

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.