Eldönthetség

Eldönthetőség, vagy decidability, a formális logika és számítástudomány egyik alapfogalma. A fogalom egy döntési probléma vagy egy nyelv megoldhatóságát írja le azzal a követelményel, hogy van-e olyan algoritmus (vagy Turing-gép), amely minden bemenetre determinisztikusan leáll és igen vagy nem választ ad. Ha egy nyelvhez létezik ilyen meghatalmazott eldöntő eljárás, akkor a nyelv eldönthető (rekurzív); ha nincs, akkor eldönthetetlen (undecidable).

A gyakorlatban ezt a nyelvek osztályozásával szokás szemléltetni. Egy adott nyelv L eldönthető, ha a bemenetre adott szóval kapcsolatban az algoritmus végigfut és mindig eldönti, hogy a szó a L-hez tartozik-e vagy sem. Például a reguláris nyelvek eldönthetők, mert létezik determinisztikus vagy nem determinisztikus véges automata, amely megáll és meghatározza a tagságot. A kontextusfüggetlen nyelvek is eldönthetők (a CYK-algoritmus például meghatározza a tagságot). Ezzel szemben általános elsőrendű logika dönthetetlensége híres eredmény: a Church–Turing-tétel értelmében a teljes elsőrendű logikára vonatkozó egyetértés kérdése nem dönthető el általánosan.

Fontos összefüggések között szerepel a rekurzív függvényelmélet, a Turing-gépek és a dönthetőség kapcsolata, valamint a dönthetőség és a bonyolultság különválasztása: egy probléma lehet dönthető, de gyakorlatilag nehezen vagy rendkívül hosszú idő alatt oldható meg. Számos konkrét problémát eldönthetetlennek bizonyítottak (például a-halmazok halt megállási kérdése), míg mások bizonyítottan decidibilisek vagy tisztán decidibilisek bizonyos elméletekben.