Tarkat ohjeet, jotka määrittelevät laskentaprosessin (jota sanotaan tällöin algoritmiseksi), joka alkaa mielivaltaisesta syötteestä (tietystä määrästä syötteitä, jotka ovat mahdollisia tietylle algoritmille) ja käskyistä, joiden tarkoituksena on saada tulos (tai tuotos), joka määräytyy täysin syötteen perusteella. Esimerkiksi peruskoulussa opetettavat säännöt sarakkeittain tapahtuvaa yhteen- ja vähennyslasku, kertolasku ja jakolasku ovat algoritmeja; näissä algoritmeissa mahdolliset tulokset ovat ei-negatiivisia kokonaislukuja, jotka kirjoitetaan desimaalijärjestelmässä, kun taas mahdolliset syötteet ovat tällaisten lukujen järjestettyjä pareja. Yleensä ei oleteta, että tulos välttämättä saadaan: prosessi, jossa algoritmia sovelletaan johonkin mahdolliseen syötteeseen (eli algoritmiprosessi, joka alkaa tästä syötteestä), voi myös päättyä ilman tulosta (tällöin on kyse tuloksettomasta pysähdyksestä) tai se ei voi päättyä lainkaan. Jos prosessi päättyy (ei pääty), sanotaan, että syöte soveltuu (ei sovellu) kyseiselle algoritmille.
Tärkeä tulos tällä alalla on ns. pysähtymisongelman ratkaisemattomuus. On mahdollista konstruoida sellainen algoritmi $ \alpha $, että ei ole olemassa algoritmia, jolla voidaan päättää, onko jokin mielivaltainen syöte, joka on mahdollinen $ \alpha $:lle $ \alpha $, myös sopiva $ \alpha $:lle $ \alpha $. Erityisesti voidaan löytää sellainen algoritmi $ \alpha $, jonka mahdollisten syötteiden joukko on luonnollisten lukujen joukko.
Algoritmin käsite on yksi keskeisimmistä konsepteista nykyaikaisessa matematiikassa, erityisesti laskennan alalla. Seuraavassa annetaan esimerkki. Tietyn tyyppisten yhtälöiden numeerisen ratkaisun löytäminen on yhtä kuin sellaisen algoritmin rakentaminen, joka muuntaa mielivaltaisen tämän tyyppisen yhtälön ja mielivaltaisen positiivisen rationaaliluvun $ \epsilon $ luvuksi (tai lukujoukoksi), joka eroaa yhtälön juuresta (juurista) vähemmän kuin $ \epsilon $. Algoritmin yhteydessä käytettyä termiä ”laskentaprosessi” ei kuitenkaan pidä ymmärtää niin, että sillä tarkoitettaisiin pelkästään numeerisia laskutoimituksia: jopa alkeisalgebrassa käytetään kirjaimilla tehtäviä laskutoimituksia. Tavallisiin aritmeettisiin laskutoimituksiin liittyy joitakin symboleja, jotka eivät ole numeroita (sulkeet, yhtäläisyysmerkit, aritmeettisten operaattoreiden symbolit). Näin ollen on tarkoituksenmukaista tarkastella algoritmeja, joihin liittyy mielivaltaisia symboleja ja symboleista muodostettuja objekteja. Yksinkertaisin esimerkki tällaisesta objektista on sanan muodostavien symbolien lineaarinen sarja. On myös mahdollista tarkastella ”epälineaarisia” objekteja – algebrallisia matriiseja, jonkin muodollisen kielen johdospuita ja yleisiä graafeja. Intuitiivisesti pienin algoritmien syötteille ja tuloksille asetettu vaatimus on, että niiden on oltava konstruktiivisia objekteja (vrt. Konstruktiivinen objekti). Algoritmin käsite on siis hyvin yleinen. Voidaan puhua algoritmista, jolla käännetään kielestä toiseen, lennonjohtajan algoritmista (joka käsittelee tietoja lentokoneiden liikkeistä kiinteiden sääntöjen mukaisesti) ja muista esimerkeistä algoritmisesti kuvatuista ohjausprosesseista. Näin ollen algoritmin käsite on yksi kybernetiikan ja tietojenkäsittelytieteen keskeisistä ideoista.
Esimerkki algoritmista.
Mahdolliset syötteet ja mahdolliset tulokset ovat kaikki mahdolliset sanat aakkosissa $ \{ a, b \} $. Siirtyminen sanasta $ X $ sanaan $ Y $on ”sallittua” seuraavissa kahdessa tapauksessa (missä $ P $merkitsee mielivaltaista sanaa): 1) $ X $on muotoa $ aP $ ja $ Y $on muotoa $ Pb $; tai 2) $ X $on muotoa $ baP $, kun taas $ Y $on muotoa $ Paba $. Ohjeet muotoillaan seuraavasti: ”Määritä jokin sana syötteeksi, suorita sallitut siirtymät, kunnes saat sanan muodossa aaP; pysäytä sitten ja anna sanan P olla tulos” . Nämä ohjeet muodostavat algoritmin, jota merkitään nimellä $ \mathfrak A $. Syötteenä on sana $ babaa $. Yhden siirtymän jälkeen saadaan $ baaaba $; toisen siirtymän jälkeen saadaan $ aabaabaaba $. Tällöin algoritmi pysähtyy ja tuloksena on $ baaba $. Tarkastellaan toista syötettä $ baaba $. Saadaan peräkkäin $ abaaba, baababab, abababa, bababab, babababa , . . . . $. Voidaan osoittaa, että tämä prosessi ei koskaan pääty (eli yksikään tuotetuista sanoista ei koskaan ala sanalla $ aa $). Otetaan nyt syötteeksi $ abaab $. Saadaan $ baabb, abbaba, bbabab $; muut sallitut siirtymät eivät ole mahdollisia, ja samalla lopetusehto ei täyty. On olemassa tulokseton pysäytys. Näin ollen tulo $ babaa $ on sopiva $ \mathfrak A $:lle, ja tulot $ baaba $ ja $ abaab $ eivät ole.
Algoritmien merkitys.
Tieteessä algoritmeihin törmää kaikkialla: jonkin ongelman ”yleinen” ratkaisu vaatii algoritmin. Ihmisen kyky laskea lukuja yhteen on esimerkki tästä. Kyse ei ole siitä, että hän löytää ennemmin tai myöhemmin minkä tahansa kahden luvun summan, vaan pikemminkin siitä, että hänellä on hallussaan menetelmä minkä tahansa kahden luvun yksikäsitteiseen yhteenlaskuun, joka on annettu kirjallisessa muodossa, eli yhteenlaskualgoritmi, kuten tunnettu pylväskohtainen yhteenlasku. ”Yleensä” ongelman ratkaiseminen formalisoidaan algoritmisen ongelman ratkaisemiseksi. Algoritminen ongelma koostuu erillisistä ongelmatapauksista, ja kaikkien niiden ratkaisemiseksi on löydettävä yksi algoritmi. Jos tällaista algoritmia ei ole, sanotaan, että algoritminen ongelma on ratkaisematon. Näin ollen tietyn tyyppisten yhtälöiden numeerisen ratkaisemisen ongelma ja automaattisen kääntämisen ongelma ovat algoritmisia ongelmia. Niiden ongelmaesimerkkejä ovat vastaavasti tietyn tyyppisten yksittäisten yhtälöiden numeerisen ratkaisun löytäminen ja yksittäisten lauseiden kääntäminen. Muita esimerkkejä ovat algebran algebrallisten yhtäsuuruuksien todentaminen algebrassa ja matemaattisen logiikan algoritminen ongelma, joka koskee lauseiden pääteltävyyden tunnistamista annetuista aksioomista. (Matemaattisessa logiikassa algoritmin käsite on myös tärkeä, koska se toimii perustana laskennan keskeiselle käsitteelle, joka on yleistys ja tarkempi muoto intuitiivisista käsitteistä ”todiste” ja ”osoitus” .). Tietyn algoritmisen ongelman ratkaisemattomuuden toteaminen (esim. ongelma, joka koskee lauseiden totuuden tai todistettavuuden toteamista jollakin loogis-matemaattisella kielellä) on tärkeää, koska se osoittaa, että kyseisen ongelman tietyt ongelmatapaukset voidaan periaatteessa ratkaista vain kullekin yksittäiselle ongelmatapaukselle ominaisten menetelmien avulla.
Algoritmin käsitteen tieteellinen merkitys on tunnustettu jo pitkään. Jo varhaisimmista ajoista lähtien ihmiset ovat etsineet konstruktiivisia menetelmiä matemaattisten ongelmien ratkaisemiseksi. Tällaiset pyrkimykset hyötyivät yleensä sopivien symbolisten merkintätapojen uudesta saatavuudesta. Tämä prosessi on edistänyt merkittävästi tieteellistä tietämystä erityisesti sen jälkeen, kun oli käynyt selväksi, että jotkin ongelmat ovat luonnostaan ratkaisemattomia (ympyrän neliöiminen jne.). Kun oli havaittu, että tiettyjä ongelmia ei voida ratkaista suorilla laskutoimituksilla, syntyi 1800-luvulla teoreettinen käsite joukko. Vasta tämän käsitteen nopean kehityksen jälkeen (johon ei liittynyt konstruktiivisten menetelmien ongelmia niiden nykyaikaisessa merkityksessä) oli 1900-luvun puolivälissä mahdollista palata konstruktiivisiin ongelmiin, mutta tämä tapahtui eri tasolla, jota rikastutti sillä välin kiteytynyt algoritmin käsite. Tämä käsite muodostaa perustan matematiikan konstruktiiviselle suuntaukselle.
Sana ”algoritmi” tulee sanasta ”algoritmi” , joka on latinankielinen translitteraatio 9. vuosisadan arabialaisen matemaatikon Al-Khwarizmin nimestä. ”Algoritmi” oli keskiajan Euroopassa ”desimaalipositiojärjestelmä ja sen avulla laskemisen taito” , sillä Al-Khwarizmin tutkielman latinankielisen käännöksen (1200-luvulla) kautta positiojärjestelmä otettiin käyttöön Euroopassa.
Algoritmiprosessin rakenne.
Algoritmiprosessi on prosessi, jossa konstruktiivisia objekteja muunnetaan peräkkäin erillisten ”askeleiden” avulla, ja kukin askel muodostuu yhden konstruktiivisen objektin korvaamisesta toisella objektilla. Sovellettaessa siis algoritmia $ \mathfrak A $ sanaan $ baaba $ saadaan peräkkäin sanat $ baaba, abaaba, baabab $ jne. Jos sovelletaan esimerkiksi sarakeskeisen vähennyslaskun algoritmia numeropariin <307, 49 >, saadaan peräkkäin seuraavat konstruktiiviset objektit:
$ $ $ \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}$$
Huomautetaan, että peräkkäisten konstruktiokohteiden sarjassa kukin peräkkäinen konstruktiokohde määräytyy (kyseisen algoritmin puitteissa) täysin sitä välittömästi edeltävän konstruktiokohteen perusteella. Tiukemmassa lähestymistavassa oletetaan myös, että siirtyminen mistä tahansa konstruktiivisesta objektista sitä välittömästi seuraavaan on riittävän ”alkeellista” – siinä mielessä, että edeltävän objektin yhden askeleen transformaatio välittömästi seuraavaan objektiin on paikallinen (ei koko konstruktiivinen objekti muutu, vaan vain sen algoritmin rajoittama osa; lisäksi tämä transformaatio itsessään ei määräydy täydellisenä edeltävästä objektista, vaan vain sen rajoitetusta osasta).
Siten meillä ei ole vain joukko mahdollisia syötteitä ja joukko mahdollisia tuloksia, vaan myös joukko mahdollisia välituloksia, jotka edustavat työympäristöä, jossa algoritminen prosessi kehittyy. Kun kyseessä on $ \mathfrak A $, kaikki nämä kolme joukkoa ovat yhteneväisiä, mutta tämä ei päde sarakekohtaisen vähennyslaskun algoritmiin – mahdolliset syötteet ovat numeropareja, mahdolliset tulokset ovat numeroita (kaikki desimaalijärjestelmässä), kun taas mahdolliset välitulokset ovat ”kolmikerroksisia” tietueita, jotka ovat tyypiltään
$$$ \begin{array}{r} p \\\\\underline{- q } \\\ r \\\\end{array}$$
jossa $ q $ on numeron kirjoitettu tietue desimaalijärjestelmässä, $ r $ on samanlainen tietue tai tyhjä sana, kun taas $ p $ on numeron kirjoitettu tietue desimaalijärjestelmässä, jossa on pisteitä joidenkin numeroiden päällä. Pääsääntöisesti voidaan erottaa useita algoritmille ominaisia (ei riippumattomia) parametreja: 1) mahdollisten syötteiden joukko, 2) mahdollisten tulosten joukko, 3) mahdollisten välitulosten joukko, 4) aloitussääntö, 5) suoran siirtymän sääntö, 6) lopetussääntö ja 7) tuloksen hakusääntö.
Algoritmin käsitteen formalisointi.
Algoritmin käsite yleisessä muodossaan on matemaattinen peruskäsite, jota ei voida määritellä yksinkertaisempien käsitteiden avulla. Tarkkaan ottaen algoritmin käsitteen formalisoinnit itse asiassa rajoittavat sitä jonkin verran. Jokaisessa tällaisessa formalisoinnissa annetaan tarkka määritelmä jollekin luokalle, jonka sisällä kukin parametri voi vaihdella. Eri formalisoinnit eroavat toisistaan näiden luokkien valinnan perusteella. Koska parametrit määrittelevät yksiselitteisesti jonkin algoritmin, parametrialueiden valinta määrittää jonkin algoritmiluokan. Tällainen valinta voi kuitenkin väittää olevansa intuitiivisen algoritmin käsitteen formalisointi vain, jos voidaan olla varmoja siitä, että mille tahansa ”intuitiiviselle” algoritmille on olemassa vastaava algoritmi tarkasteltavan valinnan määrittelemässä algoritmien luokassa. Tämä vaatimus muotoillaan kullekin formalisoinnille perushypoteesiksi, jota ei nykytietämyksen mukaan voida matemaattisesti osoittaa.
Ensimmäiset tämäntyyppiset formalisoinnit ovat E.L. Postin
ja A.M. Turingin ansiota , , jonka konstruktiot ennakoivat monessa suhteessa niitä ajatuksia, joihin nykyaikaiset tietokoneet perustuvat. On myös versioita, jotka ovat muotoilleet A.A. Markov ,
(vrt. Normaalialgoritmi) ja A.N. Kolmogorov , , joka perusti lähestymistavan tietyntyyppisiin konstruktiivisiin topologisiin komplekseihin, joiden avulla on mahdollista ilmaista tarkemmin transformaation ”paikallisena olemisen” ominaisuus. Kussakin näistä formalisoinneista perushypoteesi on tyydyttävässä sopusoinnussa käytännön kanssa. Toinen tämän hypoteesin puolesta puhuva argumentti on se, että, kuten voidaan osoittaa, kaikki ehdotetut muodolliset versiot (tehokkaasta laskettavuudesta) ovat ekvivalentteja.
Tarkastellaan esimerkiksi Turingin ehdottamaa formalisointia. Alkuperäisessä muodossaan se oli kuvaus jostakin teoreettisesta tietokoneesta, joka koostui 1) äärettömästä nauhasta, joka on jaettu peräkkäisiin soluihin, joista kukin solu kykenee sisältämään jonkin symbolin koneen ”nauhan aakkosista”; ja 2) ”äärellisestä ohjaimesta”, joka kullakin ajanhetkellä on jossakin ”tilassa” (annetusta äärellisestä tilojen luettelosta). Äärellinen ohjaus voi liikkua nauhaa pitkin solu kerrallaan ja muuttaa ohittamiensa solujen sisältöä. Ohjelma, joka valvoo äärellisen ohjaimen liikettä, muodostaa algoritmin tällaisella koneella suoritettaville laskutoimituksille (”Turingin algoritmi” ). Tarkempi ja yksityiskohtaisempi kuvaus on kohdassa Turingin kone. Tässä esitetään Turingin konstruktion nykyaikaistettu selitys. Turingin algoritmin määrittelemiseksi määritetään a) pareittain erilliset aakkoset $ B, D, C $, joissa on erillinen kirjain $ \lambda $ D $:ssa $ D $ ja erillinen kirjain $ \alpha $ ja $ \omega $ C $:ssa $ C $; ja b) joukko pareja, jotka ovat muotoa $ \langle p \xi , \eta Tq \rangle $, jossa $ p, q \in C $, $ \xi , \eta \in B \cup D $, kun taas $ T $ on yksi kolmesta symbolista $ -, 0, + $; tässä joukossa (jota kutsutaan ohjelmaksi) ei ole kahta paria, joilla olisi sama ensimmäinen koordinaatti. Mahdolliset syötteet ja mahdolliset tulosteet ovat $ B $:n sanoja, kun taas mahdolliset välitulokset ovat $ B \cup D \cup C $:n sanoja, jotka sisältävät enintään yhden $ C $:n kirjaimen. Aloitussääntö on, että alkusana $ P $ muunnetaan sanaksi $ \lambda \alpha P \lambda $. Lopetussääntö on, että välitulos, joka sisältää $ \omega $, on lopullinen. Tuloksen hakusääntö on, että tuloksena on lopullisen välituloksen kirjainsarja, joka seuraa $ \omega $ ja edeltää ensimmäistä kirjainta, joka ei kuulu $ B $. Muunnossääntö, joka muuntaa $ A $:n $:ksi $ A ^ \prime $, on seuraava. Kirjain $ \lambda $ kirjoitetaan $ A $:n vasemmalle ja oikealle puolelle; näin muodostetussa sanassa osa muotoa $ \epsilon p \xi $, jossa $ p \in C $, $ \epsilon \xi \in B \cup D $, korvataan sanalla $ Q $ säännön mukaisesti: Jos $ T $ on $ – $, $ Q = q \epsilon \eta $; jos $ T = 0 $, $ Q = \epsilon q \eta $; jos $ T $ on $ + $, $ Q = \epsilon \eta q $. Tämän vaihdon tuloksena syntyvä sana on $ A ^ \prime $. Viitteitä , , , , , , , ,
on Algoritmit, teoria.
Yllä mainittua perushypoteesia kutsutaan yleensä Church-Turing-teesiksi tai Turingin hypoteesiksi. Tämän teesin mukaan se, mikä voidaan laskea tehokkaasti sen intuition mukaan, mikä on tehokas prosessi, voidaan laskea myös Turingin koneella eli muodollisesti määritellyllä algoritmin käsitteellä. Koska Church-Turing-teesi on luonteeltaan sellainen, että se samaistaa intuitiivisen epävirallisen käsitteen muodolliseen täsmälliseen määritelmään, sitä ei voida muodollisesti todistaa.
Monet formalisoinnit ovat osoittautuneet samanarvoisiksi, eikä yksikään formalisointi ole osoittautunut ehdottomasti tehokkaammaksi. Edellä mainittujen formalisointien lisäksi seuraavat viitteet ovat länsimaissa vakiintuneimpia: Churchin formalisointi luvuista ja laskettavista funktioista lambda-termeillä, Kleenen yleiset rekursiiviset skeemat sekä J.C. Shepherdsonin ja H.E. Sturgisin ehdottama rekisterikoneiden malli, jota S.A. Cook ja R.A. Reckhow laajensivat realistisemmaksi tietokonemalliksi. Markovin ja Kolmogorovin versiot ovat vähemmän tunnettuja. Täydellisyyden vuoksi esitetään myös alkuperäiset viittaukset Turingiin ja Postiin.
| A.M. Turing, ”On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) s. 230-265 | |
| A.M. Turing, ”Corrections to ”On computable numbers, with an application to the Entscheidungsproblem” ” Proc. London Math.Soc. Ser. 2 , 43 (1937) s. 544-546 | |
| A. Church, ”An unsolvable problem of elementary number theory” Amer. J. Math. , 58 (1936) s. 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) s. 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 |