0
$\begingroup$

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 ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$ – Ariel Aug 10 '20 at 20:48
  • 1
    $\begingroup$ 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 $\endgroup$ – Ariel Aug 10 '20 at 20:49
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.