È $ \ {w ~ | ~ \ forlt x \ in t (m_v): | w |> | x | ~ \} $ decidabile?

Question

Voglio chiedere se $ \ {w | \ forlt x \ in t (m_v): | w |> | x | \} $ è decidabile sev è un indice di una macchina di tinger casuale ma fissa con $ | t (m_v) | <\ infty $ .

La mia idea: È coe-semi-decidabile poiché non appena trovo una $ x \ in t (m_v) $ con $ |x | \ Geq | W | $ Ho dimostrato che questo sepcifico non è nel set.Penso che non sia semi-decidabile, dal momento che ci può sempre essere una $ x \ in t (m_v) $ che è più lungo di w.Quindi penso anche che il problema sia indecidabile.

Supervisionare qualcosa?

Answer 1

Sì, ti manca qualcosa.

Il primo argomento secondo cui questa lingua è co-semi-decidabile è corretta. Tuttavia, il secondo è sbagliato (e non scritto formalmente. Una prova formale non può consistere in tali argomenti, sono solo per l'intuizione di solito).

Ora per mostrare perché è completamente decidabile: Sappiamo che $ | t (m_v) |= c <\ Infty $ . Ora, poiché questo è un costante inferiore all'infinito, deve esserci una $ x_0 \ in t (m_v) $ per quale $ | x_0 | $ è la più lunga dalle parole in $ t (m_v). $

Ora, costruisci la macchina di tinger che accetta $ W $ IFF $ | W |> | x_0 | $ .

poiché $ x_0 $ è il più lungo, quindi se $ | w |> | x_0 | $ Avremo quella $ \ Forall x \ in t (m_v): | w |> | x_0 | \ ge | x | $ e quindi $ W $ è nella tua lingua. Ora, se $ | w | \ Le | X_0 | $ , quindi ovviamente $ w $ non è nella tua lingua.

così $ W $ è nella tua lingua IFF $ W $ è accettato dalla macchina di Turing Costruito.