Problemă de reziliere

Problema terminării (engleză Halting problem, tradusă și cu problema stoping sau problema stop) întreabă dacă este întotdeauna posibil, descrie un algoritm și o anumită intrare finalizată, pentru a determina dacă algoritmul în cauză se termină sau continuă să ruleze pe termen nelimitat . S-a demonstrat că nu poate exista un algoritm general capabil să rezolve problema pentru toate intrările posibile. Cea mai cunoscută versiune a problemei este cea propusă în 1936 de matematicianul Alan Turing , împreună cu dovada indecizibilității sale.

Dovada indecidabilității

Este absurd să presupunem că există un algoritm, implementat într-o pseudolingvă, care ia ca intrare orice alt algoritm a având o intrare finită d și este capabil să stabilească dacă a se termină în timp finit (returnând valoarea adevărată ) sau dacă există not terminate (returnând în acest caz valoarea false ).

 // halts () returnează true dacă intrarea sa se termină, false în caz contrar
C boolean ( a , d ):
    opriri de retur ( a ( d ));

Deoarece atât și mașină d au secvențe de simboluri indistinct, este posibil să se treacă același algoritm ca al doilea parametru al C, care este de a executa C (a, a).

Haideți acum să buclăm un program care nu se termină niciodată (de exemplu, în timp ce este adevărat ): este posibil să construim un alt algoritm numit K care, luând intrarea a, execută bucla, fără a returna nicio valoare dacă C (a, a) returnează adevărat , while returnează false dacă C (a, a) returnează false . Adică:

 // loop () este o funcție care nu se termină
K boolean ( a ):
dacă C ( a , a ) loop ();
întoarce-te adevărat ;

Deci K se încheie prin returnarea valorii adevărate numai dacă algoritmul a cu intrarea a nu se termină, altfel K continuă să se bucle buclând la nesfârșit fără a returna nicio valoare.

Trecând la algoritmul K același K, adică K (K) , acest algoritm se încheie, returnând valoarea adevărată , numai dacă algoritmul K cu intrarea K nu se termină. Adică, K (K) se încheie dacă și numai dacă K (K) nu se termină, ceea ce este o contradicție care se dovedește a fi absurdă ipoteza inițială privind existența unui algoritm C care, având în vedere orice algoritm a și intrarea sa d , este capabil să determine dacă a (d) se termină sau nu.

Dovadă că limbajul problemei de oprire este un limbaj indecidabil

Fie L _{H să} denumească limbajul problemei de oprire și să presupunem că L _H este decisiv. Apoi, prin definiție, există o mașină Turing T care decide L _H și că pentru orice intrare x se calculează T (x)

în starea de acceptare dacă x $\in$ ${\ displaystyle \ in}$ $\în$ L _H ;
în starea de respingere dacă x $\not \in$ ${\ displaystyle \ not \ in}$ ${\ displaystyle \ not \ in}$ L _H.

Din T obținem a doua mașină Turing T 'prin completarea stărilor de acceptare și respingere a mașinii T, deci calculul lui T' (x) merge

în starea de acceptare dacă x $\not \in$ ${\ displaystyle \ not \ in}$ ${\ displaystyle \ not \ in}$ L _H ;
în starea de respingere dacă x $\in$ ${\ displaystyle \ in}$ $\în$ L _H.

Din T 'derivăm o a treia mașină Turing T' 'care fie acceptă, fie nu se termină, de aceea calculul lui T' '(x) merge

în starea de acceptare dacă T 'acceptă;
nu se termină dacă T 'respinge.

Deoarece setul de mașini Turing Ť este numărabil atunci T $\in$ ${\ displaystyle \ in}$ $\în$ Ť asta înseamnă că $\exists$ ${\ displaystyle \ există}$ $\ există$ n $\in$ ${\ displaystyle \ in}$ $\în$ N (set de numere naturale) astfel încât T _n (n) = T '' (n).

Dacă T _n (n) acceptă atunci T '(n) ar trebui să accepte și el, dar dacă T' (n) acceptă atunci înseamnă că n $\not \in$ ${\ displaystyle \ not \ in}$ ${\ displaystyle \ not \ in}$ L _H și dacă n $\not \in$ ${\ displaystyle \ not \ in}$ ${\ displaystyle \ not \ in}$ L _H apoi T _n (n) respinge.

Dacă T _n (n) respinge atunci T '(n) ar trebui să respingă și el, dar dacă T' (n) respinge atunci n $\in$ ${\ displaystyle \ in}$ $\în$ L _H și dacă n $\in$ ${\ displaystyle \ in}$ $\în$ L _H atunci T _n (n) acceptă.

În ambele cazuri există o contradicție, prin urmare T '' nu există și din moment ce T '' se obține prin modificări simple la mașina T care decide L _H, acest lucru duce la a spune că L _H nu este decis.

Relațiile cu alte teoreme

Teorema lui Rice este o versiune mai generală a teoremei care afirmă că problema terminării este indecidabilă. De fapt, se afirmă că, pentru fiecare proprietate non-trivială a funcțiilor parțiale, problema determinării funcțiilor care îndeplinesc această proprietate și care nu este indecidabilă.

linkuri externe

( EN ) Problemă de terminare , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Controlul autorității	GND ( DE ) 4247732-3

Portal IT

Portalul de matematică