Czy rozstrzygalność jest rozstrzygalna?

Zastanawiam się, czy decydowanie o rozstrzygalności problemu jest problemem rozstrzygalnym. Chyba nie, ale po wstępnych poszukiwaniach nie mogę znaleźć literatury na ten temat.

computability undecidability decision-problem synchronizacja
źródło

Hej, stary

Na twoje pytanie nie można odpowiedzieć w obecnej formie, jak pokazują dwie odpowiedzi, które w zasadzie mówią „Trywialnie, nie” i „Trywialnie, tak” (z dodatkowym komentarzem mówiącym „nie” na „nie”). Zapytałeś, czy problem można rozstrzygnąć, ale nie zdefiniowałeś, na czym on polega. W szczególności, jaki jest wkład? Jeśli chcesz zaprojektować maszynę Turinga , który powie Ci, czy problem jest rozstrzygalne, trzeba dać ten problem jako wkład do . Ale jak ty to robisz?

M

$M$

M

$M$

David Richerby,

Biorąc pod uwagę obecne odpowiedzi, pojawia się pytanie „Czy decyzja jest decydująca Decydowalność jest rozstrzygalna?”, Ale nie zamierzam o to pytać :-)

Mark Hurd

Odpowiedzi:

Główna edycja mojego oryginału:

Naiwne czytanie twojego pytania wydaje się być, niech będzie problemem $P$

$P=$ danym języku jest rozstrzygalne? $L$

Więc pytasz

Czy rozstrzygalne? $P$

Jak zauważyli DW i David, odpowiedź brzmi „tak”, choć nie wiemy, który z dwóch trywialnych decydentów jest właściwy. Sugeruję to, aby ułożyć problem tak, aby nie był tak trywialny. Najpierw rzeczy nieco ograniczyć poprzez uwzględnienie tylko tych języków , które są językami zaakceptowane przez jakiś TM . Powodem tego jest to, że jeśli język nie jest akceptowany przez żadną bazę TM, to nie jest on ponownie (rozpoznawalny), a zatem nie może być rekurencyjny (rozstrzygalny). Następnie możemy przekształcić jako $L(M)$ $M$ $P$

$P'=$ Biorąc pod uwagę opis, TM, czy rozstrzygalne? $\langle M\rangle$ $M$ $L(M)$

Teraz jest językiem opisów TM, a nie językiem, jakim wydawało się (pod hojną interpretacją), i teraz jest całkowicie rozsądne pytanie, czy język jest rozstrzygalny. W tym czytaniu język składający się z opisów TM nie jest rozstrzygalny. Jest to łatwa konsekwencja twierdzenia Rice'a . Mamy teraz dwie odpowiedzi: moje „nie” i „tak” DW, w zależności od interpretacji. $P'$ $P$ $P'$

{⟨ M ⟩ ∣ M is a TM and L (M) is decidable}

$\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}$

Rick Decker
źródło

Dziękuję Ci! Zrozumienie, przynajmniej płytko, obie odpowiedzi dały mi informacje, których szukałem, czyli w przybliżeniu: „Czy możemy stworzyć maszynę, która może decydować o tym, co może, a czego nie decydować w ogóle?” (Wiem, że nie jest to dobre frazowanie, ale nie mogę wymyślić lepszego frazowania.) Bardzo pomocne, zwłaszcza, że uznajesz obie interpretacje.

zsynchronizować

Pomyślałem, że pokazanie, że dla każdego rozstrzygalnego problemu istnieje certyfikat (algorytm z dowodem) i dla każdego nierozstrzygalnego problemu istnieje również certyfikat (zmniejszenie z nierozstrzygalnego problemu).

rus9384

Jak widzieliśmy w różnych odpowiedziach, część odpowiedzi polega na sformułowaniu właściwego problemu.

W 1985 r. Joost Engelfriet napisał „Nieobliczalność obliczeń” (Biuletyn EATCS nr 26, czerwiec 1985 r., Strony 36–39) jako odpowiedź na pytanie zadane przez sprytnego studenta. Niestety, BEATCS było wtedy w wersji papierowej, a artykuł nie pozostawił elektronicznych śladów.

$\Psi$ $F(m,n)$ $f:\Bbb N \to \Bbb N$ $m,n\in \Bbb N$ $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ $\underline m$ $m$

Cytuję:

$\Phi$ $\Bbb N \to \Bbb N$ $f$ $f$

Zabawną częścią są następujące spostrzeżenia poczynione w artykule:

$\Phi$

Hendrik Jan
źródło

Tak. Zawsze jest rozstrzygalne.

Dla każdego problemu P, niech Q będzie problemem ustalenia, czy P jest rozstrzygalne, czy nie. Twierdzę, że Q jest rozstrzygalne. Dlatego. Tautologicznie albo P jest rozstrzygalne, albo nie. Tak więc jeden z dwóch programów jest poprawny: (1) print "yup P is decidable"lub (2) print "nope P is not decidable". Ustalenie, który z tych dwóch programów jest poprawny, jeden z nich jest prawidłowy, więc decydujący dla Q na pewno istnieje . Dlatego problem Q jest rozstrzygalny.

Przypomina to następujące klasyczne pytanie: czy można rozstrzygnąć, czy hipoteza Collatza jest prawdziwa? Odpowiedź brzmi tak. Może to wyglądać dziwnie, ponieważ nikt nie wie, czy Hipoteza Collatza jest prawdziwa (to słynny otwarty problem). Wiemy jednak, że hipoteza Collatza jest albo prawdziwa, albo nieprawda. W pierwszym przypadku program print "yup it's true"jest decydujący. W tym drugim przypadku program print "nope it's not true"jest decydujący. Nie wiemy, który z nich jest prawidłowym decydentem, ale to wystarczy, aby udowodnić, że istnieje prawidłowy decydent. Dlatego problem jest rozstrzygalny.

DW
źródło

Myślę, że interpretacja tego pytania przez Ricky Deckera jest lepsza. Biorąc pod uwagę pewne kodowanie problemu, zdecyduj, czy problem jest rozstrzygalny.

Yuval Filmus

@YuvalFilmus, OK, to rozsądne. Czy masz skończone kodowanie problemów (tj. Języków), które uważasz za rozsądne i nie sprawiają, że problem jest trywialny? Naturalne skończone kodowanie języka jest jak maszyna Turinga, która rozpoznaje ten język, ale sprawia, że problem jest trywialny, jak ilustruje twój komentarz do odpowiedzi Ricky Deckera. Potrzebowalibyśmy więc innego rozsądnego kodowania, które nie cierpi z powodu tego rodzaju problemów. Czy masz na to jakieś sugestie?

Możesz użyć logiki pierwszego rzędu w odpowiednim języku. Lub wejściem może być maszyna w 0 '(na przykład), tj. Maszyna Turinga z dostępem do wyroczni zatrzymującej.

Yuval Filmus

Z twierdzenia Rice'a wiemy, że nawet ustalenie R we wszechświecie RE jest nierozstrzygalne. Czy to nie wystarczy? (Nie wszystkie TM są decydujące.)

Raphael

Dziękuję Ci! Chociaż nie była to zamierzona przeze mnie interpretacja, pomogło mi to zrozumieć, dlaczego pytanie, które zadałem, może nie być wystarczająco dobrze sformułowane, aby odzwierciedlić moje zamiary.

zsynchronizować