Rozstrzygalność języka przedrostka

W połowie kadencji istniała odmiana następującego pytania:

Dla rozstrzygalnego zdefiniuj Pokaż, że niekoniecznie jest rozstrzygalny.$L$

$$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$ $\text{Pref}(L)$

Ale jeśli wybiorę to myślę, że jest również , a zatem jest rozstrzygalne. Również daje ten sam wynik. A ponieważ musi być rozstrzygalny, nie mogę wybrać problemu z zatrzymaniem lub coś takiego ...$L=\Sigma^*$$\text{Pref}(L)$$\Sigma^*$$L=\emptyset$$L$

1. Jak mogę znaleźć , że nie podlega rozstrzygnięciu?$L$$\text{Pref}(L)$
2. Jakie warunki na sprawią, że rozstrzygalny, a które sprawią, że będzie nierozstrzygalny?$L$$\text{Pref}(L)$

Zauważ, że używając egzystencjalnego kwantyfikatora przed rozstrzygającym językiem, możemy uzyskać dowolny język re, tzn. Każdy język re jest wyrażalny jako

$$\{ x\in \Sigma^* \mid \exists y \in \Sigma^* \ \langle x,y \rangle \in V \}$$

gdzie $V$jest rozstrzygalnym językiem. Należą do nich niezdecydowane języki re, takie jak

$$A_{TM} = \{ \langle e, x\rangle\ \mid \text{$e$ encodes a Turing machine which accepts $x$} \}$$ .

Jedyną różnicą jest to, że tutaj musimy się rozdzielić $x$ i $y$my sami. Standardową sztuczką jest użycie nowego symbolu do rozdzielenia dwóch części (załóżmy, że należy do separatora$y$). Dlatego każdy inny język, w tym nierozstrzygalny, można wyrazić w tym formacie.

W przypadku drugiego pytania nie ma ogólnego algorytmicznego sposobu sprawdzenia, czy prefiksy danego rozstrzygalnego języka są nierozstrzygalne. Wynika to z twierdzenia Rice'a.

Meta-wiedza: chcesz znaleźć nierozstrzygalny język, który ma jednak pewne właściwości obliczeniowe. Arbitralny język, który nie podlega rozstrzygnięciu, prawdopodobnie nie doprowadzi cię zbyt daleko. Ale na wpół rozstrzygalne…

---

Silniejsza wskazówka: co to jest język częściowo rozstrzygalny? Oznacza to, że możemy wyliczyć słowa: to jakiś zestaw słów$u$ taki, że istnieje liczba całkowita $n$ takie, że

$$u = f(n)$$

Wpatrz się trochę w to równanie, mając na uwadze rozstrzygalność i prefiksy.

---

Intuicyjnie mówiąc, załóżmy, że masz $x$ i chcesz sprawdzić, czy jest w środku $\mathrm{Pref}(L)$. Ogólnie rzecz biorąc, nie zrobisz nic lepszego niż czek$x a$, $x b$, $x a a$itp. gdzie $a,b,\cdots$to litery alfabetu. Jest to częściowa funkcja rekurencyjna, która testuje członkostwo$\mathrm{Pref}(L)$. Oczywiście wiedzieliśmy o tym$\mathrm{Pref}(L)$był już; musimy pokazać, że czasami nie ma alternatywnej metody. Weźmy trochę zestawu$S \subset \mathbb{N}$ który jest ponownie i nie rekurencyjny, i niech $f$ być wyliczeniem $S$ ($S = {f(x) \mid x\in\mathbb{N}}$).

Załóżmy, że alfabet zawiera trzy symbole $0$, $1$ i $:$ (jeśli masz tylko dwa symbole $\{\aleph,\beth\}$, koduj $0$ tak jak $\aleph\aleph$, $1$ tak jak $\aleph\beth$ i $:$ tak jak $\beth$). Gdyby$n\in\mathbb{N}$, pozwolić $\bar n$ być $n$ zapisane w bazie 2 za pomocą symboli $0$ i $1$ bez prowadzenia $0$.

Pozwolić $L = \{\bar y\mathord:\bar x \mid y = f(x)\}$. Mówiąc prosto po angielsku, bierzemy elementy$S$ i określając ich indeks wyliczeniowy. $L$ jest wyraźnie rozstrzygalne (sprawdź, czy jest jeden) $:$, że dwucyfrowe sekwencje nie zawierają wiodących $0$, i że pierwsza sekwencja cyfr oznacza obraz według $f$liczby, którą przeliteruje drugi). Ale decyduje, czy niektórzy$\bar y$ jest prefiksem $L$ jest równoznaczne z podjęciem decyzji, czy $y$ jest w $S$, czego nie możesz zrobić bez wiedzy $x$ od $S$z założenia nie jest rekurencyjny. Formalnie,$\mathrm{Pref}(L)$ nie jest rozstrzygalne, ponieważ $\mathrm{Pref}(L) \cap \{0,1\}^*\mathord: = S\mathord:$ nie podlega rozstrzygnięciu.