Detaljerede instruktioner, der definerer en beregningsproces (som så siges at være algoritmisk), som begynder med et vilkårligt input (ud af et vist antal input, som er mulige for den givne algoritme) og med instruktioner, der har til formål at opnå et resultat (eller output), som er fuldt ud bestemt af input. F.eks. er de regler, der undervises i folkeskolen for kolonnevis addition, subtraktion, multiplikation og division, algoritmer; i disse algoritmer er de mulige resultater ikke-negative hele tal skrevet i decimalsystemet, mens de mulige input er ordnede par af sådanne tal. Det antages generelt ikke, at resultatet nødvendigvis opnås: processen med at anvende en algoritme på et muligt input (dvs. en algoritmisk proces, der starter med dette input) kan også afsluttes, uden at der opnås et resultat (i så fald har man et resultatløst stop), eller den kan slet ikke afsluttes. Hvis processen afsluttes (ikke afsluttes), siger man, at input er egnet (er ikke egnet) for den pågældende algoritme.
Et vigtigt resultat på dette område er den ubeslutsomhed, der er forbundet med det såkaldte stopproblem. Det er muligt at konstruere en algoritme $ \alpha $ således, at der ikke findes nogen algoritme til at afgøre, om et vilkårligt input, som er muligt for $ \alpha $, også er egnet for $ \alpha $ eller ej. Især kan man finde en sådan algoritme $ \alpha $, for hvilken mængden af dens mulige input er mængden af naturlige tal.
Begrebet algoritme er et af de centrale begreber i moderne matematik, især inden for området beregninger. Et eksempel er givet nedenfor. At finde den numeriske løsning af ligninger af en given type svarer til at konstruere en algoritme, der omdanner en vilkårlig ligning af denne type og et vilkårligt positivt rationelt tal $ \epsilon $til et tal (eller en mængde tal), der adskiller sig fra denne lignings rod(er) med mindre end $ \epsilon $. Udtrykket “beregningsproces”, som anvendes i forbindelse med en algoritme, skal dog ikke forstås som værende udelukkende numeriske beregninger: selv i elementær algebra anvendes beregninger med bogstaver. Standardberegninger i aritmetiske beregninger omfatter nogle symboler, som ikke er tal (parenteser, lighedstegn, symboler for aritmetiske operatorer). Det er derfor hensigtsmæssigt at overveje algoritmer, der involverer vilkårlige symboler og objekter, der er sammensat af symboler. Det enkleste eksempel på et sådant objekt er en lineær sekvens af symboler, der udgør et ord. Det er også muligt at overveje “ikke-lineære” objekter – algebraiske matricer, afledningstræer i et formelt sprog og generelle grafer. Intuitivt set er det mindste krav til algoritmernes input og resultater, at de skal være konstruktive objekter (jf. konstruktivt objekt). Begrebet algoritme er således meget generelt. Man kan tale om en algoritme til oversættelse fra et sprog til et andet, om en algoritme for en flyveleder (der behandler oplysninger om flyenes bevægelser i henhold til faste regler) og andre eksempler på algoritmisk beskrevne kontrolprocesser. Derfor er begrebet algoritme en af de centrale ideer inden for kybernetik og datalogi.
Eksempel på en algoritme.
Lad de mulige input og de mulige resultater være alle mulige ord over alfabetet $ \{ a, b \} $. Overgangen fra et ord $ X $til et ord $ Y $er “tilladt” i følgende to tilfælde (hvor $ P $betegner et vilkårligt ord): 1) $ X $er af formen $ aP $, og $ Y $er af formen $ Pb $; eller 2) $ X $er af formen $ baP $, mens $ Y $er af formen $ Paba $. Instrukserne er formuleret som følger: “Udpeg et ord som input, udfør de tilladte overgange, indtil et ord af formen aaP er opnået; stop derefter og lad ordet P være resultatet” . Disse instruktioner udgør en algoritme, som vil blive betegnet $ \mathfrak A $. Tag ordet $ babaa $ som input. Efter én overgang får man $ baaaba $; efter den anden får man $ aabaabaaba $. Her stopper algoritmen med $ baaba $ som resultat. Overvej et andet input $ baaba $. Man får i rækkefølge $ abaaba, baababab, baababa, abababa, bababab, bababab, babababa , . . . Det kan påvises, at denne proces aldrig vil ende (dvs. at ingen af de genererede ord nogensinde vil begynde med $ aa $). Tag nu $ abaab $ som input. Man får $ baabb, abbaba, bbababab $; ingen yderligere tilladte overgange er mulige, og samtidig er afslutningsbetingelsen ikke opfyldt. Man har et resultatløst stop. Således er input $ babaa $ velegnet til $ \mathfrak A $, og input $ baaba $og $ abaab $ er det ikke.
Algoritmers betydning.
I videnskaben støder man på algoritmer overalt: En “generel” løsning på et problem kræver en algoritme. Menneskets evne til at addere tal er et eksempel herpå. Ikke i den forstand, at han før eller siden kan finde summen af to vilkårlige tal, men snarere i den forstand, at han besidder en metode til en entydig addition af to vilkårlige tal, der er givet i skriftlig form, dvs. en additionsalgoritme som f.eks. den velkendte kolonnevise additionsmetode. “Generelt” løses et problem formaliseres som løsning af et algoritmisk problem. Et algoritmisk problem består af separate probleminstanser, og der skal findes en enkelt algoritme til løsning af dem alle. Hvis der ikke findes en sådan algoritme, siger man, at det algoritmiske problem er uløseligt. Således er problemet med numerisk løsning af ligninger af en given type og problemet med automatisk oversættelse algoritmiske problemer. Deres probleminstanser er henholdsvis at finde den numeriske løsning af individuelle ligninger af den givne type og at finde oversættelsen af individuelle sætninger. Andre eksempler er verifikation af algebraiske ligninger i algebra og det algoritmiske problem med at genkende, om sætninger kan udledes af givne aksiomer i matematisk logik. (I matematisk logik er begrebet algoritme også vigtigt, da det tjener som grundlag for nøglebegrebet kalkyle, som er en generalisering og en mere præcis form af de intuitive begreber “bevis” og “demonstration” .) Fastlæggelsen af uløseligheden af et givet algoritmisk problem (f.eks. problemet med at fastslå sandheden eller påviseligheden af sætninger i et eller andet logisk-matematisk sprog) er vigtig, fordi den viser, at specifikke problemtilfælde af dette problem i princippet kun kan løses ved hjælp af metoder, der er specifikke for hvert enkelt problemtilfælde.
Den videnskabelige betydning af begrebet algoritme har været anerkendt i lang tid. Siden de tidligste tider har man søgt efter konstruktive metoder til at løse matematiske problemer. Sådanne bestræbelser har normalt draget fordel af den nye tilgængelighed af passende symbolske notationer. Denne proces har ydet et væsentligt bidrag til den videnskabelige viden, især efter at det var blevet klart, at nogle problemer i sagens natur er uløselige (kvadrering af cirklen osv.). Efter at det var blevet erkendt, at visse problemer ikke kan løses ved direkte beregninger, blev det teoretiske begreb mængde født i det 19. århundrede. Først efter en periode med en hurtig udvikling af dette begreb (som ikke omfattede problemer med konstruktive metoder i deres moderne betydning), blev det i midten af det 20. århundrede muligt at vende tilbage til konstruktive problemer, men det skete på et andet niveau, beriget af begrebet algoritme, som i mellemtiden havde udkrystalliseret sig. Dette begreb danner grundlaget for den konstruktive tendens i matematikken.
Ordet “algoritme” kommer af ordet “algoritmi” , sidstnævnte er den latinske translitteration af navnet på den arabiske matematiker Al-Khwarizmi fra det 9. århundrede. En “algoritme” var i middelalderens Europa “det decimal-positionelle system og kunsten at regne med det” , da det er gennem den latinske oversættelse (12. århundrede) af Al-Khwarizmis afhandling, at det positionelle system blev indført i Europa.
Strukturen af en algoritmisk proces.
En algoritmisk proces er en proces af fortløbende omdannelse af konstruktive objekter ved hjælp af diskrete “trin” , idet hvert trin består i udskiftning af et konstruktivt objekt med et andet. Når man således anvender algoritmen $ \mathfrak A $ på ordet $ baaba $, følger der efter hinanden ordene $ baaba, abaaba, baababab $ osv. Hvis man f.eks. anvender algoritmen for kolonnevis subtraktion på talparret <307, 49 >, opnår man successivt følgende konstruktive objekter:
$$ \begin{array}{rrrr}307 &3 \dot{0} 7 &\dot{3} \dot{0} 7 &\dot{3} \dot{0} 7 \\\\\underline{- 49 } &\underline{- 49 } &\underline{- 49 } &\underline{- 49 } \\{} & 8 &58 &58 &258 \\end{array}$$$$
Det skal bemærkes, at i en serie af på hinanden følgende konstruktive objekter er hvert på hinanden følgende konstruktivt objekt fuldt bestemt (inden for rammerne af den givne algoritme) af det konstruktive objekt, der går umiddelbart forud for det. I den mere stringente tilgang antages det også, at overgangen fra et hvilket som helst konstruktivt objekt til det umiddelbart efterfølgende er tilstrækkeligt “elementær” – i den forstand, at den et-trins transformation af det foregående til det umiddelbart efterfølgende objekt er lokal (det er ikke hele det konstruktive objekt, der transformeres, men kun dets algoritmebegrænsede del; desuden er denne transformation i sig selv ikke bestemt af det fuldstændige foregående objekt, men kun af en begrænset del af det).
I overensstemmelse hermed har man ikke kun et sæt af mulige input og et sæt af mulige resultater, men også et sæt af mulige mellemresultater, der repræsenterer det arbejdsmedie, hvori den algoritmiske proces udvikler sig. Med hensyn til $ \mathfrak A $ er alle disse tre sæt sammenfaldende, men dette gælder ikke for algoritmen for kolonnevis subtraktion – de mulige input er talpar, de mulige resultater er tal (alle i decimalsystemet), mens de mulige mellemresultater er “tre-etagers” poster af typen
$$ \$begin{array}{r} p \\\\\\underline{- q } \\\ r \\\end{array}}$$$
hvor $ q $er den skriftlige registrering af et tal i decimalsystemet, $ r $er en lignende registrering eller det tomme ord, mens $ p $er den skriftlige registrering af et tal i decimalsystemet med prikker over nogle af cifrene. Som regel kan der skelnes mellem flere (ikke uafhængige) parametre, som er karakteristiske for en algoritme: 1) mængden af mulige input, 2) mængden af mulige resultater, 3) mængden af mulige mellemresultater, 4) startreglen, 5) reglen for direkte overgang, 6) reglen for afslutning og 7) reglen for genfinding af resultatet.
Formalisering af begrebet algoritme.
Begrebet algoritme i sin generelle form er et grundlæggende matematisk begreb, som ikke kan defineres ved hjælp af enklere begreber. Strengt taget begrænser formaliseringer af begrebet algoritme det faktisk noget. I hver sådan formalisering gives en nøjagtig definition af en eller anden klasse, inden for hvilken hver af parametrene kan variere. De forskellige formaliseringer adskiller sig fra hinanden ved valget af sådanne klasser. Da parametrene utvetydigt definerer en algoritme, bestemmer valget af parameterdomæner en klasse af algoritmer. Et sådant valg kan imidlertid kun hævde at være en formalisering af det intuitive algoritmebegreb, hvis man kan være sikker på, at der for enhver “intuitiv” algoritme findes en tilsvarende algoritme i den klasse af algoritmer, der er defineret ved det pågældende valg. Dette krav formuleres for hver formalisering som en fundamental hypotese, der efter den nuværende videnstand ikke kan påvises matematisk.
De første formaliseringer af denne type skyldes E.L. Post
og A.M. Turing , , hvis konstruktioner i mange henseender foregreb de ideer, som moderne computere bygger på. Der findes også versioner formuleret af A.A. Markov ,
(jf. Normal algoritme) og af A.N. Kolmogorov , , som baserede fremgangsmåden på konstruktive topologiske komplekser af en bestemt type, hvilket gør det muligt at udtrykke mere præcist egenskaben “at være lokal” for en transformation. I hver af disse formaliseringer er den grundlæggende hypotese i tilfredsstillende overensstemmelse med praksis. Et andet argument til fordel for denne hypotese er, at alle de formelle versioner (af effektiv beregnelighed), der er blevet foreslået, som det kan påvises, er ækvivalente.
Som eksempel kan man betragte den formalisering, der blev foreslået af Turing. I sin oprindelige form var dette en beskrivelse af en teoretisk computer bestående af 1) et uendeligt bånd, opdelt i på hinanden følgende celler, hvor hver celle kan indeholde et symbol fra maskinens “båndalfabet”; og 2) en “endelig kontrol”, som på hvert tidspunkt befinder sig i en eller anden “tilstand” (ud fra en given endelig liste af tilstande). Den finitte kontrol kan bevæge sig langs båndet, en celle ad gangen, og ændre indholdet af de celler, den passerer. Et program, der overvåger den finitte kontrols bevægelse, udgør algoritmen for de beregninger, der udføres på en sådan maskine (en “Turing-algoritme” ). For en mere præcis og detaljeret beskrivelse se Turing-maskine. Her gives en moderniseret fremstilling af Turings konstruktion. For at definere en Turing-algoritme angiver man a) parvis adskilte alfabeter $ B, D, C $, med et adskilt bogstav $ \lambda $i $ D $og adskilte bogstaver $ \alpha $og $ \omega $i $ C $; og b) et sæt af par af formen $ \langle p \xi , \eta Tq \rangle $ hvor $ p, q \in C $, $ \xi , \eta \in B \cup D $, mens $ T $ er et af de tre symboler $ -, 0, + $; i dette sæt (som kaldes et program) er der ikke to par med samme første koordinat. De mulige indgange og mulige udgange er ord over $ B $, mens de mulige mellemresultater er ord over $ B \cup D \cup C $, som ikke indeholder mere end ét bogstav af $ C $. Startreglen er, at det indledende ord $ P $omdannes til ordet $ \lambda \alpha P \lambda $. Afslutningsreglen er, at et mellemresultat, som indeholder $ \omega $, er endeligt. Reglen for genfinding af output er, at output er den sekvens af bogstaver i det endelige mellemresultat, der følger efter $ \omega $ og går forud for det første bogstav, der ikke tilhører $ B $. Transformationsreglen, der omdanner $ A $ til $ A ^ \prime $, er som følger. Bogstavet $ \lambda $ skrives til venstre og til højre for $ A $; i det således dannede ord erstattes den del af formen $ \epsilon p \xi $, hvor $ p \in C $, $ \epsilon \xi \in B \cup D $, af et ord $ Q $ i overensstemmelse med reglen: et par med den første term $ p \xi $ søges i programmet; lad den anden term i dette par være $ \eta Tq $; hvis $ T $ er $ – $, er $ Q = q \epsilon \eta $; hvis $ T = 0 $, er $ Q = \epsilon q \eta $; hvis $ T $ er $ + $, er $ Q = \epsilon \eta q $. Det ord, der fremkommer ved denne ombytning, er $ A ^ \prime $. For referencer, se , , , , , , , ,
af Algoritmer, teori om.
Den grundlæggende hypotese, der er nævnt ovenfor, kaldes normalt Church-Turing-tesen eller Turing-hypotesen. Denne tese fastslår, at det, der kan beregnes effektivt i henhold til ens intuition om, hvad der udgør en effektiv proces, også kan beregnes af en Turing-maskine, dvs. et formelt defineret begreb om en algoritme. I kraft af sin natur, der består i at identificere et intuitivt uformelt begreb med en formel præcis definition, kan Church-Turing-tesen ikke bevises formelt.
Mange formaliseringer har vist sig at være ækvivalente, og ingen formalisering har vist sig at være strengt set mere kraftfuld. Ud over de formaliseringer, der er nævnt ovenfor, er følgende referencer de mest standardiserede i Vesten: Church’s formalisering af tal og beregnelige funktioner ved hjælp af lambda-termer, Kleene’s generelle rekursive skemaer og registermaskine-modellen foreslået af J.C. Shepherdson og H.E. Sturgis, som blev udvidet til en mere realistisk computermodel af S.A. Cook og R.A. Reckhow. Markovs og Kolmogorovs versioner er mindre velkendte. For fuldstændighedens skyld er de oprindelige referencer til Turing og Post også angivet.
| A.M. Turing, “On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, “Corrections to “On computable numbers, with an application to the Entscheidungsproblem” ” Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, “An unsolvable problem of elementary number theory” Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, “General recursive functions of natural numbers” Math. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, “Formal reductions of the general combinatorial decision problem” Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, “Computability of recursive functions” J. Assoc. Comp. Mach. , 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, “Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) pp. 354-375 |