O problemă indecidabilă este o întrebare care nu poate fi rezolvată cu ajutorul unui singur algoritm. Acesta este un subiect de interes în matematică și programare computerizată, unde problema indecidabilă are implicații semnificative. Cercetătorii interesați de mașinile Turing, de exemplu, au abordat problema problemei opririi, uitându-se la momentul în care programele de calculator se opresc, față de rularea la infinit. Ca și în cazul altor provocări din matematică, cercetări considerabile înconjoară modalități de a ocoli problemele indecidabile, pe lângă identificarea de noi probleme pentru mai multă evaluare și studiu.
Acest subiect presupune probleme de decizie, întrebări cu răspunsuri da sau nu. În matematică, acestea sunt adesea prezentate sub formă de formule. Un exemplu simplu ar putea fi „Pentru orice număr real, este X divizibil egal cu Y?” Aceasta este o problemă decidabilă, deoarece dacă computerului i se dă vreo valoare pentru X sau Y, poate folosi un algoritm pentru a răspunde la întrebare. Este posibil ca problemele mai complexe să nu poată fi rezolvate cu un singur algoritm pentru toate valorile posibile.
În aceste cazuri, un algoritm poate fi corect pentru unele răspunsuri, dar ar putea fi incapabil să răspundă pentru alte valori. Având în vedere unele valori, algoritmul ar putea trece printr-o serie de pași pentru a determina dacă răspunsul la întrebare a fost da sau nu. În alte cazuri, nu ar putea face acest lucru deoarece i-ar lipsi informațiile necesare. Aceasta este o problemă cunoscută cu unele probleme care implică matrici, analize complexe și anumite alte funcții.
Identificarea unei probleme indecidabile poate apărea în contextul cercetării în matematică și informatică. Odată ce o problemă este considerată a fi indecidabilă, cercetătorii pot aplica o varietate de tactici pentru a infirma această teorie. Aceasta poate include dezvoltarea de algoritmi care funcționează pentru anumite valori, discutarea specificului problemei care fac imposibilă tratarea eficientă cu un algoritm pentru toate valorile și activitățile conexe. Publicațiile de matematică și informatică pot discuta cele mai recente progrese în acest domeniu cu exemple de algoritmi pe care cercetătorii i-au folosit pentru a explora limitele unei probleme indecidabile.
Departe de a fi doar un subiect de interes teoretic, problema indecidabilă poate avea implicații importante pentru lumea reală. De exemplu, unii viruși informatici prezintă sisteme cu probleme indecidabile. Încercarea sistemului de a rezolva problema poate consuma resurse, determinând înghețarea sistemului sau creând vulnerabilități ale sistemului. În mod similar, tehnicienii ar putea cauza o problemă cu un sistem, prezentându-i fără să vrea o problemă pe care nu o poate rezolva. Este posibil ca aceștia să fie nevoiți să încheie un program sau o operație, ceea ce ar putea duce la pierderea datelor.