nierozstrzygalny problem i jego negacja jest nierozstrzygalna

Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie.

Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji Ld, ale nie wydaje mi się, aby dopełnienie było nierozstrzygalne.

Czy w takim przypadku oznacza to, że maszyna Turinga M może „zgubić” niektóre ciągi znaków, które zamiast tego powinny zostać rozpoznane, ponieważ są one częścią języka, który próbujemy zidentyfikować?

Rozważ następujący język:

$$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$

jest nierozstrzygalny i nierozstrzygalny, to samo dotyczy jego dopełnienia. Dlaczego? Intuicja mówi, że „ M 2 nie zatrzymuje się na wejściu x 2 ” nie jest częściowo rozstrzygalne, więc L 2 nie jest częściowo rozstrzygalne; a kiedy spojrzymy na uzupełnienie L 2 , to samo dzieje się z M 1 . Można to sformalizować ostrożniej, stosując redukcje.$L_2$$M_2$$x_2$$L_2$$L_2$$M_1$

Mówiąc bardziej ogólnie, jeśli jest językiem nierozstrzygalnym i nierozstrzygalnym, to wtedy$L$

$$L' = \{(x,y) : x \in L, y \notin L\}$$

spełnia twoje wymagania: jest nierozstrzygalna i nierozstrzygalna, to samo dotyczy dopełnienia L ′ .$L'$$L'$

Zauważ, że przeważająca większość problemów spełnia kryterium, którego szukasz: zarówno problem, jak i jego uzupełnienie nie są w połowie rozstrzygalne. Wynika to z faktu, że istnieje tylko policzalnie wiele problemów pół rozstrzygalnych, ale istnieje niezliczona ilość problemów.

Na przykład, niech być problemu stopu maszyn Turinga i pozwolić M mieć klasę urządzeń z Turinga ORACLE  H . Niech H 2 jest zatrzymanie problem  M . Twierdzę, że ani H 2, ani  ¯ H 2 nie są częściowo rozstrzygalne$H$$\cal{M}$$H$$H_2$$\cal{M}$$H_2$$\overline{H_2}$

$H_2$$\cal{M}$$H$$H_2$$T$$H$$T$$\cal{M}$$H_2$$H_2$

$\overline{H_2}$$\cal{M}$$H$$\overline{H_2}$$\cal{M}$$H_2$$\overline{H_2}$$\cal{M}$$\cal{M}$$H_2$$\cal{M}$$\overline{H_2}$$\cal{M}$$\overline{H_2}$$\cal{M}$$H$

Oto kilka naturalnych przykładów:

• $\Pi_2^0$

• $\Pi_2^0$

• $\Sigma_3^0$

$\Pi_2^0$$\Sigma_3^0$