[Teoria złożoności] Dowód dla Problemu Stopu

[_tommy_]

Witam,

Ostatnio trafiłem na Problem Stopu i dowód o jego nierozstrzygalności. Większość źródeł podaje dowód w formie jaki można znaleźć tutaj:

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/informatyka/algorytmy/2017/03/27/Problem_Stopu/

W pytaniu bazuję na oznaczeniach z artykułu z Delty.
Moje pytanie dotyczy tego, czy dla dowodu konieczne jest aby program P' otrzymywał jako argument samego siebie? Według mnie przy tej konstrukcji programu P' można byłoby go wywołać również z innymi parametrami.

Z góry dziękuję za wyjaśnienia!

[Afish]

No właśnie chodzi o to, żeby była ta rekurencja, bo inaczej nie możemy wnioskować.
Weźmy problem \(\displaystyle{ P'(K)}\). Jeżeli \(\displaystyle{ P(K, K)}\) się zatrzyma, to wtedy \(\displaystyle{ P'(K)}\) się nie zatrzyma, więc \(\displaystyle{ P(P', P')}\) zwróci false, ale z tego nic nie wywnioskujemy. Dopiero gdy \(\displaystyle{ K=P'}\), wtedy mamy sprzeczność i dowód, że \(\displaystyle{ P}\) nie istnieje. Podobna zasada jest w antynomii Grelinga.