Dowód nierozstrzygalności problemu zatrzymania

Mam problem ze zrozumieniem dowodu nierozstrzygalności problemu zatrzymania.

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

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

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 M - M ( P ) = nie P nie akceptuje ⟨ P ⟩ ?$P$$M$$M(P) =$$P$$\langle P \rangle$

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

akceptuje ⟨ M ⟩ wtedy i tylko wtedy, gdy M nie akceptuje ⟨ M ⟩ ; 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$

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

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

Argument, że jest niemożliwy do zbudowania, opiera się na działaniu określonego „perwersyjnego” programu P , takiego, który wykorzystuje H jako podprogram. P przyjmuje jako dane wejściowe listę dowolnego programu, x 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 x 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 H jest programem.$P$$H$

$P$$p$$P$

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

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

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ł.

Rezultatem dowodu jest ta analogia:

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

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