beregnelighed

Verificeret
Artiklens indhold er godkendt af redaktionen.

beregnelighed, emneområde inden for datalogi og filosofi, hvor man studerer, hvilke problemer der principielt kan løses af en automatisk udført beregningsprocedure, fx en algoritme udført af en computer. Et vigtigt resultat er, at der findes problemer, der 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 af emneområdet beregnelighed, hvor tids- og pladsforbrug studeres, kaldes kompleksitet af beregninger.

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, bl.a. A.M. Turing, A. Church og S. Kleene, 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å opbygning 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, der er en model af en computer med et program. En funktion, der aldrig returnerer værdien "udefineret", kaldes Turingberegnelig, hvis der findes en Turingmaskine, der med et tal som inddata giver den tilsvarende funktionsværdi som uddata. De beregnelige funktioner karakteriseres altså her via beregningsmodellen.

Et eksempel på konstruktiv karakterisation 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.

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, 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. 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.

Vind tre bøger i Den Store Danskes quiz.

Gå til quiz.

 

Find bøger

   
   Find Lydbøger
hos Storytel
   Find bøger
bogpriser.dk
   Studiebøger
pensum.dk
   Læs e-bøger
hos Ready

 

Hvad er et tag? Tags er artiklens nøgleord. Artikler med et fælles tag findes ved at klikke på tagget. Når du er logget ind, kan du tilføje tags og dermed skabe sammenhænge.
Nyhedsbrev

Om artiklen

Seneste forfatter
Redaktionen
29/01/2009
Ekspert
palnatoke
Oprindelig forfatter
JClau
29/01/2009

© Gyldendal 2009-2014 - Powered by MindTouch Deki