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