Beregnelighed er et område inden for datalogi og filosofi, hvor man studerer, hvilke problemer der principielt kan løses af en automatisk udført beregningsprocedure, fx af en algoritme udført af en computer.

Et vigtigt resultat er, at der findes problemer, som ikke kan løses, og funktioner, for hvilke der ikke kan angives en algoritme til beregning af uddata fra inddata. Problemer af denne type kaldes uafgørlige og funktionerne ikke-beregnelige.

Normalt tages der ikke hensyn til resurseforbruget under beregningerne, hverken med hensyn til tid eller plads. Den gren inden for beregnelighed, som beskæftiger sig tids- og pladsforbrug, kaldes kompleksitet af beregninger.

Modeller for beregning

For at kunne argumentere præcist om en beregning må man arbejde med en formel model af, hvad en beregningsprocedure er, og en præcis beskrivelse af, hvad der beregnes. Som udgangspunkt ser man oftest på beregning af den type funktioner, der til hvert positivt heltal knytter enten et andet positivt heltal (funktionsværdien) eller værdien "udefineret". Man søger så at give en præcis beskrivelse af den klasse af funktioner, hvis funktionsværdier kan beregnes.

Beregnelighedsproblemet blev studeret længe før konstruktionen af de første computere. Matematikere og logikere, blandt andre Alan M. Turing, Alonzo Church og Stephen C. Kleene (1909-1994), har foreslået forskellige metoder til at afgrænse klassen af beregnelige funktioner. Metoderne er ofte væsensforskellige i deres tilgang. Den enkelte metode kan være baseret enten på en matematisk model af, hvordan en beregning foregår i en computer, eller på opbygningen af mere komplicerede funktioner ud fra enkle grundlæggende funktioner og enkle sammensætningsoperationer.

Den simpleste model for en maskinel beregning tager udgangspunkt i en Turingmaskine, som er en model af en computer med et program. En funktion, der aldrig returnerer værdien "udefineret", kaldes Turingberegnelig, hvis der findes en Turingmaskine, som med et tal som inddata efter endelig tid giver den tilsvarende funktionsværdi som uddata. De beregnelige funktioner karakteriseres altså her via beregningsmodellen.

Et eksempel på konstruktiv karakterisering af beregnelige funktioner er klassen af rekursive funktioner. Disse opbygges fra få, simple funktioner ved hjælp af funktionssammensætning, primitiv rekursion og såkaldt ubegrænset minimalisering. Alle funktioner, der kan opbygges på denne måde, kaldes μ-rekursive funktioner. Forbavsende nok er denne klasse præcis den samme som de Turing-beregnelige funktioner.

Alle forsøgte klassifikationsmetoder giver som resultat samme klasse af beregnelige funktioner, hvilket er udtrykt i Church-Turings tese. Hvordan beregningsmodellen formaliseres er altså ikke afgørende for, hvilke funktioner der kan beregnes. Tesen kan ikke bevises matematisk, men ingen forsøgte klassifikationsmetoder har hidtil kunnet rejse tvivl om tesens gyldighed.

I relation til computere og programmer betyder Church-Turings tese, at på trods af store forskelle i maskinarkitektur og programmeringssprog er klassen af problemer, der kan løses algoritmisk, den samme for alle computere. Forbrug af tid og plads kan dog variere meget.

Ikke-beregnelige funktioner

Beviset for eksistensen af funktioner, der ikke kan beregnes af en computer, er et godt eksempel på betydningen af en præcis beskrivelse af beregningsmodellen. At se på eksisterende maskiner og programmeringssprog er ikke nok, idet fremtiden altid vil kunne bringe nye idéer. Men under forudsætning af, at Church-Turings tese er korrekt, kan man nøjes med at se på den meget simple Turingmaskine-model. Ved at vælge den simplest mulige type Turingmaskine som udgangspunkt opnås, at alle maskinbeskrivelser bliver sammenlignelige. Derfor kan man nummerere alle Turingmaskiner, og selvom alle Turingmaskiner ikke beregner funktioner, giver rækkefølgen også anledning til en nummerering af de maskiner, der beregner funktioner. Derfor kan også alle Turing-beregnelige funktioner nummereres.

For at overbevise sig om, at der er funktioner, der ikke er Turing-beregnelige, er det derfor nok at indse, at det ikke er muligt at nummerere alle funktioner, der til hvert positivt heltal knytter et andet positivt heltal som funktionsværdi. Da man kan nummerere de Turing-beregnelige funktioner, kan denne klasse så ikke rumme alle funktionerne.

Uanset hvilken nummerering af alle funktioner man vælger, er det muligt at definere en funktion, der ikke kan være med i nummereringen. For en konkret nummerering af funktioner ser man på den funktion, der for tallet n som værdi har 1 plus værdien af den n'te funktion for tallet n. Denne funktion kan ikke optræde i nummereringen, for hvis den havde nummer p, skulle dens værdi for tallet p ifølge forskriften være lig den samme værdi plus 1, og dette kan ikke lade sig gøre. Altså kan ingen konkret nummerering af alle funktioner findes, og dermed må der være flere funktioner end dem, der er beregnelige.

Ovenstående er et såkaldt diagonaliseringsbevis, som også er kernen i Cantors bevis for, at mængden af alle mængder af heltal ikke kan opremses. Kernen er, at de Turing-beregnelige funktioner kan nummereres, og det kan man kun vise, når den anvendte beregningsmodel er tilstrækkelig simpel til, at hver mulig beregning kan få sit eget nummer.

Standsningsproblemet

Diagonaliseringsbeviset udtrykker, at der findes funktioner, der ikke kan beregnes, men ikke noget om hvilke funktioner, dette er. Et konkret problem, der ikke kan afgøres algoritmisk er standsningsproblemet. Standsningsproblemet er at afgøre om et givet program vil standse efter endelig tid. Man kan prøve at køre programmet, og hvis det standser, har man et svar. Men hvis det efter mange timers kørsel ikke endnu er standset, ved man ikke, om det vil standse efter endnu nogle timer, eller om det aldrig vil standse. Alonzo Church beviste i 1936, at standsningsproblemet for lambdakalkylen er uafgørligt (og dermed ikke beregnelig), og Alan Turing beviste næsten samtidigt, at standsningsproblemet er uafgørligt for Turingmaskiner.

Læs mere i Den Store Danske

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig