Problema de oprire
Problema Halting este o problemă din domeniul informaticii. Problema constă în a analiza un program de calculator și în a afla dacă programul va funcționa la nesfârșit sau nu. Spunem că un program "rezolvă problema de întrerupere" dacă se poate uita la orice alt program și poate spune dacă acel alt program va funcționa la nesfârșit sau nu.
De exemplu, un program ca acesta:
while True: continuă;se va repeta la nesfârșit, dar programul
while False: continuă;se oprește foarte repede.
Există vreun program care să rezolve problema opririi? Se pare că nu există. Dovedim acest fapt arătând că, dacă există un program care rezolvă problema de întrerupere, atunci se întâmplă ceva imposibil. Așadar, pentru moment, ne vom comporta ca și cum ar exista într-adevăr un program care rezolvă problema opririi. Aici, P este o funcție care va evalua funcția F (apelată cu argumentul I) și va returna adevărat dacă se execută la nesfârșit și fals în caz contrar.
def P(F, I): if F(I) runs forever: return True; else: return False;P poate să se uite la orice program și să afle dacă acesta va funcționa la nesfârșit sau nu. Folosim P pentru a crea un nou program pe care îl vom numi Q. Ceea ce face Q este să se uite la un alt program și apoi să răspundă la următoarea întrebare: "Dacă rulăm acest program și îl facem să se uite la o copie a lui însuși, va funcționa la nesfârșit?". Putem crea Q deoarece avem P. Tot ce trebuie să facem este să îi spunem lui Q să creeze un nou program care este vechiul program care se privește pe el însuși, iar apoi să folosim P pentru a afla dacă noul program funcționează la nesfârșit sau nu.
def Q(F): return P(F, F);Acum creăm un alt program R. R se uită la un alt program și îi cere lui Q să răspundă la acel program. Dacă Q răspunde "da, dacă rulăm acest program și îl facem să se uite la o copie a lui însuși, va funcționa la nesfârșit", atunci R se oprește. Dacă Q răspunde "nu, dacă rulăm acest program și îl facem să se uite la o copie a lui însuși, acesta nu va rula la nesfârșit", atunci R intră într-o buclă infinită și rulează la nesfârșit.
def R(F): if Q(F): return; //terminare else: while True: continue; //loop foreverAcum vom vedea ce se întâmplă dacă facem ca R să se uite la o copie a sa. Se pot întâmpla două lucruri: fie se va opri, fie va rula la nesfârșit.
Dacă rularea lui R și obligarea lui R să se uite la o copie a sa nu se execută la nesfârșit, atunci Q a răspuns "da, dacă rulăm acest program și îl obligăm să se uite la o copie a sa, el se va executa la nesfârșit". Dar Q a spus acest lucru atunci când s-a uitat la R însuși. Deci, ceea ce a spus Q este de fapt: "da, dacă rulăm R și îl facem să se uite la o copie a sa, acesta va rula la nesfârșit". Așadar: Dacă R care rulează pe o copie a lui însuși nu rulează la nesfârșit, atunci el rulează la nesfârșit. Acest lucru este imposibil.
Dacă rularea lui R și obligarea lui R să se uite la o copie a lui însuși este veșnică, atunci Q a răspuns "nu, dacă rulăm acest program și îl obligăm să se uite la o copie a lui însuși, nu va fi veșnic". Dar Q a spus acest lucru atunci când se uită la R însuși. Deci ceea ce a spus Q de fapt este: "nu, dacă rulăm R și îl facem să se uite la o copie a sa, nu va rula la nesfârșit". Așadar: Dacă R care rulează pe o copie a lui însuși rulează la nesfârșit, atunci nu rulează la nesfârșit. Acest lucru este, de asemenea, imposibil.
Indiferent ce se întâmplă, avem parte de o situație imposibilă. Am făcut ceva greșit și trebuie să aflăm ce anume. Cele mai multe dintre lucrurile pe care le-am făcut nu au fost greșite. Nu putem spune că "a face un program să se uite la o copie a sa este greșit" sau că "a privi ce a spus un alt program și apoi a intra într-o buclă dacă acesta a spus un lucru și a se opri dacă a spus un alt lucru" este greșit. Nu are sens să spunem că nu ne este permis să facem aceste lucruri. Singurul lucru pe care l-am făcut și care pare să fie greșit este că am pretins că un program ca P există. Și din moment ce acesta este singurul lucru care ar putea fi greșit, și ceva trebuie să fie greșit, acesta este. Aceasta este dovada că un program ca P nu există. Nu există nici un program care să rezolve problema opririi.
Această dovadă a fost găsită de Alan Turing în 1936.
Întrebări și răspunsuri
Î: Ce este problema Halting?
R: Problema Halting este o problemă din domeniul informaticii care analizează un program de calculator și determină dacă programul va rula la nesfârșit sau nu.
Î: Cum știm dacă un program rezolvă problema Halting?
R: Spunem că un program "rezolvă problema halting" dacă se poate uita la orice alt program și poate spune dacă acel alt program va rula la nesfârșit sau nu.
Î: Există o modalitate de a dovedi că nu există un astfel de program?
R: Da, arătând că, dacă ar exista un astfel de program, atunci s-ar întâmpla ceva imposibil. Această dovadă a fost găsită de Alan Turing în 1936.
Î: Ce face P?
R: P este o funcție care evaluează o altă funcție F (apelată cu argumentul I) și returnează adevărat dacă se execută la nesfârșit și fals în caz contrar.
Î: Ce face Q?
R: Q analizează un alt program și apoi răspunde la întrebarea dacă rularea aceluiași program pe el însuși va duce sau nu la o buclă infinită. Aceasta se realizează prin utilizarea lui P pentru a face o evaluare a funcției F date.
Î: Ce face R?
R: R se uită la un alt program și îi cere lui Q să răspundă la acel program. Dacă Q răspunde "da, dacă rulăm acest program și îl facem să se uite la o copie a lui însuși, acesta va rula la nesfârșit", atunci R se oprește; cu toate acestea, dacă Q răspunde "nu, dacă rulăm acest program și îl facem să se uite la o copie a lui însuși, acesta nu va rula la nesfârșit", atunci R intră într-o buclă infinită și rulează la nesfârșit.
Î: Ce se întâmplă când îl faceți pe R să se privească pe sine însuși?
R: Se pot întâmpla două lucruri - fie R se oprește, fie rulează la nesfârșit - dar ambele rezultate sunt imposibile, conform celor dovedite cu privire la inexistența unor programe precum P, deci ceva trebuie să fi mers prost undeva pe drumul care a dus la obligarea lui R să se uite la el însuși.
