Это $ \ {w ~ | ~ \ \ forall x \ in t (m_v): | w |> | x | ~ \} $ projectable?

Question

Я хочу спросить, $ \ {w | \ forall x \ in t (m_v): | w |> | x | \} $ directable, еслиv - индекс случайной, но фиксированной машины для Turing с $ | t (m_v) | <\ infty $ .

Моя идея: Он является CO-SEMI, поскольку, как только я нахожу $ x \ in t (m_v) $ с $ |x | \ geq | w | $ Я показал, что этот сепцифический W не находится в наборе.Я думаю, что он не получен полученным, поскольку всегда может быть $ x \ in t (m_v) $ , который длиннее w.Поэтому я также думаю о проблеме неразрешимой.

Я что-то контролировать?

Answer 1

Да, вы не хватаете чего-то.

Первый аргумент, который этот язык является COMI-DICIDABLE, является правильным. Однако второй неправильный (и не формально написан. Официальное доказательство не может состоять из таких аргументов, они обычно только для интуиции).

Теперь, чтобы показать, почему он полностью разрешен: Мы знаем, что $ | t (m_v) |= c <\ infty $ . Теперь, поскольку это постоянно меньше, чем бесконечность, должна быть $ x_0 \ in t (m_v) $ , для которого $ | x_0 | $ - самый длинный из слов в $ t (m_v). $

Теперь создайте машину Turing, который принимает $ W $ iff $ | w |> | x_0 | $ .

Поскольку $ x_0 $ - самый длинный, то если $ | W |> | x_0 | $ У нас будет то, что $ \ forall x \ in t (m_v): | w |> | x_0 | \ ge | x | $ и, таким образом, $ w $ на вашем языке. Теперь, если $ | w | \ le | x_0 | $ , то, очевидно, $ W $ не на вашем языке.

Таким образом, $ W $ на вашем языке IFF $ W $ принимается Turging Machine We построен.