Ist $ \ {w ~ | \ \ forall x \ in t (m_v): | W |> | x | ~ \} $ entschieden?

Question

Ich möchte fragen, ob $ \ {w | \ fürall x \ in t (m_v): | W |> | x | \} $ ist entschieden, wennv ist ein Index einer zufälligen, aber festen Turing-Maschine mit $ | t (m_v) | <\ fentray $ .

meine idee: Es ist co-halb entschlossen, da ich einen $ x \ in t (m_v) $ mit $ |x | \ geq | w | $ Ich habe gezeigt, dass dieses SEPCIFIC W nicht im Set ist.Ich denke, es ist nicht halb entschlossen, da es immer einen $ X \ in t (m_v) $ gibt, der länger als w ist.Dafür denke ich auch, dass das Problem unentscheidbar ist.

Beaufschlüssele ich etwas?

Answer 1

ja, du fehlt etwas.

Das erste Argument, das diese Sprache co-semi-entschlossen ist, ist korrekt. Der zweite ist jedoch falsch (und nicht formal geschrieben. Ein formaler Nachweis konnte nicht aus solchen Argumenten bestehen, sie sind normalerweise nur für die Intuition).

jetzt zu zeigen, warum es vollständig entschieden ist: Wir wissen, dass $ | t (m_v) |= C <\ Infty $ . Da dies ein Konstant ist, der kleiner als unendlich ist, muss ein $ X_0 \ in T (M_V) $ sein, für den $ | x_0 | $ ist die längste von den Wörtern in $ t (m_v). $

Bauen Sie nun die Turing-Maschine, die $ W $ IFF $ | W |> | x_0 | $ .

Da $ X_0 $ das längste ist, dann wenn $ | W |> | x_0 | $ Wir werden diesen $ \ fürall x \ in t (m_v) haben: | W |> | x_0 | \ ge | x | $ und somit $ W $ ist in Ihrer Sprache. Jetzt, wenn $ | W | \ le | x_0 | $ , dann ist offensichtlich $ w $ nicht in Ihrer Sprache.

somit $ W $ ist in Ihrer Sprache in Ihrer Sprache, IFF-Klasse="Math-Container"> $ W $ wird von der Turing-Maschine akzeptiert, die wir gebaut.