Unele probleme sunt indecidabile: niciun calculator nu le poate rezolva, oricât de puternic ar fi.
Gândește-te la un puzzle imposibil: vrei să știi dacă un program se va bloca vreodată, dar nu poți afla sigur. Turing a arătat că există întrebări la care calculatoarele nu pot răspunde niciodată, chiar dacă sunt foarte rapide. Este ca și cum ai încerca să găsești o comoară care nu există.
Să zicem că scrii un program care verifică dacă alt program se blochează. Turing a demonstrat că un astfel de verificator universal nu poate exista. Asta înseamnă că, oricât de inteligent ai fi, nu poți construi o mașină care să prezică toate blocările. E ca și cum ai încerca să creezi o listă completă a tuturor minciunilor posibile. În viața de zi cu zi, asta explică de ce antivirusul tău ratează uneori amenințări noi.
De ce contează Această limită a calculului ne ajută să înțelegem de ce unele probleme, cum ar fi securitatea perfectă, sunt imposibile.