Neodlučiv problem je pitanje koje se ne može riješiti korištenjem jednog algoritma. Ovo je predmet interesa matematike i računalnog programiranja, gdje neodlučivi problem ima značajne implikacije. Istraživači koji se zanimaju za Turingove strojeve, na primjer, bavili su se problemom zaustavljanja, promatrajući kada se računalni programi zaustavljaju, u odnosu na beskonačno pokretanje. Kao i kod drugih izazova u matematici, značajna istraživanja okružuju načine za zaobilaženje neodlučivih problema, uz identificiranje novih problema za više evaluacije i proučavanja.
Ovaj predmet uključuje probleme odlučivanja, pitanja s da ili ne odgovorima. U matematici se oni često prikazuju u obliku formula. Jednostavan primjer mogao bi biti “Je li za sve realne brojeve X jednako djeljiv s Y?” Ovo je problem koji se može riješiti, jer ako se računalu daju bilo koje vrijednosti za X ili Y, ono može koristiti algoritam da odgovori na pitanje. Složeniji problemi možda neće biti rješivi s jednim algoritmom za sve moguće vrijednosti.
U tim slučajevima algoritam može biti točan za neke odgovore, ali ne može odgovoriti za druge vrijednosti. S obzirom na neke vrijednosti, algoritam bi se mogao kretati kroz niz koraka kako bi utvrdio je li odgovor na pitanje bio da ili ne. U drugim slučajevima to ne bi bilo moguće učiniti jer bi mu nedostajale potrebne informacije. Ovo je poznat problem s nekim problemima koji uključuju matrice, složenu analizu i određene druge funkcije.
Identifikacija neodlučivog problema može se dogoditi u kontekstu istraživanja matematike i informatike. Nakon što se vjeruje da je problem neodlučiv, istraživači mogu primijeniti razne taktike kako bi opovrgli ovu teoriju. To može uključivati razvoj algoritama koji rade za neke vrijednosti, raspravu o specifičnostima problema koji onemogućuju učinkovito liječenje algoritmom za sve vrijednosti i povezane aktivnosti. Publikacije iz matematike i informatike mogu raspravljati o najnovijem napretku u ovom području s primjerima algoritama koje su istraživači koristili za istraživanje granica neodlučivog problema.
Daleko od toga da je tema od samo teoretskog interesa, neodlučivi problem može imati važne implikacije na stvarni svijet. Na primjer, neki računalni virusi predstavljaju sustave s neodlučivim problemima. Pokušaj sustava da riješi problem može pojesti resurse, uzrokujući zamrzavanje sustava ili stvaranje ranjivosti sustava. Slično, tehničari mogu uzrokovati problem sa sustavom tako što mu nesvjesno predstavljaju problem koji ne može riješiti. Možda će morati prekinuti program ili operaciju, što bi moglo rezultirati gubitkom podataka.