Beregnbarhet

Beregnbarhet er et grunnleggende begrep i beregnings- og matematikkteori som beskriver hvilke problemer eller funksjoner som kan løses eller beregnes av en algoritme. For en total funksjon f: N -> N betyr beregnbarhet at det finnes en maskin som stanser for alle inndata n og returnerer f(n). For beslutningsproblemer betyr beregnbarhet at det finnes en maskin som alltid avgjør om et gitt inn-data tilhører et språk, og som avslutter i alle fall.

Formaliseringene bruker ofte Turing-maskiner, lambda-kalkulus eller rekursive funksjoner; alle disse modellene anses å fange begrepet beregnbarhet og er antatt ekvivalente når det gjelder effektiv beregning. Church-Turing-tesen sier at hver effektiv beregningsprosedyre kan beskrives av en av disse modellene.

Eksempler: grunnleggende aritmetiske funksjoner som addisjon og multiplikasjon er beregnbare. Ackermann-funksjonen er et kjent eksempel på en total beregnbar funksjon som ikke er primitive rekursiv. Halting-problemet er et klassisk eksempel på et ikke-beregnbart beslutningsproblem, hvilket betyr at ingen generell maskin kan avgjøre for alle programmer og innganger om de stopper.

Betydning og anvendelser: beregnbarhet gir et teoretisk rammeverk for å forstå hva som kan automatiseres og hva som ikke kan, og den danner grunnlag for studier av beregningskompleksitet, formell verifikasjon og teoretisk datastruktur. Feltet bidrar til å kartlegge grensene for algoritmer og maskinell problemløsning.