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 forever

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