Udowodnij to

Chciałbym skorzystać z Twojej pomocy przy następującym problemie:

$L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ . Pokaż, że .$L \notin RE \cup CoRE$

Wiem, że aby udowodnić , wystarczy znaleźć język taki, że i pokazać, że istnieje redukcja z na .$L\notin RE$$L'$$L'\notin RE$$L'$$L$ $(L'\leq _M L)$

Zacząłem myśleć o językach, które już wiem, że nie są w , i wiem, że . Myślałem o tej redukcji z do : . dla każdego : jeśli zatrzymuje się dla każdego wejścia przeciwnym razie byłoby to , ale to nie jest poprawne, prawda? Jak mogę sprawdzić, czy zatrzymuje się na początku każdego wejścia? i - czy to jest sposób, aby to zrobić?$RE$$Halt^* =\{⟨M⟩ ∣ M\mbox{ halts for every input} \} \notin RE$$Halt^*$$L$$f(⟨M⟩)=(M')$$⟨M⟩$$M$$L(M')=0^n1^n$$o^n1^n0^n$$M$

Myślę, że pytanie brzmi, jak to pokazać $L$ nie jest ponownie Jednym ze sposobów na to jest zmniejszenie dopełnienia problemu zatrzymania do $L$, ponieważ uzupełnieniem problemu zatrzymania nie jest re

Oto wskazówka na temat jednego ze sposobów zmniejszenia tej emisji: dane $M$ i $x$, chcemy stworzyć język bezkontekstowy wtedy i tylko wtedy, gdy $M(x)$nie zatrzymuje się. Więc zacznij symulować$M$ na wejściu $x$. Tak długo jak$M(x)$ nie zatrzymuje się, tworzymy język, który wygląda $\{ 0^n : n \in \mathbb{N}\}$. Ale jeśli$M(x)$ zatrzymuje się, zmieniamy język, który generujemy po tym momencie, aby był językiem ponownym, ale nie kontekstowym.