Jak pokazać, że funkcja nie jest obliczalna?

43

Wiem, że istnieje Maszyna Turinga, jeśli funkcja jest obliczalna. Jak więc pokazać, że funkcja nie jest obliczalna lub że nie ma do tego żadnej maszyny Turinga. Czy istnieje coś takiego jak lemat pompujący?

— użytkownik5507
źródło

57

Zanim odpowiem na twoje ogólne pytanie, pozwól mi najpierw cofnąć się o krok, podać tło historyczne i odpowiedzieć na wstępne pytanie: Czy istnieją funkcje niepoliczalne?

^{[notacja: możemy powiązać dowolną funkcję $f$ z językiem $L_f=\{ (x,y) \mid y=f(x) \}$ a następnie omówić rozstrzygalność $L_f$ zamiast obliczalności $f$ ]}

Języki nierozstrzygalne zrobić opuszczeniu w

Istnieje kilka języków, których nie może określić żadna maszyna Turinga. Argument jest prosty: istnieje „tylko” wiele $(\aleph_0)$ różnych baz TM, ale niepoliczalnie wiele $(\aleph)$ różnych języków. Zatem istnieje co najwyżej $\aleph_0$ rozstrzygalnych języków, a pozostałe (nieskończenie wiele) są nierozstrzygalne. Dalsza lektura:

Aby położyć dłoń na konkretnym nierozstrzygalnym języku, pomysł polega na użyciu techniki o nazwie diagonalizacja (Georg Cantor, 1873), która pierwotnie została użyta do wykazania, że jest więcej liczb rzeczywistych niż liczb całkowitych, lub innymi słowy, że . $\aleph > \aleph_0$

Pomysł skonstruowania pierwszego nierozstrzygalnego języka jest prosty: wymieniamy wszystkie maszyny Turinga (co jest możliwe, ponieważ można je wyliczyć!) I tworzymy język, który nie zgadza się z każdą TM na co najmniej jednym wejściu.

\begin{array}{cccccc} ε & 0 & 1 & 00 & \dots \\ M_{1} & 1 & 0 & 1 & 0 & 1 \\ M_{2} & 0 & 1 & 0 & 0 & 0 \\ M_{3} & 0 & 0 & 0 & 1 & 0 \\ ⋮ & ⋱ \end{array}

$\begin{array}{c|ccccc} & \varepsilon & 0 & 1& 00 & \cdots \\ \hline M_1 & \color{red}{1} & 0 & 1 & 0 & 1 \\ M_2 & 0 & \color{red}{1} & 0 & 0 & 0 \\ M_3 & 0 & 0 & \color{red}{0} & 1 & 0 \\ \vdots & & & & \ddots & \end{array}$

Powyżej, każdy wiersz to jedna TM, a każda kolumna to jedno wejście. Wartość komórki wynosi 0, jeśli TM odrzuca lub nigdy się nie zatrzymuje, i 1, jeśli TM akceptuje te dane wejściowe. Definiujemy język tak, aby zawierał ty sygnał wejściowy tylko wtedy, gdy ta TM nie akceptuje tego wejścia. $D$ $D$ $i$ $i$

Zgodnie z powyższą tabelą ponieważ akceptuje . Podobnie , ale ponieważ nie akceptuje . $\varepsilon \notin D$ $M_1$ $\varepsilon$ $0\notin D$ $1\in D$ $M_3$ $1$

Załóżmy teraz, że decyduje i wyszukuje wiersz w tabeli: jeśli w tej kolumnie jest , to akceptuje to wejście, ale nie ma go w , a jeśli jest tam , to wejście jest w ale tego nie akceptuje. Dlatego nie decyduje i dotarliśmy sprzeczność. $M_k$ $D$ $k$ $1$ $k$ $M_k$ $D$ $0$ $D$ $M_k$ $M_k$ $D$

Teraz twoje pytanie. Istnieje kilka sposobów udowodnienia, że język jest nierozstrzygalny. Spróbuję dotknąć najczęstszych.

1. Bezpośredni dowód

Pierwszą metodą jest bezpośrednie pokazanie, że język jest nierozstrzygalny, poprzez pokazanie, że żadna TM nie może go zdecydować. Zwykle jest to zgodne z przedstawioną powyżej metodą diagonalizacji.

Przykład.

Pokaż, że (dopełnienie) Język przekątnej jest nierozstrzygalny.
$\bar{L_{D}} = {⟨ M ⟩ ∣ ⟨ M ⟩ \notin L (M)}$ $\overline {L_D} = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}$

Dowód.
Załóżmy, że jest rozstrzygalne i niech będzie decydującym. Istnieją dwa przypadki: $\overline {L_D}$ $M_D$

przyjmuje $M_D$ $\langle M_D \rangle$ lecz następnie, tak . Więc to nie może się zdarzyć, jeśli postanawia . $\langle M_D \rangle \in L(M_D)$ $\langle M \rangle \notin \overline {L_D}$ $M_D$ $\overline {L_D}$
nie akceptuje $M_D$ $\langle M_D \rangle$ : tak , a zatem . Ale jeśli jest w , powinny zaakceptowali go, a my ponownie osiągnęła sprzeczność. $\langle M_D \rangle \notin L(M_D)$ $\langle M \rangle \in \overline {L_D}$ $L_D$ $M_D$

2. Właściwości zamknięcia

Czasami możemy użyć właściwości zamknięcia, aby pokazać, że jakiś język nie jest rozstrzygalny, w oparciu o inne języki, o których wiemy, że nie są rozstrzygalne.

W szczególności, jeśli nie jest rozstrzygalne (piszemy ), to również jego dopełnienie jest nierozstrzygalne: jeśli istnieje decydujący dla możemy po prostu użyć go do podjęcia decyzji , akceptując, gdy odrzuca i odwrotnie. Ponieważ zawsze zatrzymuje się z odpowiedzią (jest to decydujący), zawsze możemy odwrócić jego odpowiedź. $L$ $L\notin R$ $\overline{L}$ $M$ $\overline{L}$ $L$ $M$ $M$

Wniosek: przekątnej język jest nierozstrzygalnym, . ${L_D} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \}$ $L_D \notin R$

Podobny argument można zastosować, zauważając, że jeśli zarówno jak i jego uzupełnienie są rekurencyjnie policzalne, oba są rozstrzygalne. Jest to szczególnie przydatne, jeśli chcemy udowodnić, że języka nie da się wyliczyć rekurencyjnie, co jest silną właściwością niż nierozstrzygalność. $L$ $\overline{L}$

3. Zmniejszenie nierozstrzygniętego problemu

Zwykle dość trudno jest bezpośrednio udowodnić, że język jest nierozstrzygalny (chyba że jest już skonstruowany w sposób „diagonalny”). Ostatnią i najczęstszą metodą udowodnienia nierozstrzygalności jest użycie innego języka, o którym wiemy, że jest nierozstrzygalny. Chodzi o to, aby zredukować jeden język do drugiego: aby pokazać, że jeśli jeden jest rozstrzygalny, to drugi musi być również rozstrzygalny, ale wiadomo, że jeden z nich jest nierozstrzygalny, co prowadzi do wniosku, że pierwszy jest również nierozstrzygalny. Przeczytaj więcej na temat redukcji w „Jakie są typowe techniki wzajemnego zmniejszania problemów?” .

Przykład.

Pokaż, że przekątna język jest nierozstrzygalny.
$H P = {⟨ M, x ⟩ ∣ M halts on x}$ $HP = \{ \langle M,x \rangle \mid M \text{ halts on } x \}$

Dowód.
Wiemy, że jest nierozstrzygalny. Zmniejszamy do (to jest oznaczone ), to znaczy, że wykazują, że jeśli był rozstrzygalne można było używać jej decydującym zdecydować , co jest sprzeczne. $L_D$ $L_D$ $HP$ $L_D \le HP$ $HP$ $L_D$

Zmniejszenie polega na konwersji kandydata dla (to jest wejścia do potencjalnego decydującym / akceptora ) z kandydatem do tak, że wtedy i tylko wtedy, gdy . Zapewniamy, że ta konwersja jest obliczalna. Zatem decyzja mówi nam, czy , więc jeśli możemy zdecydować HP, będziemy mogli również zdecydować .¹ $w$ $L_D$ $L_D$ $w'$ $HP$ $w\in L_D$ $w' \in HP$ $w'$ $w\in L_D$ $L_D$

Konwersja jest następująca. Podjąć pewne i wyjściowe , ² gdzie jest tm, która zachowuje się jak , ale jeśli odrzutów, a przechodzi w nieskończonej pętli. $w=\langle M \rangle$ $w'=\langle M' , \langle M \rangle\rangle$ $M'$ $M$ $M$ $M'$

Zobaczmy, że spełniają wymagania. Jeśli , to znaczy, że postojów i akceptuje wejście . W związku z tym, również zatrzymanie i akceptuje wejście . Tak więc, . Z drugiej strony, jeśli następnie albo odrzuca albo nigdy zatrzymanie na $w,w'$
$w\in L_D$ $M$ $\langle M\rangle$ $M'$ $\langle M\rangle$ $\langle M', \langle M\rangle \rangle \in HP$
$w\notin L_D$ $M$ . W obu przypadkach trafi do nieskończonej pętli na . Tak więc, , i pokazuje, że są wykonane wtedy i tylko wtedy, gdy , i w ten sposób wykazać, że . $\langle M\rangle$ $M'$ $\langle M\rangle$ $\langle M', \langle M\rangle \rangle \notin HP$ $w\in L_D$ $w'\in HP$ $HP\notin R$

Dalsza lektura: wiele przykładów redukcji i dowodzenia niemożności rozstrzygnięcia języków można znaleźć za pomocą tagu redukcji .

Obowiązują pewne ograniczenia dotyczące ograniczenia. Sama konwersja musi być obliczalna i dobrze zdefiniowana dla każdego wejścia.
Sygnał wejściowy o wygląda , gdzie jest TM i jest kilka znaków. Więc tutaj wybieramy ciąg który ma być kodowaniem maszyny , która jest tylko jakimś ciągiem .. $HP$ $\langle M,x\rangle$ $M$ $x$ $x$ $M$

4. Twierdzenie Rice'a

„Więc za każdym razem chcemy udowodnić jest nierozstrzygalny, musimy zmniejszyć (lub ) do tego? Czy to nie jest jakiś skrót?” $L$ $L_D$ $HP$

Cóż, w rzeczywistości jest. To jest twierdzenie Rice'a .

Twierdzenie mówi, że wiele języków o określonej strukturze jest nierozstrzygalnych. Ponieważ wszystkie te języki mają tę pewną strukturę, możemy wykonać redukcję raz i zastosować ją do dowolnego języka, który przyjmuje podobną strukturę.

Twierdzenie to formalnie sformułowano w następujący sposób:

$\emptyset \subsetneq S \subsetneq RE$ $L_S$
$L_{S} = {⟨ M ⟩ ∣ L (M) \in S}$ $L_S = \{ \langle M \rangle \mid L(M) \in S \}$

Zestaw jest podzbiorem języków w ; nazywamy to właściwością, ponieważ opisuje właściwość akceptowanego języka . Wszystkie bazy TM, których język spełnia tę właściwość, należą do . $S$ $RE$ $L(M)$ $L_S$

Na przykład może być właściwością, że zaakceptowany język zawiera dokładnie dwa słowa: $S$ $L(M)$

$S_{2} = {L ∣ | L | = 2, L \in R E} .$ $S_2 = \{ L \mid |L| =2 , L \in RE\}.$ W tym przypadku jest zbiorem wszystkich baz TM, których język składa się z dokładnie dwóch słów: $L_{S_2}$ $L_{S_{2}} = {⟨ M ⟩ ∣ L (M) \in S} = {⟨ M ⟩ ∣ | L (M) | = 2} .$ $L_{S_2} = \{\langle M \rangle \mid L(M) \in S\} = \{\langle M \rangle \mid |L(M)|=2\}.$

Właściwość może być bardzo prosta, ale nie może to być wszystkie języki RE lub żaden z języków RE. Jeśli lub wówczas właściwość jest uważana za trywialną , a indukowany jest obliczalny. Przykładem prostego jest taki, który zawiera tylko jeden język, powiedzmy . Zauważ, że chociaż zawiera tylko jeden język, istnieje nieskończenie wiele maszyn których językiem jest , więc jest nieskończony i nierozstrzygalny. $S=\emptyset$ $S=RE$ $L_S$ $S$ $S_{complete}=\{ \Sigma^*\}$ $S$ $M$ $\Sigma^*$ $L_{S_{compete}}$

Twierdzenie to jest bardzo silne, aby udowodnić nierozstrzygalność wielu języków.

Przykład.

Język , jest niezdecydowany $L_\emptyset = \{ \langle M \rangle \mid M \text{ never reaches the accepting state} \}$

Dowód.
Możemy zapisać jako , to znaczy dla właściwości . Jest to nietrywialna właściwość (obejmuje język , ale nie obejmuje na przykład języka . Dlatego według twierdzenia Rice'a jest nierozstrzygalny. $L_\emptyset$ $\{ \langle M \rangle \mid L(M)=0 \}$ $L_\emptyset=L_S$ $S=\{ L \in RE, |L|=0\}$ $L=\emptyset$ $L=\{1, 11, 111,\ldots\}$ $L_\emptyset$

Udowodnimy teraz twierdzenie. Jak wspomniano powyżej, pokażemy redukcję z do (dla dowolnego arbitralnego, nietrywialnego ). $HP$ $L_S$ $S$

Dowód.
Niech będzie nietrywialną własnością, . Pokazujemy , czyli zmniejszamy do , abyśmy mogli zdecydować moglibyśmy zdecydować (co, jak wiemy, jest niemożliwe, dlatego nie może być rozstrzygalne). W dowodzie poniżej zakładamy, że język nie jest pusta część , czyli . (jeśli pusty język jest w , równoważny dowód działa na właściwości dopełniacza , pominę szczegóły). Ponieważ $S$ $\emptyset \subsetneq S \subsetneq RE$ $HP \le L_S$ $HP$ $L_S$ $L_S$ $HP$ $L_S$ $S$ $\emptyset \notin S$ $S$ $\overline S = RE \setminus S$ $S$ jest nietrywialny, obejmuje co najmniej jeden język; nazwijmy ten język i załóżmy, że jest maszyną, która akceptuje (taka maszyna istnieje, ponieważ zawiera tylko języki w RE). $L_0$ $M_0$ $L_0$ $S$

Przypomnijmy, że przy takiej redukcji (patrz sekcja 3 powyżej) musimy pokazać, jak przekonwertować wejście dla na wejście dla , aby $w$ $HP$ $w'$ $L_S$

w \in H P if and only if w^{'} \in L_{S}

$w\in HP \quad \text{ if and only if }\quad w' \in L_S$

Niech , konwertujemy go na gdzie opis maszyny (na wejściu ) jest następujący: $w=(\langle M \rangle, x)$ $w'=\langle M' \rangle$ $M'$ $x'$

Uruchom na . $M$ $x$
Jeśli krok 1 powyżej się zatrzyma, uruchom na i odpowiednio zaakceptuj / odrzuć. $M_0$ $x'$

Widzimy, że ta konwersja jest ważna. Po pierwsze, należy łatwo skonstruować opis podany . $M'$ $w=(\langle M \rangle, x)$

Jeśli , to zatrzymuje się na . W takim przypadku przechodzi do kroku 2 i zachowuje się jak . Dlatego jego akceptowaną język . Dlatego . Jeśli to zapętla się na . W tym przypadku, pętle na dowolnym wejściu - że zostaje zatrzymany w etapie 1. Język akceptowane przez„w tym przypadku jest pusty, . Dlatego . $w\in HP$ $M$ $x$ $M'$ $M_0$ $L(M')=M_0\in S$ $w'=\langle M' \rangle \in L_S$
$w\notin HP$ $M$ $x$ $M'$ $x'$ $M'$ $L(M')=\emptyset \notin S$ $w'=\langle M' \rangle \notin L_S$

4.1. Twierdzenie o rozszerzonym ryżu

Twierdzenie Rice'a daje nam w łatwy sposób, aby pokazać, że pewnego języka , który spełnia pewne właściwości jest nierozstrzygalny, to znaczy, . Rozszerzona wersja twierdzenia Rice'a pozwala nam ustalić, czy język jest wymienny rekurencyjnie, czy nie, to znaczy określa, czy , sprawdzając, czy spełnia pewne dodatkowe właściwości. $L$ $L \notin R$ $L \notin RE$ $L$

Twierdzenie (Rice, rozszerzone). Biorąc pod uwagę właściwość , język jest wymienny ( ) tylko wtedy, gdy wszystkie następujące trzy instrukcje są łącznie utrzymać $S \subseteq RE$
$L_{S} = {⟨ M ⟩ ∣ L (M) \in S}$ $L_S = \{ \langle M \rangle \mid L(M) \in S \}$ $L_S \in RE$

Dla dowolnych dwóch , jeśli oraz wówczas również . $L_1, L_2 \in RE$ $L_1 \in S$ $L_1 \subseteq L_2$ $L_2 \in S$

Jeśli to istnieje skończona podzbiór tak że . $L_1\in S$ $L_2 \subseteq L_1$ $L_2 \in S$

Zbiór wszystkich skończonych języków w jest wyliczalny (innymi słowy: istnieje TM, która wylicza wszystkie skończone języki ). $S$ $L\in S$

Dowód.
Jest to twierdzenie „wtedy i tylko wtedy” i powinniśmy udowodnić oba jego kierunki. Po pierwsze, pokazujemy, że jeśli jeden z warunków (1,2,3) nie jest spełniony, to . Następnie pokażemy, że jeśli wszystkie trzy warunki utrzymują się jednocześnie, to . $L_S \notin RE$ $L_S \in RE$

Jeśli (1,2) jest wstrzymane, ale (3) nie, to $L_S \notin RE$ .
Załóżmy, że , i zobaczymy, że mamy sposób na zaakceptowanie dowolnych skończonych języków w (a zatem zestaw wszystkich tych języków to RE), a zatem warunek (3) zachowuje się i dochodzimy do sprzeczności . Jak zdecydować, czy skończony należy do czy nie? Łatwo - używamy opis skonstruować maszynę że akceptuje tylko słowa , a teraz możemy uruchomić maszynę na (pamiętaj - założyliśmy , więc nie jest to maszyna, która akceptuje $L_S \in RE$ $S$ $L$ $S$ $L$ $M_L$ $L$ $L_S$ $M_L$ $L_S\in RE$ $L_S$ !). Jeśli to a ponieważ , jego maszyna powie tak na wejściu , i gotowe. $L\in S$ $\langle M_L \rangle \in L_S$ $L_S\in RE$ $\langle M_L \rangle$

Jeśli (2,3) utrzymuje, ale (1) nie, to $L_S \notin RE$ . Zakładamy, że i pokażemy, że mamy sposób decydować o , co prowadzi do sprzeczności.
$L_S \in RE$ $HP$

Ponieważ warunek (1) nie posiada, nie jest językiem i rozszerzeniem tego, tak że . Teraz powtórzymy argument użyty w Rozdziale 4, aby zdecydować : biorąc pod uwagę dane wejściowe dla , konstruujemy maszynę której językiem jest jeśli lub w inny sposób, jego językiem jest . Następnie możemy zdecydować : albo zatrzymuje się na , albo maszyna RE dla akceptuje $L_1 \in S$ $L_2 \supseteq L_1$ $L_2 \notin S$ $HP$ $(\langle M \rangle,x)$ $HP$ $M'$ $L_1$ $(\langle M \rangle,x)\notin HP$ $L_2$ $HP$ $M$ $x$ $L_S$ $M'$ ; możemy działać równolegle i mamy gwarancję, że przynajmniej jeden się zatrzyma.

Podajmy szczegóły budowy (na wejściu ): $M'$ $x'$

Wykonaj następujące czynności równolegle:
1.1 uruchom na . 1.2 uruchom maszynę na $M$ $x$
$L_1$ $x'$
Jeśli 1.2 zatrzyma się i zaakceptuje - zaakceptuj.
Jeśli 1.1 zatrzyma się: uruchom maszynę na . $L_2$ $x'$

Dlaczego to działa? Jeśli 1.1 nigdy się nie zatrzymuje, a akceptuje dokładnie wszystkie dane wejściowe, które są akceptowane w kroku 1.2, więc . Z drugiej strony, jeśli , to w pewnym momencie krok 1.1 zatrzymuje się, a akceptuje dokładnie . Może się zdarzyć, że zaakceptuje wcześniej, ale ponieważ , nie zmienia to języka w tym przypadku. $(\langle M \rangle,x)\notin HP$ $M'$ $L(M')=L_1$ $(\langle M \rangle,x)\in HP$ $M'$ $L_2$ $1.2$ $L_1 \subseteq L_2$ $M'$

Jeśli (1,3) jest wstrzymane, ale (2) nie, to $L_S \notin RE$ .
Ponownie założymy i pokażemy, że staje się rozstrzygalne, co jest sprzecznością. $L_S\in RE$ $HP$

Jeśli warunek (2) nie jest spełniony, to dla dowolnego wszystkie jego skończone podzestawy spełniają (zwróć uwagę, że musi być nieskończony, ponieważ ). Jak wyżej, aby zdecydować dla danego wejścia , konstruujemy maszynę której językiem jest if i niektóre skończone przeciwnym razie . Sprzeczność zachodzi w podobny sposób jak powyżej. $L_1\in S$ $L_2 \subseteq L_1$ $L_2 \notin S$ $L_1$ $L_1\subseteq L_1$ $HP$ $(\langle M \rangle,x)$ $M'$ $L_1$ $(\langle M \rangle,x)\notin HP$ $L_2$

Konstrukcja tej maszyny jest dość podobna do poprzedniej którą zbudowaliśmy. Maszyna (na wejściu ) wykonuje: $M'$ $M'$ $x'$

Uruchamia na dlakroki. $M$ $x$ $|x'|$
Jeśli zatrzyma się podczas kroku 1 - odrzuć $M$
W przeciwnym razie uruchom maszynę na . $L_1$ $x'$

Utrzymuje, że jeśli , to w pewnym momencie, powiedzmy po 1000 krokach, zatrzymuje się na . Dlatego krok 1 zatrzyma (i odrzuci) wszelkie dane wejściowe o długości . Dlatego w tym przypadku jest skończone . Należy również zauważyć, że , a w szczególności przez nasze założenia na unieważnienie warunkiem (2), że mamy . $(\langle M \rangle,x)\in HP$ $M$ $x$ $x'$ $>1000$ $L(M')$ $L(M') \subseteq L_1$ $L(M) \notin S$

Z drugiej strony, jeśli , to krok 1 nigdy się nie zatrzymuje, a my nigdy nie odrzucamy w kroku 2. W tym przypadku łatwo zauważyć, że i in zwłaszcza . $(\langle M \rangle,x)\notin HP$ $L(M)=L_1$ $L(M)\in S$

Pozostaje nam wskazać inny kierunek rozszerzonego twierdzenia. Oznacza to, że musimy pokazać, że jeśli wszystkie warunki (1,2,3) są spełnione, to mamy TM, która akceptuje , czyli . Innymi słowy, musimy pokazać maszynę , aby dla każdego wejścia dla którego , maszyna zaakceptowała te dane wejściowe, . $L_S$ $L_S \in RE$ $M_S$ $\langle M \rangle$ $L(M) \in S$ $M_S(\langle M \rangle) \to \textsf{accept}$

Oto jak zachowuje się maszyna (na wejściu ): $M_S$ $\langle M \rangle$

Niech będzie maszyną, która wylicza wszystkie skończone języki w , gwarantowane przez warunek (3). $M_{\text{enum }S}$ $S$
Uruchom następujące polecenie równolegle (przez połączenie typu „jaskółczy ogon”, patrz np. To i to ) dla 2.1 Uruchom aż wyświetli język 2.2. Sprawdź, czy akceptuje wszystkie słowa (uruchom na tych słowach, ponownie równolegle). 2.3 Jeśli dla niektórych , akceptuje wszystkie słowa - zaakceptuj. $i=1,2,...$
$M_{\text{enum }S}$ $L_i$
$M$ $L_i$ $M$
$i$ $M$ $L_i$

Dlaczego to działa? Jeśli ma skończony podzbiór , a gdy wyjdzie z tego podzbioru, w krokach 2.2 / 2.3 okaże się, że akceptuje wszystkie słowa w tym języku i zaakceptować. $L(M) \in S$ $L_j \in S$ $M_{\text{enum }S}$ $M$

Z drugiej strony, jeśli nie może być akceptując wszystkie słowa dla każdego . Rzeczywiście, pod warunkiem (1), każdy również znajduje się w , więc jeśli akceptuje wszystkie słowa w dla niektórych , to a zatem , w przeciwieństwie. $L(M) \notin S$ $L_i$ $i=1,2,...$ $L' \supseteq L_i$ $S$ $M$ $L_i$ $i$ $L(M)\supseteq L_i$ $L(M) \in S$

Na koniec zauważ, że poniższe jest prostym (i bardzo przydatnym) następstwem powyższych:

Następstwo (ryż, rozszerzone). Biorąc pod uwagę nietrywialną właściwość , tak że , język nie jest wymienny rekurencyjnie, to znaczy . $S \subsetneq RE$ $\emptyset \in S$
$L_{S} = {⟨ M ⟩ ∣ L (M) \in S}$ $L_S = \{ \langle M \rangle \mid L(M) \in S \}$ $L_S \notin RE$

— Ran G.
źródło

Dziękujemy za dodanie rozszerzonej wersji twierdzenia Rice'a! Znam inną wersję; Będę musiał to wykopać. W każdym razie nie sądzę, aby posiadanie dowodów było bardzo ważne lub nawet pomocne. Może możesz odwołać się do nich lub przesłać je gdzie indziej, jeśli nie ma dobrego odniesienia?

— Raphael

13

Jednym z przydatnych narzędzi jest twierdzenie Rice'a . Oto, co mówi:

Niech nietrywialnym zestaw części obliczeniowych funkcji pojedynczych, i Gödel numeracja od . Następnie zestaw indeksów $\emptyset \subsetneq P \subsetneq \mathcal{P}$ $\varphi$ $\mathcal{P}$ $P$

$\qquad I_P = \{ i \in \mathbb{N} \mid \varphi_i \in P \}$

nie jest rekurencyjny.

Można go również znaleźć w postaci kodowania maszyn Turinga (lub dowolnego innego języka programowania Turinga), tj. ; tutaj definiuje numerację Gödla. $I_P = \{ \langle M \rangle \mid M\ \mathrm{TM}, f_M \in P \}$ $\langle . \rangle$

To znaczy, możesz użyć twierdzenia Rice'a, aby udowodnić takie zbiory nierekurencyjne, które są zestawami indeksów nietrywialnych zbiorów funkcji (lub takie można sprowadzać do ). $S$ $S$

Zauważ, że istnieje rozszerzenie, którego można użyć, aby pokazać, że niektóre zestawy indeksów nie są wymienne rekurencyjnie.

Przykład

Niech ma numerację Gödla. Rozważ zestaw naturals $\varphi$

$\qquad A = \{ i \in \mathbb{N} \mid \varphi_i(j) = 1 \text{ for all } j \in 2\mathbb{N} \}$ .

Teraz, ponieważ dla $P = \{ f \in \mathcal{P} \mid f(j) = 1 \text{ for all } j \in 2\mathbb{N} \}$

$A = I_P$ ,
$(n \mapsto 1) \in P$ i
$(n \mapsto 2) \notin P$ ,

Twierdzenie Rice'a można zastosować, a nie jest rozstrzygalne. $A$

Ponieważ wielu nie zna numeracji Gödla, należy zauważyć, że przykład działa również w zakresie maszyn Turinga (tj. Programów), używając . $A = \{ \langle M \rangle \mid f_M(x) = 1 \text{ for all } x \in 2\mathbb{N} \}$

Nieprzygotowany

Rozważ zestaw naturals

$\qquad A = \{ i \in \mathbb{N} \mid \varphi_i(j) = i \text{ for all } j \in 2\mathbb{N} \}$

co z pewnością nie jest obliczalne. Jednak nie jest zestawem indeksów dla żadnego ! Niech jakiegoś . Ponieważ jest numeracją Gödla , istnieje (nieskończenie wiele) z ale dla wszystkich wstrzymanych, ponieważ . $A$ $P$ $f=\varphi_i$ $i \in A$ $\varphi$ $j \neq i$ $\varphi_j = f$ $j \notin A$ $f(2)=i \neq j$

Uważaj na to! Zasadniczo, jeśli indeks funkcji jest używany po „prawej stronie” lub jako parametr funkcji w definicji zestawu, prawdopodobnie nie jest to zestaw indeksów. Może być potrzebna właściwość numeracji Gödla i twierdzenie o punkcie stałym, aby pokazać, że zbiór nie jest zestawem indeksów. $s_{mn}$

Zobacz tutaj i tutaj pokrewne posty na temat twierdzenia Rice'a.

— Raphael
źródło