Synteza programu, rozstrzygalność i problem zatrzymania

Czytałem odpowiedź na ostatnie pytanie i przyszło mi do głowy coś dziwnego, efemerycznego. Moje pytanie może zdradzić, że moim teoretycznym kotletom poważnie brakuje (głównie prawdy) lub że jest zbyt wcześnie, aby przeczytać tę stronę. Teraz, gdy wyłączenie odpowiedzialności jest na drodze ...

Jest to dobrze znany wynik teorii obliczeń, że problem zatrzymania nie może być rozstrzygnięty dla baz TM. Nie wyklucza to jednak możliwości istnienia maszyn, które mogą rozwiązać problem zatrzymania dla niektórych klas maszyn (tylko nie wszystkie).

Rozważ zestaw wszystkich rozstrzygalnych problemów. Dla każdego problemu istnieje nieskończenie wiele baz TM, które decydują o tym języku. Czy możliwe są następujące

Istnieje TM, która decyduje o problemie zatrzymania podzbioru maszyn Turinga; i $S$
Wszystkie rozstrzygalne problemy są rozwiązywane przez co najmniej jedną maszynę Turinga w ? $S$

Oczywiście znalezienie maszyny Turinga w może nie być samo obliczalne; ale ignorujemy ten problem. $S$

EDYCJA: Na podstawie poniższej odpowiedzi Shaulla wydaje się, że (a) ta idea jest zbyt źle sprecyzowana, aby była znacząca, lub (b) moja poprzednia próba nie była całkiem trafna. Ponieważ staram się wypracować w komentarzach do odpowiedzi Shaull jest, moim zamiarem nie jest to, że mamy zagwarantowane, że TM jest w wejście . To, co naprawdę rozumiem przez moje pytanie, brzmi: czy mogłaby istnieć taka , tak że członkostwo w jest decydującym problemem . Program do rozwiązania problemu zatrzymania dla przypuszczalnie zapisałby „nieprawidłowe wejście” na taśmie lub coś innego, gdyby otrzymał dane wejściowe, które rozpoznaje jako nie będące w $S$ $S$ $S$ $S$ $S$ . Kiedy tak sformułuję, nie jestem pewien, czy to pozwala nam rozwiązać problem zatrzymania, czy też nie, czy ma zastosowanie twierdzenie Rice'a (czy rozstrzygalność jest właściwością semantyczną języka w stosunku do twierdzenia Rice'a?)

turing-machines undecidability halting-problem Patrick87
źródło

myślę, że gdzieś tutaj czai się uzasadnione / znaczące pytanie na granicach teorii, ale nie w obecnej formie, jednak +1 za próbę [i to zrzeczenie się na początku jest zaskakujące, biorąc pod uwagę twój status przedstawiciela / moderatora] ... może to jest pytanie, które czytałeś? algorytm rozwiązania problemu zatrzymania

turings

być może inny sposób sformułowania pytania, nie wiem, czy taka była intencja (co czyni go bardzo zaawansowanym). rozważ wszystkie możliwe „algorytmy quasialn” i powiązane z nimi uznane zestawy . [patrz inne pytanie dotyczące defns]. czy unia wszystkich takich uznanych zbiorów równa wszystkich rekurencyjnych / rozstrzygalnych baz TM?

S_{n}

$S_n$

S_{n}

$S_n$

dniu

Myślę, że może być problem z sformułowaniem problemu.

Rozważmy zestaw decyduje o jego języku . Problem zatrzymania jest rozstrzygalny dla tego zestawu (to znaczy, jeśli obiecano nam, że dane wejściowe są w tym zestawie). W rzeczywistości jest to trywialne (maszyny w zawsze zatrzymują się). $S=\{M: M$ $\}$ $S$

Również wyraźnie każdy język rozstrzygalne jest w . $S$

EDYCJA: Na podstawie zmian w pytaniu - w rzeczywistości członkostwo w byłoby nierozstrzygalne: jeśli zawiera maszynę dla każdego rozstrzygalnego języka, to . W ten sposób, Twierdzenie Rice'a, jeśli jest rozstrzygalne następnie zawiera każdą maszynę, ale potem zatrzymanie problemem jest nierozstrzygalny na . $S$ $S$ $S\neq \emptyset$ $S$ $S$ $S$

Shaull
źródło

Innymi słowy,

trywialnie odpowiada na pytanie pozytywnie.

S = {⟨ A ⟩ ∣ \forall x . A (x) ↓, L (A) \in R}

$S = \{\langle A \rangle \mid \forall x. A(x) \downarrow, L(A) \in \mathrm{R}\}$

Raphael

@ Rafael - nie, ponieważ choć

, nie oznacza to, że

jest decydującym. Dlatego wyraźnie podejmujemy decyzje.

L (A) \in R

$L(A)\in R$

A

$A$

Shaull

Ah, tak. Naprawiono komentarz.

Raphael

+1 Nie jestem pewien, czy jasno przekazałem swoje znaczenie. Co tak naprawdę oznaczało zapytać: czy to możliwe, że taki

istnieje i możemy sprawdzić, jak dowolny TM, aby zobaczyć czy jest w

. Nie wiemy a priori , że jest w

; tylko to, że

jest sformułowane w taki sposób, że możemy to sprawdzić. Innymi słowy, czy jest możliwe, że istnieje

tak że członkostwo w

jest rozstrzygalne? Twoje ostatnie zdanie jest nieco mylące;

to zestaw Maszyn Turinga (cóż, ich reprezentacje); nie z języków, które decydują TM, ale myślę, że wiem, co masz na myśli.

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

S

$S$

Patrick87

(ps Niestety o uzyskanie imię złego w moim edycji Jest zbyt wcześnie dla mnie zrobić CS.SE zaczyna pojawiać się coraz bardziej prawdopodobne.)

Patrick87

Synteza programu, rozstrzygalność i problem zatrzymania

Odpowiedzi: