Prüfen, ob die Turing-Maschine mindestens k> 2 -zustände durchläuft, bevor Sie ein Wort annehmen

Question

$ l= {\ langle m, k \ rangle \ mid \ existiert w \ in l (m) \ Text \ in l (m) \ text {so, dass mindestens $ M $ stattfindet $ k> 2 $ verschiedene Zustände, bevor $ W $} \} $

Ich versuche daran zu denken, dass er nachweisen kann, dass diese Sprache weder re noch Kern ist. Wie kann man dieses Problem nähern?Gibt es einen Hinweis oder eine Intuition?

Ich überprüfe normalerweise, ob Reis verwendet werden kann, aber die Frage hier geht nicht um die Sprache selbst

Answer 1

eindeutig $ L $ ist akzeptabel (simulieren Sie einfach $ M $ und verfolgen Sie die Anzahl der verschiedene Zustände während der Simulation auftreten). Wir zeigen jetzt, dass es nicht entschieden ist.

Wenn $ L $ entschieden wurden, könnten Sie das Anhalten des Anhaltensproblems wie folgt lösen: Angesichts einer TM-Klasse-Klasse="Math-Container"> $ T $ und eine Eingabe $ x \ in \ Sigma ^ * $ , konstruieren Sie ein TM $ M $ Das ignoriert seinen Eingang, simuliert $ T $ mit input $ x $ und wenn die Simulation abgeschlossen ist, akzeptiert. Sie können weiterhin sicherstellen, dass, wenn $ M $ akzeptiert, dann auch zumindest 3 $ $ unterschiedliche Zustände durchquert indem Sie einfach vom Anfangszustand in einen anderen (unterschiedlichen) Zustand übergeben, bevor Sie die Simulation von $ T $ starten.

Überprüfen Sie nun, ob $ \ Langle M, 3 \ Rangle \ in L $ . Wenn die Antwort positiv ist, gibt es einige $ w \ in \ sigma ^ * $ , für die $ m (w) $ akzeptiert, dass der $ t (x) $ hält. Wenn die Antwort negativ ist, dann $ M $ Niemals hält, zeigt, dass $ t (x) $ nicht halt.