Opriți problema

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 noiembrie 2021; verificările necesită 4 modificări .

Problema opririi este una dintre problemele din teoria algoritmilor [1] , care poate fi afirmată informal ca:

Sunt oferite descrierea procedurii și datele de intrare inițiale ale acesteia. Este necesar să se determine: se va încheia vreodată executarea procedurii cu aceste date; sau că procedura va rula tot timpul fără oprire.

Alan Turing a dovedit în 1936 că problema opririi este indecidabilă pe o mașină Turing . Cu alte cuvinte, nu există un algoritm general pentru rezolvarea acestei probleme. [2]

Problema opririi este esențială pentru teoria computabilității, deoarece este primul exemplu de problemă care nu poate fi rezolvată algoritmic.

În ceea ce privește funcțiile, problema poate fi ușor descrisă după cum urmează:

Pentru orice funcție F(G, start_state) care poate determina dacă o altă funcție se oprește, puteți scrie întotdeauna o funcție G(start_state) care, atunci când este transmisă la F, va avea rezultatul opus al execuției așa cum prezice F.

Pentru multe alte sarcini[ ce? ] se poate dovedi indecizia lor algoritmică încercând să le reducă la problema opririi. Aceasta se face după schema „dimpotrivă”: să existe o anumită problemă pentru care se cere să-i stabilească insolubilitatea. Apoi presupunem că este rezolvabil și încercăm, folosind acest fapt, să scriem un algoritm pentru rezolvarea problemei de oprire pentru această problemă. Dacă acest lucru reușește, atunci vom ajunge la o contradicție, deoarece se știe că nu există un algoritm pentru rezolvarea problemei opririi. Aceasta înseamnă că presupunerea a fost greșită și că problema inițială este, de asemenea, de nerezolvat.

Dovada

Luați în considerare un set de algoritmi care iau un număr natural ca intrare și oferă, de asemenea, un număr natural ca ieșire. Să alegem un limbaj de programare complet Turing. Fiecare algoritm poate fi scris ca o secvență finită de caractere în acest limbaj. Să ordonăm mulțimea (acest lucru este posibil, deoarece este un set de secvențe finite de elemente ale unei mulțimi finite și, prin urmare, numărabile ), și fiecare algoritm va primi propriul său număr de serie. Să numim Analizorul un algoritm ipotetic care primește o pereche de numere naturale ca intrare și: $S$ $S$ $(N,X)$

se oprește și returnează 1 dacă algoritmul cu numărul nu se oprește după primire $N$ $X$
nu se oprește altfel (dacă algoritmul cu număr se oprește după primirea ). $N$ $X$

Problema opririi poate fi reformulată astfel: Există un Analizor?

Teorema. Analizorul nu există.

Să demonstrăm prin contradicție. Să presupunem că Analizorul există. Să scriem algoritmul Diagonalizer, care ia un număr ca intrare , transmite o pereche de argumente analizorului și returnează rezultatul muncii sale. Cu alte cuvinte, Diagonalizatorul se oprește dacă și numai dacă algoritmul cu număr nu se oprește după ce a primit numărul ca intrare . Fie numărul ordinal al Diagonalizatorului din mulțime . Rulați Diagonalizatorul trecându-i acest număr . Diagonalizatorul se va opri dacă și numai dacă algoritmul cu numărul (adică el însuși) nu se oprește atunci când primește un număr ca intrare (pe care i l-am transmis). Din această contradicție rezultă că presupunerea noastră este greșită: Analizorul nu există, ceea ce urma să fie demonstrat. $N$ $(N,N)$ $N$ $N$ $K$ $S$ $K$ $K$ $K$

Vezi și

Graficul fluxului de control poate fi folosit pentru a clasifica rapid atunci când programul nu are bucle (și, prin urmare, se oprește), are bucle triviale (și, prin urmare, se oprește), are bucle non-triviale (indecidabile) sau intră într-o buclă infinită.

Note

↑ N.K. Vereshchagin, A. Shen Prelegeri despre logica matematică și teoria algoritmilor. Partea 3. Funcții computerizate Arhivat 12 noiembrie 2015 la Wayback Machine
↑ Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society - London Mathematical Society , 1937. - Vol. s2-42, Iss. 1. - P. 230-265. — ISSN 0024-6115 ; 1460-244X - doi:10.1112/PLMS/S2-42.1.230 (în această publicație, Turing introduce definiția unei mașini Turing , formulează problema blocării și arată că aceasta, ca și problema rezoluției , este de nerezolvat).

Link -uri

c2:Problemă de oprire
Problemă cu înghețarea