Es $ \ {w ~ | ~ \ forall x \ in t (m_v): | w |> | x | ~ \} $ decidible?

Question

Quiero preguntar si $ \ {w | \ forall x \ in t (m_v): | w |> | x | \} $ es decidible siv es un índice de una máquina de turing aleatoria pero fija con $ | t (m_v) | <\ infty $ .

mi idea: Es co-semi-decidible ya que tan pronto como encuentro un $ x \ in t (m_v) $ con $ |x | \ geq | w | $ He demostrado que este Sepcific W no está en el conjunto.Creo que no es semi-decidible, ya que siempre puede haber un $ x \ en t (m_v) $ que es más largo que W.Para ello, también creo que el problema es indecidible.

¿Voy a supervisar algo?

Answer 1

Sí, te estás perdiendo algo.

El primer argumento de que este lenguaje es co-semi-decidible es correcto. Sin embargo, el segundo está incorrecto (y no está escrito formalmente. Una prueba formal no pudo consistir en tales argumentos, solo son para la intuición generalmente).

Ahora para mostrar por qué es totalmente decidible: Sabemos que $ | t (m_v) |= C <\ INFTY $ . Ahora, dado que esta es una constante más pequeña que el infinito, debe haber un $ x_0 \ in t (m_v) $ para el $ | x_0 | $ es la más larga de las palabras en $ t (m_v). $

Ahora, construye la máquina de Turing que acepta $ w $ iff $ | w |> | x_0 | $ .

desde $ x_0 $ es el más largo, entonces si $ | w |> | x_0 | $ Tendremos ese $ \ forall x \ in t (m_v): | w |> | x_0 | \ ge | x | $ y por lo tanto $ W $ está en su idioma. Ahora, si $ | w | \ le | x_0 | $ , obviamente $ w $ no está en su idioma.

por lo tanto $ w $ está en su idioma IFF $ W $ es aceptado por la máquina Turing We construido.