Besluttbart

Besluttbart er et begrep innen logikk og informatikk som beskriver om et problem kan avgjøres av en algoritme. Et beslutningsproblem består av en mengde innganger, og et språk er besluttbart hvis det finnes en algoritme som for hver inngang terminerer og avgjør om inngangen tilhører språket (ja hvis den gjør, nei ellers). Dette er ekvivalenter med at språket har en total beregningsfunksjon, eller at en Turing-maskin kan bestemme medlemskap for alle innganger og alltid avslutte.

I praksis betyr besluttbarhet at det finnes en mekanisk prosess som kan gi riktig svar for alle tilfeller innenfor problemet. Ikke-besluttbare problemer mangler slik garanti; det finnes ikke noen algoritme som alltid gir riktig svar i alle tilfeller, ofte demonstrert via redusering fra kjente ubesluttbare problemer som halting-problemet.

Eksempler på besluttbare språk og problemer inkluderer alle regulære språk og kontekstfrie språk, samt aritmetikke teorier som Presburger-aritmetik med bare addisjon. Halvparten av kjente teoretiske problemer er ubesluttbare, som halting-problemet for Turing-maskiner og beslutningsproblemene i full førsteordens logikk over naturlige tall. Besluttbarhet er derfor et grunnleggende skillepunkt i teoretisk datalogi mellom hva som kan løses av algoritmer og hva som er uunngåelig uenighetsbart eller umulig å avgjøre.

Relaterte begreper inkluderer decidability (det engelske uttrykket), beslutningsproblemer, rekursivitet og semi-decidable/recursively enumerable problemer. Besluttbarhet brukes også i språk- og programanalyse for å vurdere hvilke spørsmål som kan automatiseres.