Eldönthetetlen

Eldönthetetlen (undecidable) egy döntési probléma vagy matematikai állítás, amelyre nem létezik általános algoritmus, amely minden lehetséges bemenetre helyes igen/nem választ adna. Más szóval: nincs olyan program, amely garantáltan leállna és minden bemenetre helyesen eldöntené a kérdést.

Definíció és kontextus szerint egy probléma decidable, ha létezik olyan Turing-gép vagy más végrehajtható algoritmus, amely mindegyik bemenetre megállva pontosan eldönti, hogy a bemenet a kérdés alá tartozik-e vagy sem. Ha ilyen gép nem létezik, a probléma eldönthetetlen. A fogalmat a számítástudományban és a logikában használják.

Részben eldönthető fogalom alatt olyan problémákat értenek, amelyekre van olyan gép, amely a pozitív példákat (igen válaszokat) leállva felismeri, de a negatív példákat (nem válaszokat) általában nem áll le. Ezeket gyakran rekurzívan felsorolható (recursively enumerable) nyelvek írják le.

Példák: a megállási probléma (halting problem), amely megmondja, hogy egy adott program leáll-e egy adott bemeneten, bizonyult eldönthetetlennek. Az elsőrendű logika döntési problémája és a hozzátartozó Entscheidungsproblem szintén elméletben eldönthetetlennek bizonyultak a Church–Turing tételek és Gödel-féle eredmények alapján.

Jelentőség: az eldönthetetlenség korlátozza, hogy minden matematikai vagy algoritmikus kérdésre automatizáltan válaszolhassunk, és kiemelten fontos a computabilitás és a bizonyítási határok megértésében.