beslutningsproblemet

Beslutningsproblemet, eller beslutningsproblemet (Engelska: the decision problem), är frågan om det finns en algoritm som, givet varje påstående inom ett formellt system, kan avgöra dess sanningsvärde eller giltighet. I Hilberts program under tidigt 1900-tal var målet att hitta mekaniska metoder för att bevisa eller avvisa varje matematisk sats. Problemet i sin mest omfattande form gäller först-orderlogik, där statementens giltighet i alla möjliga modeller skulle kunna avgöras av en generell procedur.

Historiskt visade två parallella resultat 1936 att beslutningsproblemet inte kan lösas i allmänhet. Alan Turing visade att det inte finns något allmänt stoppbart sätt att avgöra om en beräkningshandling slutar. Samma år visade Alonzo Church att det inte finns något algoritmiskt sätt att avgöra giltigheten av varje sats i första ordningen. Dessa resultat innebar att det inte finns någon universell datorprocedur som kan avgöra sanningsvärdet för alla först‑ordningssatser. Gödel:s komp­lethetssats sammanförde syntaktisk bevisbarhet med semantisk giltighet och stärkte slutsatsen: beslutbarhet förfullständig första ordningen logik är oåterkalleligen omöjlig.

Undantag finns i vissa avgränsade fragment där beslutbarhet återfås, till exempel propositional logik och vissa begränsade första ordningenlogiska språk med särskilda begränsningar. Betydelsen av beslutningsproblemet ligger i att fastslå gränserna för vad som kan automatiseras inom logik och matematisk rättegång, och den har påverkat studier inom beräkningsteori och artificiell intelligens.

Se även: Entscheidungsproblem, Turing och halting-problemet, Gödel's ofullständighetssats, beräknelighetsteori.