Rozstrzygalność języka przedrostka

9

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

Dla rozstrzygalnego zdefiniuj Pokaż, że niekoniecznie jest rozstrzygalny. $L$
$Pref (L) = {x ∣ \exists y s.t. x y \in 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$

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

computability undecidability

— Ran G.
źródło

9

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 Σ^{*} ∣ \exists y \in Σ^{*} ⟨ x, y ⟩ \in V}

$\{ 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_{T M} = {⟨ e, x ⟩ ∣ e encodes a Turing machine which accepts x}

$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.

— Kaveh
źródło

czy możesz wyraźnie podać

V

$V$ to tworzy

A_{T M}

$A_{TM}$ ?

— Ran G.

2

niech

y

$y$ być ciągiem, który ma reprezentować przerywanie obliczeń akceptujących

M_{e}

$M_e$ na

x

$x$ ,

V

$V$ sprawdzi, czy

y

$y$ jest obliczeniem akceptującym

M_{e}

$M_e$ na

x

$x$ .

— Kaveh

To miłe rozwiązanie!

— Ran G.

3

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)

$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.

— Gilles „SO- przestań być zły”
źródło