É $ \ {w ~ | ~ \ forall x \ in t (m_v): | w |> | x | ~ \} $ decidível?

Question

Eu quero perguntar se $ \ {W | \ forall x \ in t (m_v): | w |> | x | \} $ é decidível sev é um índice de uma máquina de Turing aleatória, mas fixa com $ | t (m_v) | <\ FATTY $ .

minha ideia: É co-decidível, já que, assim que encontrar uma $ x \ in t (m_v) $ com $ |x | \ geq | w | $ Eu tenho mostrado que este w w não está no conjunto.Eu acho que é semi-decidível, já que sempre pode haver uma $ x \ in t (m_v) $ que é mais longo que w.Eu também acho que o problema é indecável.

Eu supervisionei alguma coisa?

Answer 1

Sim, você está faltando alguma coisa.

O primeiro argumento de que esta linguagem é co-decidível é correta. No entanto, o segundo é errado (e não formalmente escrito. Uma prova formal não poderia consistir em tais argumentos, eles são apenas para a intuição geralmente).

Agora para mostrar por que é totalmente decidível: Sabemos que $ | t (m_v) |= c <\ frty $ . Agora, já que esta é uma constante menor que o infinito, deve haver uma $ x_0 \ in t (m_v) $ para o qual $ | x_0 | $ é o mais longo das palavras em $ t (m_v). $

Agora, construa a máquina de Turing que aceita $ W $ IFF $ | w |> | x_0 | $ .

Como $ x_0 $ é o mais longo e, em seguida, se $ | w | w |> | x_0 | $ Teremos essa $ \ forall X \ in t (m_v): | w |> | x_0 | \ ge | x | $ e, portanto, $ W $ está no seu idioma. Agora, se $ | w | \ le | x_0 | $ , então obviamente $ W $ não está no seu idioma.

Assim, $ W $ está no seu idioma IFF $ W $ é aceito pela máquina de Turing construído.