Dowód nierozstrzygalności problemu zatrzymania

25

Mam problem ze zrozumieniem dowodu nierozstrzygalności problemu zatrzymania.

Jeśli zwraca, czy program zatrzymuje się na wejściu , dlaczego musimy przekazać kod zarówno dla jak i ? $H(a,b)$ $a$ $b$ $P$ $a$ $b$

Dlaczego nie możemy karmić z i jakimś arbitralnym wejściowego, powiedzmy, ? $H()$ $P$ $x$

computability turing-machines

— Netik
źródło

Należy pamiętać, że w stosowanym tutaj modelu obliczeniowym dozwolone są wszelkie (zakodowane) dane wejściowe. Nie ma sprawdzania typu ani nic podobnego. Zawsze możesz zakodować program i przekazać go jako dane wejściowe dla siebie.

— asmeurer

2

Państwo mogłoby wyżywić

cokolwiek wejście chcesz. Struktura tego dowodu wymaga uwzględnienia konkretnego wkładu.

H

$H$

— David Richerby,

1

Możesz podać dowolne dane wejściowe do programu. Celem jest znalezienie sprzeczności. Teoretycznie maszyna „H” powinna działać dla wszystkich rodzajów danych wejściowych. Dlatego rozważamy jeden z wszystkich możliwych danych wejściowych, który prowadzi do sprzeczności.

— Ugnes,

Ten dowód jest subtelnie wadliwy. Zastanów się, czy mam H (), która działa na wszystko oprócz siebie; byłoby to nadal ogólne rozwiązanie problemu zatrzymania.

— Joshua

Powiązane, być może duplikat: cs.stackexchange.com/questions/42819/…

— Ilmari Karonen

27

Dowód ma na celu znalezienie sprzeczności. Musisz zrozumieć, czym jest wyprowadzona sprzeczność, aby zrozumieć, dlaczego jest używane jako wkład do samego siebie. Sprzeczność jest, nieformalnie: jeśli mamy maszynę H (a, b), która decyduje „a akceptuje b”, wówczas możemy zbudować maszynę, która akceptuje maszyny, które same się nie akceptują. (Czytałem, że kilka razy, aż do uzyskania go.) Urządzenie pokazane na rysunku - nazwijmy go - nie nie akceptuje ? $P$ $M$ $M(P) =$ $P$ $\langle P \rangle$

Sprzeczność się dzieje, gdy zapytać: czy zaakceptować ? Spróbuj obliczyć dwie opcje, aby zobaczyć, jak istnieje sprzeczność. $M$ $\langle M \rangle$

akceptuje wtedy i tylko wtedy, gdy nie akceptuje ; jest to wyraźnie sprzeczność. $M$ $\langle M \rangle$ $M$ $\langle M \rangle$

Dlatego tak ważne jest, aby dowód uruchamiał na sobie, a nie na dowolnych danych wejściowych. Jest to powszechny temat w dowodach niemożliwości, znanych jako argumenty przekątne. $P$

— aelguindy
źródło

38

Zignoruj na chwilę obraz; dojdziemy do tego wkrótce. Program ma być testerem halt: kiedy dajemy wejście programu (zespoły jako listę programu) oraz w ogóle cokolwiek dla , działa w następujący sposób $H(a, b)$ $H$ $a$ $a$ $b$ $H(a, b)$

Jeśli program reprezentowany przez przystankach przy podawaniu jako wejścia, odpowie „tak”. Z drugiej strony, jeśli program opisany przez tras zawsze gdy danego wejścia następnie odpowie „nie”. $a$ $b$ $H(a, b)$ $a$ $b$ $H(a, b)$
Co ważne, program zawsze się zatrzymuje i daje poprawną odpowiedź dla każdej pary . $H$ $(a, b)$

Argument, że jest niemożliwy do zbudowania, opiera się na działaniu określonego „perwersyjnego” programu , takiego, który wykorzystuje jako podprogram. przyjmuje jako dane wejściowe listę dowolnego programu, i wykonuje następujące czynności: $H$ $P$ $H$ $P$ $x$

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

Nietrudno to dostrzec

zatrzyma się wtedy i tylko wtedy, gdy program będzie działał wiecznie, jeśli otrzyma swój własny opis jako dane wejściowe. $P(x)$ $x$

Jak dotąd tak dobrze: z pewnością będzie programem, o ile jego podprogram jest programem. $P$ $H$

$P$ $p$ $P$

$P(p)$ $P(p)$

$H$ $(p, p)$ $H$ $H$

— Rick Decker
źródło

Podoba mi się ta odpowiedź. Chociaż teraz, gdy rozumiem dowód, wydaje się, że po prostu dowodzi, że H może zgłosić wyjątek dotyczący limitu rekurencji.

— Faks

2

@Fax Hnie jest wywoływany więcej niż raz, nie ma żadnej rekurencji P. H(P, P)nie wykonuje się P, po prostu „magicznie” określa, czy Pzatrzymuje się po przejściu.

— Ajedi32,

@ Ajedi32 H(P,P)nie musi być wykonywany P, ale musi być wykonywany H(x ↦ H(x,x), P)w ramach określania, czy ma się Pzatrzymać. Który rozwija się H(x ↦ H(y ↦ H(y,y), x), P)i tak dalej.

— Faks

@Fax Implementacja Hnie jest określona w tym dowodzie. Więc nie, nie musi niczego wykonywać, czy to będzie, Pczy samo. Dowód zaczyna się od założenia, że Histnieje jakiś program , który magicznie decyduje o problemie zatrzymania, a następnie udowadnia, że samo istnienie takiego programu byłoby sprzecznością, a zatem taki program nie istnieje.

— Ajedi32

1

@Fax Podnosisz jednak sensowną kwestię, czy może istnieć program, który decyduje o problemie zatrzymania, z wyjątkiem sytuacji, gdy jest wywoływany sam. Zobacz Czy istnieją dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samodzielnego odniesienia lub diagonalizacji? za interesujące pytanie na ten temat.

— Ajedi32,

9

Wypróbuj ładniejszy dowód z animacjami. A ponieważ odpowiedzi powinny zawierać coś więcej niż link do strony, oto odpowiedź na twoje pytanie.

Po pierwsze, przypomnijmy sobie, jak działa dowód nieistnienia wyroczni w Halting. Udowadniamy, że biorąc pod uwagę każdego kandydata Hna wyrocznię z Stopu, istnieje program Pi dane wejściowe, adla których Hnie można poprawnie przewidzieć, co P(a)się stanie.

Twierdzenie: Niech Hbędzie dowolnym programem, który pobiera dwa dane wejściowe i zawsze zwraca albo haltalbo loop. Istnieje program Qi dane wejściowe a, które Q(a)zatrzymują się, jeśli i tylko jeśli H(Q,a)powróci loop.

Dowód. Rozważ program

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Niech Q = Pi a = P. Albo H(Q,a) = haltalbo H(Q,a) = loop:

jeśli H(Q,a) = haltwtedy Q(a)(co jest sprawiedliwe P(P)) działa wiecznie zgodnie z definicją P.
jeśli H(Q,a) = loopnastępnie Q(a)zatrzymają się z definitywnością P.

CO BYŁO DO OKAZANIA

Zapytałeś, dlaczego rozważamy H(P,P)zamiast H(P,X)jakiegoś innego X. Oczywista odpowiedź brzmi „ponieważ H(P,P)to sprawia, że dowód działa”! Jeśli użyjesz H(P,X)jakiegoś arbitralnego X, utkniesz. Rzeczywiście, dowód wyglądałby następująco:

Złamany dowód. Rozważ program

program P(y):
  if H(y,y) = halt then
    loop forever
  else:
    return

Niech Q = Pi a = Xdla niektórych dowolnych X. Albo H(Q,X) = haltalbo H(Q,X) = loop:

załóżmy, H(Q,X) = haltże nie możemy powiedzieć, co P(X)robi, ponieważ to, czy P(X)zatrzymanie zależy od tego, co H(X,X)powróci. Utknęliśmy. Gdybyśmy jednak wiedzieli o tym P(X)i byli X(X)tacy sami, moglibyśmy poczynić postępy. (Więc naprawdę powinniśmy wziąć X = P).
jeśli H(Q,a) = loopwtedy utkniemy ponownie, i utknęlibyśmy, gdyby X = P.

Brak QED.

Mam nadzieję, że to pokazuje, że musimy rozważyć H(P,P), aby nasz pomysł zadziałał.

— Andrej Bauer
źródło

Ha ha. Niesamowite! :)

— aelguindy,

2

Rezultatem dowodu jest ta analogia:

$P$ $_{(P)}$ $P^{\prime}$ $_{(P^{\prime})}$ $P$ $_{(P)}$ $_{(P)}$ $_{(P)}$

$_{(P)}$ $_{(P^{\prime})}$

— Ahmed Nassar
źródło