Uavgjørbarhet

Uavgjørbarhet er en egenskap ved beslutningsproblemer og språk som ikke kan avgjøres av en generell algoritme. Et beslutningsproblem er et spørsmål som kan besvares med ja eller nei for enhver inndata. Hvis det finnes en maskin som alltid avslutter og gir riktig svar, er problemet avgjørbart. Hvis ingen slik maskin finnes, er det uavgjørbart.

I beregnbarhetsteori brukes uavgjørbarhet til å skille mellom problemer som kan løses automatisk og de som ikke kan det. Et klassisk eksempel er Halting-problemet: spørsmålet om et gitt program vil avslutte når det kjøres med en gitt inngang. Det er bevist at det ikke finnes noen algoritme som kan avgjøre halting for alle programmer og innganger. Halting-problemet er imidlertid rekursivt gjenkjennelig: en maskin kan bekrefte tilfeller der programmet stopper, men den kan ikke alltid gi riktig nei-svar for alle andre tilfeller.

Et språk kan være uavgjørbart uten å være helt utenkelig å gjenkjenne. Noen uavgjørbare problemer er rekursivt gjenkjennelige (RE), som Halting-problemet, mens andre ikke er RE. Dette skillelinjen har stor betydning for teori om beregnbarhet og for forståelsen av hva som kan automatiseres.

Metoder for å demonstrere uavgjørbarhet inkluderer nedreduksjon fra et kjent uavgjørbart problem og bruk av teoremer som Rice’ teorem. Uavgjørbarhet har praktiske konsekvenser for ytelseskontekst i programverifikasjon, matematisk logikk og forskningen i hva som generelt kan bestemmes automatisk.