oavgörbart

Oavgörbart är ett adjektiv som används inom logik, matematisk logik och datavetenskap för att beskriva ett beslutproblem som inte kan avgöras av någon allmän algoritm. En uppgift sägs vara oavgörbar om det inte finns någon algoritm som för varje giltig indata kan avgöra svaret ja eller nej i finit tid. Begreppet motsvarar det engelska undecidable.

Inom teori om beräkningar kopplas oavgörbarhet ofta till begreppen beslutbarhet och beräkning. Ett problem är decidabelt om det finns en algoritm som för alla indata avslutar och ger korrekt ja/nej-svar; om inget sådant program finns är problemet oavgörbart. Många oavgörbara problem är dessutom semiavgörbara (rekursivt uppräknbara) i den meningen att det finns en maskin som i alla giltiga fall avslutar med ja, men som kan gå på ogiltiga fall i oändlig tid. Ett klassiskt exempel är halting-problemet, som är oavgörbart men semiavgörbart. Andra oavgörbara problem förekommer inom första ordningens logik (beslutsproblemen) och i olika konstruktioner inom mängdteori och beräkningsteori.

Historiskt sammanhang: begreppet oavgörbarhet uppstod i 1930-talets forskning av Gödel, Church och Turing och visade att det inte finns någon universell algoritm som löser alla beslutsproblem, vilket bland annat innebär att Hilberts Entscheidungsproblem inte har en allmän lösning.

Se även: decidabelt, halting-problemet, Entscheidungsproblem, rekursiv uppräknbarhet.