beslutbarhet

Beslutsbarhet är ett begrepp inom logik och datorvetenskap som beskriver om ett problem eller en formell teori kan lösas av en algoritm. Ett beslutproblem är beslutsbart om det finns en beräkningsmodell (till exempel en Turingmaskin) som för varje giltig indata avslutas efter ett ändligt antal steg och ger ett korrekt ja‑ eller nej­svar. Om ingen sådan algoritm finns uppnås inte beslutbarhet.

En närbesläktad egenskap är semi-beslutsbarhet (rekursivt uppräknelighet): det finns en algoritm som avslutar och accepterar endast ja‑instanser, medan den kan gå i oändlighet på nej‑instanser. Olika problem kan därför vara semi‑beslutsbara utan att vara helt beslutsbara.

Exempel och gränser. Beslutsbarheten för propositionell logik är etablerad och kan avgöras, till exempel med sanningsmetoder eller tabeller. Första ordningens logik är inte beslutbar i allmänhet (Churchs teorem). Inom talteori är Presburgeraritmetik (addition) beslutbar, medan Peanoaritmetik (addition och multiplikation) inte är beslutbar. Haltsproblemet är odömt – det finns ingen algoritm som avgör, för varje maskin och varje indata, om maskinen haltar. Hilberts tionde problem visade att diophantinska ekvationer kan vara oavgörbara, vilket bekräftar att vissa frågor om heltal saknar algoritmisk lösning. Reala slutna fält är däremot beslutbara via Tarskis beslutmetod.

Beslutsbarhet är ett centralt begrepp inom computability och logik eftersom det klargör vilka frågor som kan lösas automatiskt. Sambandet mellan beslutbarhet och beräkningskomplexitet innebär dessutom att även beslutbara problem kan vara praktiskt svåra att lösa.