Gedetailleerde instructies die een rekenproces definiëren (dat dan algoritmisch wordt genoemd), dat begint met een willekeurige input (uit een bepaald aantal inputs dat mogelijk is voor het gegeven algoritme), en met instructies die gericht zijn op het verkrijgen van een resultaat (of output) dat volledig wordt bepaald door de input. Zo zijn de regels die op de lagere school worden geleerd voor kolomsgewijs optellen, aftrekken, vermenigvuldigen en delen algoritmen; in deze algoritmen zijn de mogelijke uitkomsten gehele niet-negatieve getallen, geschreven in het decimale stelsel, terwijl de mogelijke ingangen geordende paren van dergelijke getallen zijn. In het algemeen wordt niet verondersteld dat het resultaat noodzakelijkerwijs wordt verkregen: het proces van toepassing van een algoritme op een mogelijke invoer (d.w.z. een algoritmisch proces dat uitgaat van deze invoer) kan ook eindigen zonder dat een resultaat wordt verkregen (in dat geval is er sprake van een “geen-resultaat-stop”) of kan helemaal niet eindigen. Als het proces eindigt (niet eindigt), dan zegt men dat de input geschikt is (niet geschikt is) voor het algoritme in kwestie.
Een belangrijk resultaat op dit gebied is de onbeslisbaarheid van het z.g. halteringsprobleem. Het is mogelijk een algoritme $ \alpha $ zo te construeren dat er geen algoritme is om te beslissen of een willekeurige invoer die mogelijk is voor $ \alpha $ ook geschikt is voor $ \alpha $. In het bijzonder kan men zo’n algoritme $ \alpha $ vinden waarvoor de verzameling van zijn mogelijke invoer de verzameling natuurlijke getallen is.
Het begrip algoritme is een van de centrale begrippen in de moderne wiskunde, vooral op het gebied van berekeningen. Hieronder wordt een voorbeeld gegeven. Het vinden van de numerieke oplossing van vergelijkingen van een bepaald type komt neer op het construeren van een algoritme dat een willekeurige vergelijking van dit type en een willekeurig positief rationaal getal $ \epsilon $ omzet in een getal (of een verzameling getallen) dat minder dan $ \epsilon $ verschilt van de wortel(s) van deze vergelijking. De term “rekenproces”, zoals gebruikt in de context van een algoritme, moet echter niet worden opgevat als louter numerieke berekeningen: zelfs in elementaire algebra worden berekeningen met letters gebruikt. Bij standaard rekenkundige berekeningen worden bepaalde symbolen gebruikt die geen getallen zijn (haakjes, gelijkheidstekens, symbolen voor rekenkundige operatoren). Daarom is het nuttig algoritmen te beschouwen met willekeurige symbolen en objecten die uit symbolen zijn samengesteld. Het eenvoudigste voorbeeld van zo’n object is een lineaire opeenvolging van symbolen die een woord vormen. Het is ook mogelijk “niet-lineaire” objecten te beschouwen – algebraïsche matrices, afleidingen van een formele taal en algemene grafieken. Intuïtief is de minste eis die aan de inputs en resultaten van algoritmen wordt gesteld, dat zij constructieve objecten moeten zijn (cf. Constructief object). Het begrip algoritme is dus zeer algemeen. Men kan spreken van een algoritme voor de vertaling van de ene taal in de andere, van een algoritme van een luchtverkeersleider (die informatie over de bewegingen van vliegtuigen volgens vaste regels verwerkt), en andere voorbeelden van algoritmisch beschreven regelprocessen. Het begrip algoritme is dan ook een van de centrale ideeën in de cybernetica en de informatica.
Voorbeeld van een algoritme.
Laat de mogelijke ingangen en de mogelijke uitkomsten alle mogelijke woorden zijn over het alfabet $ \{ a, b \} $. De overgang van een woord $ X $ naar een woord $ Y $ is “toelaatbaar” in de volgende twee gevallen (waarbij $ P $ een willekeurig woord aanduidt): 1) $ X $ heeft de vorm $ aP $, en $ Y $ heeft de vorm $ Pb $; of 2) $ X $ heeft de vorm $ baP $, en $ Y $ heeft de vorm $ Paba $. De instructies worden als volgt geformuleerd: “wijs een woord aan als invoer, voer de toegestane overgangen uit totdat een woord van de vorm aaP wordt verkregen; stop dan en laat woord P het resultaat zijn” . Deze instructies vormen een algoritme, dat zal worden aangeduid met $ babaa $. Neem als invoer het woord $ babaa $. Na één transitie verkrijgt men $ baaaba $; na de tweede verkrijgt men $ aabaaba $. Hier stopt het algoritme met $ baaba $ als resultaat. Beschouw een andere invoer $ baaba $. Men verkrijgt achtereenvolgens $ abaaba, baabab, abababa, bababab, babababa , …. Men kan aantonen dat dit proces nooit zal eindigen (d.w.z. geen van de gegenereerde woorden zal ooit beginnen met $ aa $). Neem nu $ abaab $ als invoer. Men verkrijgt $ baabb, abbaba, bbabab $; geen verdere toelaatbare overgangen zijn mogelijk, en tegelijkertijd is niet aan de beëindigingsvoorwaarde voldaan. Men heeft een geen-resultaat-stop. Zo is de input $ babaa $ geschikt voor $ $mathfrak A $, en de input $ baaba $ en $ abaab $ niet.
De betekenis van algoritmen.
In de wetenschap komt men algoritmen overal tegen: een “algemene” oplossing van een probleem vereist een algoritme. Het vermogen van de mens om getallen op te tellen is daar een voorbeeld van. Niet het feit dat hij vroeg of laat de som van twee willekeurige getallen kan vinden, maar wel in die zin dat hij een methode bezit voor de unieke optelling van twee willekeurige getallen, gegeven in geschreven vorm, d.w.z. een optelalgoritme zoals de bekende kolom-wijze optelmethode. “In het algemeen” wordt het oplossen van een probleem geformaliseerd als het oplossen van een algoritmisch probleem. Een algoritmisch probleem bestaat uit afzonderlijke probleemgevallen, en er moet één algoritme worden gevonden voor de oplossing van al deze probleemgevallen. Als zo’n algoritme niet bestaat, zegt men dat het algoritmisch probleem onoplosbaar is. Het probleem van het numeriek oplossen van vergelijkingen van een bepaald type en het probleem van het automatisch vertalen zijn dus algoritmische problemen. Hun probleemgevallen zijn respectievelijk het vinden van de numerieke oplossing van afzonderlijke vergelijkingen van het gegeven type, en de vertaling van afzonderlijke zinnen. Andere voorbeelden zijn de verificatie van algebraïsche gelijkheden in de algebra; het algoritmische probleem van de herkenning van de afleidbaarheid van proposities uit gegeven axioma’s in de mathematische logica. (In de mathematische logica is het begrip algoritme ook belangrijk omdat het als basis dient voor het sleutelbegrip calculus, dat een veralgemening en een preciezere vorm is van de intuïtieve begrippen “bewijs” en “demonstratie”). De vaststelling van de onoplosbaarheid van een gegeven algoritmisch probleem (b.v. het probleem van de vaststelling van de waarheid of aantoonbaarheid van zinnen in een of andere logisch-mathematische taal) is belangrijk, omdat daaruit blijkt dat specifieke probleemgevallen van dat probleem in principe alleen kunnen worden opgelost met methoden die specifiek zijn voor elk afzonderlijk probleemgeval.
Het wetenschappelijk belang van het begrip algoritme wordt al heel lang onderkend. Sinds de vroegste tijden heeft men gezocht naar constructieve methoden om wiskundige problemen op te lossen. Dergelijke inspanningen profiteerden meestal van de nieuwe beschikbaarheid van geschikte symbolische notaties. Dit proces heeft een belangrijke bijdrage geleverd aan de wetenschappelijke kennis, vooral nadat duidelijk was geworden dat sommige problemen inherent onoplosbaar zijn (kwadratuur van de cirkel, enz.). Nadat men had ingezien dat bepaalde problemen niet door directe berekeningen kunnen worden opgelost, ontstond in de 19e eeuw het theoretische begrip “verzameling”. Pas na een periode van snelle ontwikkeling van dit concept (waarbij het niet ging om problemen van constructieve methoden in hun moderne betekenis), kon men in het midden van de 20e eeuw terugkeren naar constructieve problemen, maar dit gebeurde op een ander niveau, verrijkt door het concept van een algoritme dat zich intussen had uitgekristalliseerd. Dit begrip vormt de basis van de constructieve tendens in de wiskunde.
Het woord “algoritme” komt van het woord “algoritmi” , dit laatste is de Latijnse transliteratie van de naam van de 9e eeuwse Arabische wiskundige Al-Khwarizmi. Een “algoritme” was in het Europa van de Middeleeuwen “het decimale-positiestelsel en de kunst om ermee te rekenen” , want het is door de Latijnse vertaling (12e eeuw) van de verhandeling van Al-Khwarizmi dat het positiestelsel in Europa werd geïntroduceerd.
De structuur van een algoritmisch proces.
Een algoritmisch proces is een proces van opeenvolgende omzettingen van constructieve objecten door discrete “stappen” , waarbij elke stap bestaat uit de vervanging van een constructief object door een ander. Als men dus het algoritme $\mathfrak A $ toepast op het woord $ baaba $, dan volgen achtereenvolgens de woorden $ baaba, abaaba, baabab $, enz. Als men bijvoorbeeld het algoritme van kolomgewijs aftrekken toepast op het getallenpaar <307, 49 >, dan krijgt men achtereenvolgens de volgende constructieve objecten:
$$ \begin{array}{rrrr}307 &3 \7 &>Dot{3} \dot{0} 7 &\dot{3} \7 &Onderstreping{- 49 } &Onderstreping{- 49 } &Onderlijn{- 49 } &Onderlijn{- 49 } \\{} & 8 &58 &258 \einde{array}$$
Opgemerkt zal worden dat in een reeks van opeenvolgende constructieve objecten, elk opeenvolgend constructief object volledig bepaald wordt (in het kader van het gegeven algoritme) door het constructief object dat er onmiddellijk aan voorafgaat. In de meer rigoureuze benadering wordt tevens aangenomen dat de overgang van elk constructief object naar het onmiddellijk daarop volgende voldoende “elementair” is – in die zin dat de transformatie in één stap van het voorgaande in het onmiddellijk daaropvolgende object lokaal is (niet het gehele constructieve object wordt getransformeerd, maar slechts het algoritme-beperkte deel ervan; bovendien wordt deze transformatie zelf niet bepaald door het gehele voorgaande object, maar slechts door een beperkt deel ervan).
Dus heeft men niet alleen een reeks mogelijke ingangen en een reeks mogelijke uitkomsten, maar ook een reeks mogelijke tussenresultaten, die het werkmedium vertegenwoordigen waarin het algoritmische proces zich ontwikkelt. Voor $ \mathfrak A $ vallen deze drie verzamelingen samen, maar dit geldt niet voor het algoritme van kolomgewijs aftrekken – de mogelijke ingangen zijn getallenparen, de mogelijke uitkomsten zijn getallen (alle in het decimale stelsel), terwijl de mogelijke tussenresultaten “drie-verdiepingen”-records zijn van het type
$$ \begin{array}{r} p \onderstrepen{- q } \\ r einde{array}$$
waarbij $ q $ het geschreven nummer in het decimale stelsel is, $ r $ een soortgelijk nummer of het lege woord, terwijl $ p $ het geschreven nummer in het decimale stelsel is, met punten over sommige cijfers. Als regel kunnen verschillende (niet onafhankelijke) parameters worden onderscheiden die kenmerkend zijn voor een algoritme: 1) de verzameling van mogelijke ingangen; 2) de verzameling van mogelijke resultaten; 3) de verzameling van mogelijke tussenresultaten; 4) de startregel; 5) de directe overgangsregel; 6) de beëindigingsregel; en 7) de regel voor het opvragen van het resultaat.
Formalisering van het begrip algoritme.
Het begrip algoritme in zijn algemene vorm is een fundamenteel wiskundig begrip dat niet in termen van eenvoudiger begrippen kan worden gedefinieerd. Strikt genomen beperken formaliseringen van het begrip algoritme het begrip in feite enigszins. In elke formalisering wordt een exacte definitie gegeven van een klasse waarbinnen elk van de parameters kan variëren. De verschillende formaliseringen verschillen van elkaar door de keuze van dergelijke klassen. Aangezien de parameters ondubbelzinnig een of ander algoritme definiëren, bepaalt een keuze van parameterdomeinen een of andere klasse van algoritmen. Een dergelijke keuze kan echter slechts aanspraak maken op een formalisering van het intuïtieve begrip algoritme, indien men er zeker van kan zijn dat er voor elk “intuïtief” algoritme een equivalent algoritme bestaat in de klasse van algoritmen die door de beschouwde keuze wordt gedefinieerd. Deze eis wordt voor elke formalisering geformuleerd als een fundamentele hypothese, die bij de huidige stand van de kennis niet wiskundig kan worden aangetoond.
De eerste formaliseringen van dit type zijn te danken aan E.L. Post
en aan A.M. Turing , wiens constructies in vele opzichten vooruitliepen op de ideeën waarop moderne computers zijn gebaseerd. Er zijn ook versies geformuleerd door A.A. Markov,
(cf. Normaal algoritme) en door A.N. Kolmogorov , die de benadering baseerde op constructieve topologische complexen van een bepaald type, waardoor het mogelijk wordt de eigenschap van “lokaal zijn” van een transformatie nauwkeuriger uit te drukken. In elk van deze formaliseringen is de fundamentele hypothese bevredigend in overeenstemming met de praktijk. Een ander argument ten gunste van deze hypothese is het feit dat, zoals kan worden aangetoond, alle formele versies (van effectieve berekenbaarheid) die zijn voorgesteld equivalent zijn.
Als voorbeeld, beschouw de door Turing voorgestelde formalisering. In zijn oorspronkelijke vorm was dit een beschrijving van een of andere theoretische computer bestaande uit 1) een oneindige band, verdeeld in opeenvolgende cellen, waarbij elke cel een of ander symbool uit het “bandalfabet” van de machine kan bevatten; en 2) een “eindige besturing,” die zich op elk moment van de tijd in een of andere “toestand” bevindt (uit een gegeven eindige lijst van toestanden). De eindige besturing kan zich langs de band verplaatsen, één cel tegelijk, en de inhoud veranderen van de cellen die zij passeert. Een programma dat de beweging van de eindige besturing controleert, vormt het algoritme voor de berekeningen die op zo’n machine worden uitgevoerd (een “Turing-algoritme” ). Voor een meer exacte en meer gedetailleerde beschrijving zie Turing machine. Hier wordt een gemoderniseerde uiteenzetting van Turing’s constructie gegeven. Om een Turing algoritme te definiëren, specificeert men a) paarsgewijs disjuncte alfabetten $ B, D, C $, met een onderscheidende letter $ $ libda $ in $ D $ en onderscheidende letters $ \alpha $ en $ \omega $ in $ C $; en b) een verzameling paren van de vorm $ \langle p \xi , \eta Tq \rangle $ waarbij $ p, q \in C $, $ \xi , \eta \in B \cup D $, terwijl $ T $ een van de drie symbolen $ -, 0, + $ is; in deze verzameling (die een programma wordt genoemd) zijn er geen twee paren met dezelfde eerste coördinaat. De mogelijke ingangen en de mogelijke uitgangen zijn woorden over $ B $, terwijl de mogelijke tussenresultaten woorden zijn over $ B $ D $ $ die niet meer dan één letter van $ C $ bevatten. De beginregel is dat het beginwoord $ P $ wordt omgezet in het woord $ \lambda \alpha P \lambda $. De eindregel is dat een tussenresultaat dat $ \omega $ bevat, definitief is. De regel voor het ophalen van de output is dat de output de letterreeks is in het uiteindelijke tussenresultaat dat volgt op $ \omega $ en voorafgaat aan de eerste letter die niet behoort tot $ B $. De transformatieregel die $ A $ omzet in $ A ^ \prime $ is als volgt. De letter $ libda $ wordt links en rechts van $ A $ geschreven; in het aldus gevormde woord wordt het deel van de vorm $ \epsilon p \xi $, waarbij $ p \in C $, $ \epsilon \xi \in B \cup D $, vervangen door een woord $ Q $ volgens de regel: een paar met de eerste term $ p \xi $ wordt gezocht in het programma; laat de tweede term van dit paar $ \eta Tq $ zijn; als $ T $ is $ – $, $ Q = q \xilon \eta $; als $ T = 0 $, $ Q = \epsilon q \eta $; als $ T $ is $ + $, $ Q = \epsilon \eta q $. Het woord dat door deze ruil ontstaat is $ A ^ \prime $. Voor referenties, zie , , , , , ,
of Algorithms, theory of.
De hierboven genoemde fundamentele hypothese wordt gewoonlijk de Church-Turing these of de hypothese van Turing genoemd. Deze stelling stelt dat wat effectief kan worden berekend volgens iemands intuïtie over wat een effectief proces is, ook kan worden berekend door een Turing machine, d.w.z. een formeel gedefinieerd begrip van algoritme. Door de aard zelf van het identificeren van een intuïtief informeel begrip met een formele precieze definitie, kan de Church-Turing these niet formeel bewezen worden.
Vele formalisaties zijn gelijkwaardig gebleken, en geen enkele formalisatie is strikt krachtiger gebleken. Afgezien van de hierboven genoemde formalisaties zijn de volgende referenties de meest standaard in het Westen: Church’s formalisering van getallen en berekenbare functies door lambda-termen, Kleene’s algemene recursieve schema’s, en het door J.C. Shepherdson en H.E. Sturgis voorgestelde model van de registermachine, dat door S.A. Cook en R.A. Reckhow tot een realistischer computermodel werd uitgebreid. De versies van Markov en Kolmogorov zijn minder bekend. Voor de volledigheid worden ook de oorspronkelijke referenties naar Turing en Post gegeven.
| 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 |