beregningslogikk

Beregningslogikk er et fagfelt innen logikk og informatikk som studerer formelle språk, systemer og metoder for å modellere og analysere beregning samt beslutningstakning i mekaniske eller algoritmiske sammenhenger. Faget kombinerer logikkens presise språk med semantiske beskrivelser av hvordan beregninger går fram, og søker å avklare hva som kan fastslås eller bevises innenfor et gitt formelt system.

De viktigste logikktypene inkluderer proposisjonell logikk og førsteordens logikk; disse brukes til å beskrive tilstander, regler og bevis. Beregningslogikk omfatter også formelle modeller som Turingmaskiner, lambda-kalkulus og ulike typer automata-modeller. Formelle systemer blir ofte vurdert ut fra begreper som konsistens, fullstendighet og lydighet, og de analyseres ved hjelp av aksiomatisk bevisføring og semantiske tolkninger.

Et sentralt tema er beregnbarhet og kompleksitet: hva som er beregnbart av en maskin, og hvor vanskelig det er å løse problemer. Church-tese knytter sammen beregnbare funksjoner og formelle maskiner eller språk. Haltingproblemet og andre uavklarte grenser viser begrensninger i hva som kan avgjøres. Teorien om beregningslogikk undersøker også beslutbarhet, modelljekk og bevisførsel i ulike systemer.

Anvendelser inkluderer formell verifikasjon av programvare og maskinvare, kravspesifikasjon og semantisk analyse, samt logikkbasert programmering og kunstig intelligens. Innen akademia gir beregningslogikk et teoretisk rammeverk for forståelse av beregningsprosesser og logiske metoder, og den har tverrfaglige forbindelser til informatikk, matematikk og elektronikk.