Czy maszyna Turinga (TM) może zdecydować, czy problem zatrzymania dotyczy wszystkich baz TM?

9

Na tej stronie istnieje wiele wariantów pytania, czy bazy TM mogą zadecydować o problemie zatrzymania, czy dla wszystkich innych baz TM lub niektórych podzbiorów. To pytanie jest nieco inne.

Pytanie, czy problem zatrzymania dotyczy wszystkich baz TM może zostać rozstrzygnięty przez TM. Uważam, że odpowiedź brzmi „nie” i chcę sprawdzić moje rozumowanie.

Zdefiniuj język meta-zatrzymujący jako język złożony z baz TM, które decydują o tym, czy baza TM zostanie zatrzymana. $L_{MH}$

L_{M H} = {M : \forall_{M^{'}, w} M (M^{'}, w) accepts if M^{'} (w) halts, rejects otherwise}

$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$

powodu problemu zatrzymania. $L_{MH}= \emptyset$

Tak więc pytanie tytułowe bardziej precyzyjnie brzmi: czy można rozstrzygnąć, czy ? $L_{MH} = \emptyset$

Zgodnie z twierdzeniem Rice'a nierozstrzygalne jest, czy re-język jest pusty.
W obu przypadkach, jeśli jest lub nie jest ponownie, nierozstrzygalne jest, czy . $L_{MH}$ $L_{MH} = \emptyset$
Dlatego nie można rozstrzygnąć, czy . $L_{MH} = \emptyset$

To dowodzi, że baza TM nie może zdecydować, czy problem zatrzymania dotyczy wszystkich baz TM.

Czy moje rozumowanie jest prawidłowe?

AKTUALIZACJA: Próbuję wykazać, że baza TM nie może „udowodnić problemu zatrzymania” dla jakiejś definicji „udowodnienia”, która wydaje się intuicyjnie poprawna. Poniżej znajduje się ilustracja, dlaczego uważam, że jest to poprawne.

Możemy stworzyć TM który generuje w następujący sposób. TM zajmuje krotkę . Symuluje o iteracji. Jeśli akceptuje wszystko $M_{MH}$ $L_{MH}$ $(M_i,M_j,w_k,steps)$ $M_i(M_j, w_k)$ $steps$ $M_i$ $(M_j, w_k)$ pary, które zatrzymują się i odrzucają wszystkie inne, a następnie akceptuje . W przeciwnym razie odrzuca jeśli podejmie błędną decyzję lub się nie zatrzyma. $M_{MH}$ $M_i$ $M_i$ $M_i$

nie zatrzymuje się, ponieważ musi ocenić nieskończoną liczbę par dla każdego . Dodatkowo, wszystkie s nie zatrzymają się. nie będzie w stanie zaakceptować ani odrzucić żadnej ponieważ z symulacji nie dowie się, że wszystkie nie zatrzymają się. Tak więc język, który definiuje, nie jest ani rozstrzygalny. $M_{MH}$ $M_i$ $M_i$ $M_{MH}$ $M_i$ $M_i$

wychwytuje moją intuicję, co według mnie oznacza dla TM udowodnienie problemu zatrzymania. Inne propozycje, takie jak odrzucające wszystko lub wyprowadzania znany dowód Daj wcześniejszej wiedzy, że zatrzymanie problem dotyczy wszystkich . Nie można tego uznać zadowód, że coś dowodzi, ponieważ przesłanka jest wnioskiem, który dowodzi, a zatem jest okrągła. $M_{MH}$ $M_{MH}$ $M_i$ $M_{MH}$ $M_i$ $M_{MH}$ $M_{MH}$

— yters
źródło

3

Twoja poprawka nie pomaga. Problem bez parametrów jest zawsze rozstrzygalny, albo przez maszynę Turinga, która zawsze wysyła TAK, albo przez tę, która zawsze wysyła NIE. Twoja linia argumentów po prostu nie działa, niestety. Prawdziwym analogiem twierdzenia Gödla jest twierdzenie Rice'a.

— Yuval Filmus

5

„Pytanie, czy problem zatrzymania dotyczy wszystkich baz TM może zostać rozstrzygnięty przez TM”. - to zapytanie nie ma sensu, ponieważ problem zatrzymania nie „dotyczy” zestawu baz TM. Przynajmniej nie wiem, co to znaczy.

— Raphael

4

{M : L (M) = \emptyset}

$\{ M : L(M) = \emptyset \}$

\emptyset

$\emptyset$

\emptyset

$\emptyset$

7

Myślę, że nieporozumienie dotyczy tego, co oznacza wyrażenie „decydowanie X”. Formalnie, X powinno być orzecznikiem na sznurkach, a następnie maszyna decydując X jest taki, który na wejściu s wyjść wartość logiczna X ( s ). Jaki jest predykat w twoim przypadku? Jaki jest jego wkład i kiedy to prawda?

— Yuval Filmus

5

X

$X$

X

$X$

5

$\varphi$ $L_{MH} = \emptyset$

$P = \{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\}$
$M$ $\varphi$ $\neg \varphi$ $M$
$\{ M \mid M \mbox{ decides } P \}$

— Vor
źródło

19

Język maszyn Turinga decydujących o problemie zatrzymania jest rozstrzygalny. Maszyna Turinga, która decyduje o tym, po prostu zawsze wyprowadza NIE.

$\emptyset$

$T$ $L(T) = \emptyset$

— Yuval Filmus
źródło

7

Pusty język jest rozstrzygalny. Sobie z tym poradzić.

— Yuval Filmus

15

Język maszyn Turinga decydujących o problemie zatrzymania jest pusty. Pusty język jest rozstrzygalny. Dlatego język maszyn Turinga decydujący o problemie zatrzymania jest rozstrzygalny.

— Yuval Filmus

1

Pytanie brzmi, czy TM może zdecydować, że język maszyn Turinga decydujący o problemie zatrzymania jest pusty. TM nie może tego zrobić, jak pokazałem powyżej.

— po

1

@yters Czy pytasz, czy TM może udowodnić, że ten język jest pusty? Można to łatwo zrobić, po prostu wydając istniejący znany dowód.

— user253751

3

Co to znaczy, że TM coś udowodni ?

— Yuval Filmus

2

Nie rozumiesz twierdzenia Rice'a.

Twierdzenie Rice'a w tym kontekście mówi, że nie można rozstrzygnąć problemu „Czy T decyduje o pustym języku?”.

Twój problem nie polega na decydowaniu, czy dowolna maszyna Turinga decyduje o pustym języku. Twój problem polega na tym, czy istnieje M, które decyduje o pustym języku.

I takie M istnieje. Możesz zrobić jeszcze więcej: możesz zbudować taki M i udowodnić , że decyduje on o pustym języku.

Ogólny problem nierozstrzygalny nie oznacza, że nie można rozwiązać określonych przypadków. W rzeczywistości, za pomocą zwykłego urządzenia do wyliczania wszystkich dowodów, istnieje maszyna Turinga, która:

Akceptuje każdą maszynę Turinga, dla której istnieje dowód, że decyduje o pustym języku
Odrzuca każdą maszynę Turinga, dla której istnieje dowód, że nie decyduje o pustym języku
Nie zatrzymuje się, jeśli nie da się tego udowodnić w żaden sposób.

1

Definicja rozstrzygalności z Wikipedii :

Język rekurencyjny jest językiem formalnym, dla którego istnieje maszyna Turinga, która po przedstawieniu dowolnego skończonego ciągu wejściowego zatrzymuje się i akceptuje, jeśli ciąg jest w języku, a także zatrzymuje się i odrzuca inaczej. Maszyna Turinga zawsze zatrzymuje się: jest znana jako decydująca i mówi się, że decyduje o języku rekurencyjnym.

Innymi słowy, jest rozstrzygalne, jeśli istnieje maszyna Turinga, która decyduje o wszystkich ciągach wejściowych. Jest niezdecydowany iff dla każdej maszyny Turinga, nie decyduje o wszystkich ciągach wejściowych, co oznacza, że może decydować o braku lub niektórych ciągach, ale istnieje co najmniej jeden (ale praktycznie nieskończony z nich), którego nie może zdecydować.

$L$ $L = \emptyset$ $L_{MH} = \emptyset$

— użytkownik23013
źródło