Detaljerade instruktioner som definierar en beräkningsprocess (som då sägs vara algoritmisk), som börjar med en godtycklig inmatning (av ett visst antal inmatningar som är möjliga för den givna algoritmen), och med instruktioner som syftar till att erhålla ett resultat (eller output) som är helt bestämt av inmatningen. Till exempel är de regler som lärs ut i grundskolan för kolumnvis addition, subtraktion, multiplikation och division algoritmer; i dessa algoritmer är de möjliga resultaten icke-negativa heltal skrivna i decimalsystemet, medan de möjliga inmatningarna är ordnade par av sådana tal. Det förutsätts i allmänhet inte att resultatet nödvändigtvis erhålls: processen att tillämpa en algoritm på en möjlig inmatning (dvs. en algoritmisk process som utgår från denna inmatning) kan också avslutas utan att ett resultat erhålls (i ett sådant fall har man ett resultatlöst stopp) eller kan inte avslutas alls. Om processen avslutas (inte avslutas) säger man att inmatningen är lämplig (är inte lämplig) för algoritmen i fråga.
Ett viktigt resultat på detta område är att det så kallade stoppproblemet är obestridligt. Det är möjligt att konstruera en algoritm $ \alpha $ så att det inte finns någon algoritm för att avgöra om någon godtycklig indata som är möjlig för $ \alpha $ också är lämplig för $ \alpha $ eller ej. I synnerhet kan man hitta en sådan algoritm $ \alpha $ för vilken uppsättningen möjliga indata är uppsättningen naturliga tal.
Begreppet algoritm är ett av de centrala begreppen i den moderna matematiken, särskilt inom området för beräkningar. Ett exempel ges nedan. Att hitta den numeriska lösningen av ekvationer av en given typ är detsamma som att konstruera en algoritm som omvandlar en godtycklig ekvation av denna typ och ett godtyckligt positivt rationellt tal $ \epsilon $ till ett tal (eller en uppsättning tal) som skiljer sig från ekvationens rot(er) med mindre än $ \epsilon $. Termen ”beräkningsprocess”, som används i samband med en algoritm, får dock inte uppfattas som att den endast avser numeriska beräkningar: även i elementär algebra används beräkningar med bokstäver. Standardiserade aritmetiska beräkningar inbegriper vissa symboler som inte är siffror (parenteser, likhetstecken, symboler för aritmetiska operatorer). Det är därför lämpligt att beakta algoritmer som omfattar godtyckliga symboler och objekt som är sammansatta av symboler. Det enklaste exemplet på ett sådant objekt är en linjär sekvens av symboler som bildar ett ord. Det är också möjligt att betrakta ”icke-linjära” objekt – algebraiska matriser, härledningsträd i vissa formella språk och allmänna grafer. Intuitivt sett är det minsta kravet på algoritmers indata och resultat att de måste vara konstruktiva objekt (jfr Konstruktivt objekt). Begreppet algoritm är således mycket allmänt. Man kan tala om en algoritm för översättning från ett språk till ett annat, om en algoritm för en flygledare (som behandlar information om flygplanens rörelser enligt fasta regler) och andra exempel på algoritmiskt beskrivna kontrollprocesser. Följaktligen är begreppet algoritm en av de centrala idéerna inom cybernetik och datavetenskap.
Exempel på en algoritm.
Låt de möjliga inmatningarna och de möjliga resultaten vara alla möjliga ord över alfabetet $ \{ a, b \} $. Övergången från ett ord $ X $till ett ord $ Y $är ”tillåten” i följande två fall (där $ P $betecknar ett godtyckligt ord): 1) $ X $är av formen $ aP $ och $ Y $är av formen $ Pb $, eller 2) $ X $är av formen $ baP $ och $ Y $är av formen $ Paba $. Instruktionerna är formulerade på följande sätt: ”Ange ett ord som indata, utför de tillåtna övergångarna tills ett ord av formen aaP erhålls; stanna sedan och låt ordet P vara resultatet” . Dessa instruktioner utgör en algoritm, som kommer att betecknas $ \mathfrak A $. Ta ordet $ babaa $ som indata. Efter en övergång får man $ baaaba $; efter den andra får man $ aabaaba $. Här stannar algoritmen med $ baaba $ som resultat. Betrakta en annan inmatning $ baaba $. Man får i tur och ordning följande: $ abaaba, baabab, baabab, abababa, bababab, babababa, babababa , . . . Det kan visas att denna process aldrig kommer att sluta (dvs. inget av de genererade orden kommer någonsin att börja med $ aa $). Ta nu $ abaab $ som indata. Man får $ baabb, abbaba, bbababab $; inga ytterligare tillåtna övergångar är möjliga, och samtidigt uppfylls inte slutvillkoret. Man har ett stopp utan resultat. Således är ingången $ babaa $ lämplig för $ \mathfrak A $, och ingångarna $ baaba $och $ abaab $är det inte.
Algoritmernas betydelse.
Inom vetenskapen påträffas algoritmer överallt: en ”allmän” lösning på ett problem kräver en algoritm. Människans förmåga att addera tal är ett exempel på detta. Inte det faktum att han förr eller senare kan finna summan av två valfria tal, utan snarare i den bemärkelsen att han besitter en metod för den unika additionen av två valfria tal som är givna i skriftlig form, dvs. en additionsalgoritm som t.ex. den välkända kolumnvisa additionsmetoden. Att ”allmänt” lösa ett problem formaliseras som att lösa ett algoritmiskt problem. Ett algoritmiskt problem består av separata probleminstanser, och en enda algoritm måste hittas för att lösa dem alla. Om det inte finns någon sådan algoritm säger man att det algoritmiska problemet är olösligt. Problemet att numeriskt lösa ekvationer av en viss typ och problemet med automatisk översättning är således algoritmiska problem. Deras probleminstanser är att hitta den numeriska lösningen av enskilda ekvationer av given typ respektive översättningen av enskilda fraser. Andra exempel är verifiering av algebraiska likheter i algebra och det algoritmiska problemet att känna igen möjligheten att härleda satser från givna axiom i matematisk logik. (I matematisk logik är begreppet algoritm också viktigt eftersom det ligger till grund för nyckelbegreppet kalkyl, som är en generalisering och en mer exakt form av de intuitiva begreppen ”bevis” och ”demonstration”…). Fastställandet av att ett givet algoritmiskt problem är olösligt (t.ex. problemet att fastställa sanningen eller bevisbarheten hos meningar i något logisk-matematiskt språk) är viktigt, eftersom det visar att specifika probleminstanser av det problemet i princip bara kan lösas med metoder som är specifika för varje enskild probleminstans.
Den vetenskapliga betydelsen av begreppet algoritm har erkänts sedan länge. Sedan de tidigaste tiderna har människor letat efter konstruktiva metoder för att lösa matematiska problem. Sådana ansträngningar gynnades vanligtvis av den nya tillgången till lämpliga symboliska notationer. Denna process har gett ett betydande bidrag till den vetenskapliga kunskapen, särskilt efter det att det hade blivit klart att vissa problem i sig är olösbara (kvadrering av cirkeln osv.). Efter att man insett att vissa problem inte kan lösas genom direkta beräkningar föddes det teoretiska begreppet mängd på 1800-talet. Det är först efter en period av snabb utveckling av detta begrepp (som inte innebar problem med konstruktiva metoder i modern mening) som det i mitten av 1900-talet blev möjligt att återvända till konstruktiva problem, men detta skedde på en annan nivå, berikad av begreppet algoritm som hade utkristalliserats under tiden. Detta begrepp utgör grunden för den konstruktiva trenden inom matematiken.
Ordet ”algoritm” kommer från ordet ”algoritmi” , det senare är den latinska translitterationen av namnet på den arabiske matematikern Al-Khwarizmi från 800-talet. En ”algoritm” i medeltidens Europa var ”decimalpositionssystemet och konsten att räkna med det” , eftersom det är genom den latinska översättningen (1100-talet) av Al-Khwarizmis avhandling som positionssystemet introducerades i Europa.
Strukturen hos en algoritmisk process.
En algoritmisk process är en process där konstruktiva objekt omvandlas i följd med hjälp av diskreta ”steg” , där varje steg består i att ett konstruktivt objekt ersätts med ett annat. När algoritmen $ \mathfrak A $ tillämpas på ordet $ baaba $ följer således i följd orden $ baaba, abaaba, baabab $ osv. Om man till exempel tillämpar algoritmen för kolumnvis subtraktion på talparet <307, 49 >, får man successivt följande konstruktiva objekt:
$$ \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 &258 \\end{array}$$$$
Det bör noteras att i en serie av på varandra följande konstruktiva objekt bestäms varje på varandra följande konstruktivt objekt helt och hållet (inom ramen för den givna algoritmen) av det konstruktiva objektet omedelbart före det. I det mer rigorösa tillvägagångssättet antas också att övergången från ett konstruktivt objekt till det omedelbart följande är tillräckligt ”elementär” – i den meningen att den enstegiga omvandlingen av det föregående till det omedelbart följande objektet är lokal (det är inte hela det konstruktiva objektet som omvandlas, utan endast dess algoritmbegränsade del. Dessutom bestäms inte denna omvandling i sig själv av hela det föregående objektet, utan endast av en begränsad del av det).
Därmed har man inte bara en uppsättning möjliga ingångar och en uppsättning möjliga resultat, utan också en uppsättning möjliga mellanresultat, som representerar det arbetsmedium i vilket den algoritmiska processen utvecklas. När det gäller $ \mathfrak A $ sammanfaller alla dessa tre uppsättningar, men detta gäller inte algoritmen för kolumnvis subtraktion – de möjliga inmatningarna är talpar, de möjliga resultaten är tal (alla i decimalsystemet), medan de möjliga mellanresultaten är ”trevåningsregister” av typen
$$ \$begin{array}{r} p \\\\\underline{- q } \\ r \\end{array}}$$$
där $ q $är den skriftliga uppgiften om talet i decimalsystemet, $ r $är en liknande uppgift eller det tomma ordet, medan $ p $är den skriftliga uppgiften om ett tal i decimalsystemet, med prickar över några av siffrorna. Som regel kan man urskilja flera (inte oberoende) parametrar som är karakteristiska för en algoritm: 1) mängden möjliga ingångar, 2) mängden möjliga resultat, 3) mängden möjliga mellanresultat, 4) startregeln, 5) regeln för direkt övergång, 6) avslutningsregeln och 7) regeln för återvinning av resultatet.
Formalisering av begreppet algoritm.
Begreppet algoritm i sin allmänna form är ett grundläggande matematiskt begrepp som inte kan definieras med hjälp av enklare begrepp. Strängt taget begränsar formaliseringar av begreppet algoritm det faktiskt något. I varje sådan formalisering ges en exakt definition av en viss klass inom vilken var och en av parametrarna kan variera. De olika formaliseringarna skiljer sig från varandra genom valet av sådana klasser. Eftersom parametrarna otvetydigt definierar en algoritm, bestämmer ett val av parameterdomäner en viss klass av algoritmer. Ett sådant val kan dock göra anspråk på att vara en formalisering av det intuitiva algoritmbegreppet endast om man kan vara säker på att det för varje ”intuitiv” algoritm finns en likvärdig algoritm i den klass av algoritmer som definieras av det aktuella valet. Detta krav formuleras för varje formalisering som en grundläggande hypotes, som i det nuvarande kunskapsläget inte kan påvisas matematiskt.
De första formaliseringarna av denna typ kan tillskrivas E.L. Post
och A.M. Turing , , vars konstruktioner i många avseenden föregrep de idéer som moderna datorer bygger på. Det finns också versioner som formulerats av A.A. Markov ,
(jfr Normal algoritm) och av A.N. Kolmogorov , som baserade sin metod på konstruktiva topologiska komplex av en viss typ, vilket gör det möjligt att mer exakt uttrycka egenskapen ”att vara lokal” för en omvandling. I var och en av dessa formaliseringar överensstämmer den grundläggande hypotesen på ett tillfredsställande sätt med praktiken. Ett annat argument för denna hypotes är det faktum att, vilket kan visas, alla formella versioner (av effektiv beräkningsbarhet) som har föreslagits är likvärdiga.
Som exempel kan man betrakta den formalisering som Turing föreslog. I sin ursprungliga form var detta en beskrivning av en teoretisk dator som bestod av 1) ett oändligt band, uppdelat i på varandra följande celler, där varje cell kan innehålla någon symbol ur maskinens ”bandalfabet”, och 2) en ”ändlig kontroll”, som vid varje tidpunkt befinner sig i något ”tillstånd” (ur en given ändlig lista av tillstånd). Den ändliga kontrollen kan förflytta sig längs bandet, en cell i taget, och ändra innehållet i de celler den passerar. Ett program som övervakar den ändliga kontrollens rörelse utgör algoritmen för de beräkningar som utförs på en sådan maskin (en ”Turing-algoritm” ). För en mer exakt och detaljerad beskrivning se Turingmaskin. Här ges en moderniserad framställning av Turings konstruktion. För att definiera en Turing-algoritm specificerar man a) parvis disjunkta alfabet $ B, D, C $, med en särskiljande bokstav $ \lambda $i $ D $och särskiljande bokstäver $ \alpha $och $ \omega $i $ C $; och b) en uppsättning par av formen $ \langle p \xi , \eta Tq \rangle $ där $ p, q \in C $, $ \xi , \eta \in B \cup D $, medan $ T $ är en av de tre symbolerna $ -, 0, + $; i denna uppsättning (som kallas ett program) finns det inte två par med samma första koordinat. De möjliga ingångarna och de möjliga utgångarna är ord över $ B $, medan de möjliga mellanresultaten är ord över $ B \cup D \cup C $ som inte innehåller mer än en bokstav i $ C $. Startregeln är att det initiala ordet $ P $omvandlas till ordet $ \lambda \alpha P \lambda $. Avslutsregeln är att ett mellanresultat som innehåller $ \omega $är slutgiltigt. Regeln för att hämta resultatet är att resultatet är bokstavssekvensen i det slutliga mellanresultatet som följer efter $ \omega $ och föregår den första bokstaven som inte tillhör $ B $. Omvandlingsregeln som omvandlar $ A $ till $ A ^ \prime $ är följande. Bokstaven $ \lambda $ skrivs till vänster och till höger om $ A $; i det sålunda bildade ordet ersätts den del av formen $ \epsilon p \xi $, där $ p \in C $, $ \epsilon \xi \in B \cup D $, med ett ord $ Q $ i enlighet med regeln: Ett par med den första termen $ p \xi $ söks i programmet; låt den andra termen i detta par vara $ \eta Tq $; om $ T $ är $ – $, $ Q = q \epsilon \eta $; om $ T = 0 $, $ Q = \epsilon q \eta $; om $ T $ är $ + $, $ Q = \epsilon \eta q $. Det ord som skapas genom detta utbyte är $ A ^ \prime $. För referenser, se , , , , , , ,
av Algoritmer, teori om.
Den grundläggande hypotesen som nämns ovan brukar kallas Church-Turing-tesen eller Turings hypotes. Denna tes säger att det som kan beräknas effektivt enligt ens intuition om vad som utgör en effektiv process också kan beräknas av en Turing-maskin, dvs. ett formellt definierat begrepp algoritm. På grund av sin karaktär av att identifiera ett intuitivt informellt begrepp med en formell exakt definition kan Church-Turings tes inte bevisas formellt.
Många formaliseringar har visat sig vara likvärdiga, och ingen formalisering har visat sig vara strikt sett mer kraftfull. Förutom de formaliseringar som nämns ovan är följande referenser de mest standardiserade i västvärlden: Churchs formalisering av tal och beräkningsbara funktioner med hjälp av lambda-termer, Kleenes allmänna rekursiva scheman och den registermaskinsmodell som föreslogs av J.C. Shepherdson och H.E. Sturgis och som utvidgades till en mer realistisk datormodell av S.A. Cook och R.A. Reckhow. Markovs och Kolmogorovs versioner är mindre kända. För fullständighetens skull anges också de ursprungliga referenserna till Turing och Post.
| 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) s. 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) s. 217-255 | |
| S.A. Cook, R.A. Reckhow, ”Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) s. 354-375 |