Est $ \ {w ~ | ~ \ Forall X \ in t (m_v): | W |> | x | ~ \} $ DIMENDABLE?

Question

Je veux demander si $ \ {w | \ forall x \ in t (m_v): | w |> | x | \} $ est décembre siv est un index d'une machine à turir aléatoire mais fixe avec $ | t (m_v) | <\ \ € $ .

mon idée: Il est co-semi-décidable depuis dès que je trouve un $ x \ in t (m_v) $ avec $ | $ |X | \ geq | w | $ J'ai montré que ce séporacifique w n'est pas dans l'ensemble.Je pense qu'il n'est pas semi-décitable, car il peut toujours y avoir une $ x \ in t (m_v) $ qui est plus long que w.Je pense aussi que le problème est indécitable.

Est-ce que je surveillais quelque chose?

Answer 1

Oui, il vous manque quelque chose.

Le premier argument selon lequel cette langue est co-semi-décembre est correcte. Cependant, la seconde est fausse (et non formellement écrite. Une preuve formelle ne pouvait comporter que de tels arguments, ils ne sont que pour l'intuition habituellement).

Maintenant pour montrer pourquoi il est entièrement décidable: Nous savons que $ | t (m_v) |= C <\ g $ . Maintenant, comme il s'agit d'une constante plus petite que l'infini, il doit y avoir une $ x_0 \ in t (m_v) $ pour laquelle $ | x_0 | $ est le plus long des mots de $ t (m_v). $

Maintenant, construisez la machine Turing qui accepte $ w $ iff $ | w | .

depuis $ x_0 $ est le plus long, puis si $ | W |> | x_0 | $ nous aurons cette $ \ Forall x \ \ in t (m_v): | w |> | x_0 | \ ge | x | $ et donc $ w $ est dans votre langue. Maintenant, si $ | w | \ le | x_0 | $ , alors évidemment $ w $ n'est pas dans votre langue.

donc $ w $ est dans votre langue iff $ w $ est accepté par la machine Turing We Construit.