Nerešljiv problem je vprašanje, ki ga ni mogoče rešiti z uporabo enega algoritma. To je predmet zanimanja v matematiki in računalniškem programiranju, kjer ima nerešljiv problem pomembne posledice. Raziskovalci, ki jih zanimajo Turingovi stroji, so se na primer lotili problema ustavljanja, pri čemer so gledali, kdaj se računalniški programi ustavijo, v primerjavi z neskončnim delovanjem. Kot pri drugih izzivih v matematiki, številne raziskave obkrožajo načine, kako premagati nerešljive probleme, poleg prepoznavanja novih problemov za večjo oceno in študij.
Ta tema vključuje težave pri odločanju, vprašanja z da ali ne odgovori. V matematiki so te pogosto predstavljene v obliki formul. Preprost primer bi lahko bil “Ali je za vsa realna števila X enakomerno deljiv z Y?” To je težava, ki jo je mogoče rešiti, ker če računalniku dajo kakršne koli vrednosti za X ali Y, lahko uporabi algoritem za odgovor na vprašanje. Bolj zapletene težave morda ne bodo rešljive z enim algoritmom za vse možne vrednosti.
V teh primerih je lahko algoritem za nekatere odgovore natančen, za druge vrednosti pa ne more odgovoriti. Glede na nekatere vrednosti bi se algoritem lahko premikal skozi vrsto korakov, da bi ugotovil, ali je bil odgovor na vprašanje da ali ne. V drugih primerih tega ne bi mogel storiti, ker ne bi imel potrebnih informacij. To je znana težava z nekaterimi težavami, ki vključujejo matrike, kompleksno analizo in nekatere druge funkcije.
Identifikacija nerešljivega problema se lahko pojavi v okviru raziskav matematike in računalništva. Ko se domneva, da je problem nerešljiv, lahko raziskovalci uporabijo različne taktike, da ovržejo to teorijo. To lahko vključuje razvoj algoritmov, ki delujejo za nekatere vrednosti, razpravo o posebnostih problema, ki onemogoča učinkovito zdravljenje z algoritmom za vse vrednosti, in s tem povezane dejavnosti. Matematične in računalniške publikacije lahko razpravljajo o najnovejšem napredku na tem področju s primeri algoritmov, ki so jih raziskovalci uporabili za raziskovanje meja nerešljivega problema.
Daleč od tega, da bi bil nerešljiv problem samo teoretična tema, ima lahko pomembne posledice za resnični svet. Nekateri računalniški virusi na primer predstavljajo sisteme z nerešljivimi težavami. Poskus sistema, da bi rešil težavo, lahko požre vire, kar povzroči zamrznitev sistema ali ustvarja ranljivosti sistema. Podobno lahko tehniki povzročijo težavo s sistemom tako, da mu nehote predstavijo težavo, ki je ne more rešiti. Morda bodo morali prekiniti program ali operacijo, kar bi lahko povzročilo izgubo podatkov.