Egy olyan számítási folyamatot meghatározó (ilyenkor algoritmikusnak mondott) részletes utasítások, amely egy tetszőleges bemenettel kezdődik (az adott algoritmus számára lehetséges bemenetek bizonyos száma közül), és olyan utasításokkal, amelyek célja egy olyan eredmény (vagy kimenet) elérése, amelyet a bemenet teljes mértékben meghatároz. Például az általános iskolákban az oszloponkénti összeadásra, kivonásra, szorzásra és osztásra tanított szabályok algoritmusok; ezekben az algoritmusokban a lehetséges eredmények nemnegatív egész számok a tizedes rendszerben írva, míg a lehetséges bemenetek ilyen számok rendezett párjai. Általában nem feltételezzük, hogy az eredményt feltétlenül megkapjuk: az algoritmus valamilyen lehetséges bemenetre való alkalmazásának folyamata (azaz egy algoritmikus folyamat, amely ebből a bemenetből kiindulva halad) eredmény nélkül is befejeződhet (ilyen esetben eredmény nélküli megállásról van szó), vagy egyáltalán nem fejeződik be. Ha a folyamat befejeződik (nem fejeződik be), akkor azt mondjuk, hogy a bemenet alkalmas (nem alkalmas) az adott algoritmus számára.
Egy fontos eredmény ezen a területen az úgynevezett megállási probléma eldönthetetlensége. Lehetséges olyan $ \alpha $ algoritmust konstruálni, hogy nincs algoritmus annak eldöntésére, hogy egy tetszőleges bemenet, amely lehetséges $ \alpha $ számára, alkalmas-e $ \alpha $ számára is.
Az algoritmus fogalma a modern matematika egyik központi fogalma, különösen a számítások területén. Erre az alábbiakban egy példát mutatunk be. Egy adott típusú egyenlet numerikus megoldásának megtalálása egyenlő egy olyan algoritmus megalkotásával, amely egy tetszőleges ilyen típusú egyenletet és egy tetszőleges $ \epsilon $ pozitív racionális számot olyan számmá (vagy számok halmazává) alakít, amely kisebb mértékben tér el az egyenlet gyökétől (gyökeitől), mint $ \epsilon $. Az algoritmussal összefüggésben használt “számítási folyamat” kifejezés azonban nem csupán numerikus számításokat jelent: még az elemi algebrában is használnak betűkkel végzett számításokat. A szokásos aritmetikai számítások tartalmaznak néhány olyan szimbólumot, amelyek nem számok (zárójelek, egyenlőségjelek, az aritmetikai operátorok szimbólumai). Ennek megfelelően célszerű olyan algoritmusokat is figyelembe venni, amelyek tetszőleges szimbólumokat és szimbólumokból összeállított objektumokat tartalmaznak. A legegyszerűbb példa egy ilyen objektumra egy szót alkotó szimbólumok lineáris sorozata. Lehetőség van “nem lineáris” objektumok – algebrai mátrixok, bizonyos formális nyelvek származtatási fái és általános gráfok – vizsgálatára is. Intuitív módon az algoritmusok bemeneteivel és eredményeivel szemben a legkisebb követelmény, hogy konstruktív objektumok legyenek (vö. Konstruktív objektum). Így az algoritmus fogalma nagyon általános. Beszélhetünk az egyik nyelvről a másikra való fordítás algoritmusáról, egy légiforgalmi irányító algoritmusáról (a repülőgépek mozgására vonatkozó információk feldolgozása rögzített szabályok szerint), és más példák az algoritmikusan leírt irányítási folyamatokra. Következésképpen az algoritmus fogalma a kibernetika és a számítástechnika egyik központi gondolata.
Példa egy algoritmusra.
Legyen a lehetséges bemenetek és a lehetséges eredmények a $ \{ a, b \} $ ábécé összes lehetséges szava. Az átmenet egy $ X $ szóról egy $ Y $ szóra a következő két esetben “megengedett” (ahol $ P $egy tetszőleges szót jelöl): 1) $ X $az $ aP $ alakú, $ Y $ pedig a $ Pb $ alakú; vagy 2) $ X $az $ baP $ alakú, míg $ Y $az $ Paba $ alakú. Az utasításokat a következőképpen fogalmazzuk meg: “valamilyen szót jelölve meg bemenetként, hajtsuk végre a megengedett átmeneteket, amíg aaP alakú szót nem kapunk; ezután álljunk meg, és legyen a P szó az eredmény” . Ezek az utasítások egy algoritmust alkotnak, amelyet a továbbiakban $ \mathfrak A $-val jelölünk. Vegyük a $ babaa $ szót bemenetként. Egy átmenet után $ baaaba $-t kapunk; a második után $ aabaabaaba $-t. Itt az algoritmus megáll $ baaba $ eredményével. Tekintsünk egy másik bemenetet $ baaba $. Az egymás után következő eredményeket kapjuk: $ abaaba, baababab, abababa, babababab, babababa , . . . . $. Megmutatható, hogy ez a folyamat soha nem ér véget (azaz a generált szavak egyike sem kezdődik $ aa $-val). Most vegyük az $ abaab $-t bemenetként. Kapunk $ baabb, abbaba, bbababab $-t; további megengedett átmenetek nem lehetségesek, ugyanakkor a befejezési feltétel sem teljesül. Van egy eredménytelen megálló. Tehát a $ babaa $ bemenet alkalmas a $ \mathfrak A $ számára, a $ baaba $ és $ abaab $ bemenetek pedig nem.
Az algoritmusok jelentősége.
A tudományban mindenütt találkozunk algoritmusokkal: egy probléma “általános” megoldásához algoritmusra van szükség. Az ember számok összeadásának képessége példa erre. Nem abban az értelemben, hogy előbb-utóbb megtalálja két tetszőleges szám összegét, hanem abban az értelemben, hogy rendelkezik egy módszerrel két tetszőleges, írásban megadott szám egyedi összeadására, azaz egy olyan összeadási algoritmussal, mint a jól ismert oszlopos összeadási módszer. “Általában” egy probléma megoldása úgy formalizálódik, mint egy algoritmikus probléma megoldása. Egy algoritmikus probléma különálló problémapéldányokból áll, és az összes problémapéldány megoldására egyetlen algoritmust kell találni. Ha nincs ilyen algoritmus, akkor azt mondjuk, hogy az algoritmikus probléma megoldhatatlan. Így egy adott típusú egyenletek numerikus megoldásának problémája és az automatikus fordítás problémája algoritmikus probléma. Problémapéldáik az adott típusú egyes egyenletek numerikus megoldása, illetve az egyes mondatok fordítása. További példák az algebrai egyenlőségek ellenőrzése az algebrában; a tételek levezethetőségének adott axiómákból való felismerésének algoritmikus problémája a matematikai logikában. (A matematikai logikában az algoritmus fogalma azért is fontos, mert ez szolgál a kalkulus kulcsfogalmának alapjául, amely a “bizonyítás” és a “bizonyítás” intuitív fogalmainak általánosítása és pontosabb formája .). Egy adott algoritmikus probléma megoldhatatlanságának megállapítása (pl. valamilyen logikai-matematikai nyelven megfogalmazott mondatok igazságának vagy bizonyíthatóságának megállapításának problémája) azért fontos, mert megmutatja, hogy a probléma konkrét problémapéldái elvileg csak az egyes problémapéldákra jellemző módszerekkel oldhatók meg.
Az algoritmus fogalmának tudományos jelentőségét már régóta felismerték. A legkorábbi idők óta az emberek konstruktív módszereket kerestek matematikai problémák megoldására. Ezeknek a törekvéseknek általában jót tett a megfelelő szimbolikus jelölések újbóli rendelkezésre állása. Ez a folyamat jelentősen hozzájárult a tudományos ismeretekhez, különösen azután, hogy világossá vált, hogy egyes problémák eleve megoldhatatlanok (a kör négyszögesítése stb.). Miután felismerték, hogy bizonyos problémák nem oldhatók meg közvetlen számításokkal, a 19. században megszületett a halmaz elméleti fogalma. Csak e fogalom gyors fejlődésének időszaka után (amely nem a mai értelemben vett konstruktív módszerek problémáit érintette), a 20. század közepén lehetett visszatérni a konstruktív problémákhoz, de ez már más szinten, az időközben kikristályosodott algoritmus fogalmával gazdagodva történt. Ez a fogalom képezi a matematika konstruktív irányzatának alapját.
Az “algoritmus” szó az “algoritmi” szóból származik, ez utóbbi a 9. századi arab matematikus, Al-Khwarizmi nevének latin átírása. Az “algoritmus” a középkor Európájában “a tizedes-pozíciós rendszer és a vele való számolás művészete” volt , mivel Al-Khwarizmi értekezésének latin fordítása (12. század) révén került be a pozíciós rendszer Európába.
Az algoritmikus folyamat felépítése.
Az algoritmikus folyamat a konstruktív objektumok diszkrét “lépésekkel” történő egymás utáni átalakításának folyamata , minden lépés az egyik konstruktív objektumnak egy másikkal való helyettesítéséből áll. Így, ha a $ \mathfrak A $ algoritmust alkalmazzuk a $ baaba $ szóra, akkor egymás után a $ baaba, abaaba, baabab $ stb. szavak következnek. Ha például az oszloponkénti kivonás algoritmusát alkalmazzuk a <307, 49 > számpárra, akkor egymás után a következő konstruktív objektumokat kapjuk:
$$ \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}$$
Megjegyezzük, hogy az egymást követő konstruktív objektumok sorozatában minden egyes egymást követő konstruktív objektumot teljes mértékben meghatároz (az adott algoritmus keretében) az azt közvetlenül megelőző konstruktív objektum. A szigorúbb megközelítésben azt is feltételezzük, hogy az átmenet bármely konstruktív objektumról az azt közvetlenül követőre kellően “elemi” – abban az értelemben, hogy az előzőből a közvetlenül követő objektumba történő egylépéses átalakulás lokális (nem a teljes konstruktív objektum alakul át, hanem csak annak algoritmus által korlátozott része; sőt, magát az átalakulást sem a teljes előző objektum határozza meg, hanem csak annak egy korlátozott része).
Ennek megfelelően nemcsak a lehetséges bemenetek és a lehetséges eredmények halmazával rendelkezünk, hanem a lehetséges köztes eredmények halmazával is, amelyek azt a munkaközeget képviselik, amelyben az algoritmikus folyamat fejlődik. A $ \mathfrak A $ tekintetében mindhárom halmaz egybeesik, de ez nem igaz az oszloponkénti kivonás algoritmusára – a lehetséges bemenetek számpárok, a lehetséges eredmények számok (mind a tizedes rendszerben), míg a lehetséges köztes eredmények “háromszintű” típusú rekordok
$$$ \begin{array}{r} p \\\\\\underline{- q } \\\ r \\\\end{array}$$
amelyben $ q $ a szám írott rekordja a tízes számrendszerben, $ r $ egy hasonló rekord vagy az üres szó, míg $ p $ egy szám írott rekordja a tízes számrendszerben, néhány számjegy fölött pontokkal. Rendszerint több (nem független) paramétert lehet megkülönböztetni, amelyek egy algoritmusra jellemzőek: 1) a lehetséges bemenetek halmaza; 2) a lehetséges eredmények halmaza; 3) a lehetséges köztes eredmények halmaza; 4) a kezdőszabály; 5) a közvetlen átmenet szabálya; 6) a befejezési szabály; és 7) az eredmény visszakeresésének szabálya.
Az algoritmus fogalmának formalizálása.
Az algoritmus fogalma általános formában olyan alapvető matematikai fogalom, amely nem definiálható egyszerűbb fogalmakkal. Szigorúan véve az algoritmus fogalmának formalizálása valójában némileg korlátozza azt. Minden ilyen formalizálásban pontos definíciót adnak valamilyen osztályra, amelyen belül az egyes paraméterek változhatnak. A különböző formalizációk az ilyen osztályok kiválasztásában különböznek egymástól. Mivel a paraméterek egyértelműen meghatároznak valamilyen algoritmust, a paramétertartományok kiválasztása meghatározza az algoritmusok valamilyen osztályát. Egy ilyen választás azonban csak akkor állíthatjuk, hogy az algoritmus intuitív fogalmának formalizációja, ha biztosak lehetünk abban, hogy bármely “intuitív” algoritmushoz létezik egy egyenértékű algoritmus a vizsgált választás által meghatározott algoritmusok osztályában. Ezt a követelményt minden egyes formalizációra vonatkozóan alapvető hipotézisként fogalmazzuk meg, amely a jelenlegi tudásszint mellett matematikailag nem bizonyítható.
Az első ilyen típusú formalizációkat E. L. Post
és A. M. Turingnak köszönhetjük , , akinek konstrukciói sok tekintetben megelőlegezték azokat az elképzeléseket, amelyeken a modern számítógépek alapulnak. Vannak A.A. Markov ,
(vö. Normál algoritmus) és A.N. Kolmogorov , , aki a megközelítést egy bizonyos típusú konstruktív topológiai komplexumokra alapozta, ami lehetővé teszi egy transzformáció “lokálisnak lenni” tulajdonságának pontosabb kifejezését. Mindegyik formalizációban az alaphipotézis kielégítő összhangban van a gyakorlattal. Egy másik érv e hipotézis mellett az a tény, hogy – mint bizonyítható – az effektív kiszámíthatóság valamennyi javasolt formális változata (az effektív kiszámíthatóság) ekvivalens.
Példaként tekintsük a Turing által javasolt formalizációt. Eredeti formájában ez valamilyen elméleti számítógép leírása volt, amely 1) egy végtelen szalagból állt, amelyet egymást követő cellákra osztottak, és minden egyes cella képes volt valamilyen szimbólumot tartalmazni a gép “szalagos ábécéjéből”; és 2) egy “véges vezérlésből”, amely minden időpillanatban valamilyen “állapotban” van (az állapotok adott véges listájából). A véges vezérlő képes a szalag mentén mozogni, cellánként egy-egy cellát, és megváltoztatni a cellák tartalmát, amelyeken áthalad. A véges vezérlő mozgását figyelő program alkotja az ilyen gépen végzett számítások algoritmusát (“Turing-algoritmus” ). Pontosabb és részletesebb leírásért lásd: Turing-gép. Itt a Turing-konstrukció modernizált kifejtését adjuk meg. Egy Turing-algoritmus meghatározásához megadjuk a) a $ B, D, C $ páronként elkülönülő betűkészleteket, amelyekben a $ D $-ban $ \lambda $ és a $ C $-ban $ \alpha $ és $ \omega $ megkülönböztetett betűk vannak; és b) a $ \langle p \xi , \eta Tq \rangle $ alakú párok halmaza, ahol $ p, q \in C $, $ \xi , \eta \in B \cup D $, míg $ T $ a három szimbólum $ -, 0, + $ egyike; ebben a halmazban (amelyet programnak nevezünk) nincs két olyan pár, amelynek első koordinátája megegyezik. A lehetséges bemenetek és a lehetséges kimenetek $ B $ feletti szavak, míg a lehetséges köztes eredmények $ B \cup D \cup C $ feletti szavak, amelyek legfeljebb egy betűt tartalmaznak $ C $-ból. A kezdő szabály az, hogy a kezdeti $ P $ szó $ \lambda \alpha P \lambda $ szóvá alakul. A befejező szabály az, hogy a $ \omega $-t tartalmazó köztes eredmény végleges. A kimenet kinyerésére vonatkozó szabály az, hogy a kimenet a végső köztes eredményben lévő betűsorozat, amely $ \omega $ után következik, és megelőzi az első olyan betűt, amely nem tartozik $ B $-hoz. Az átalakítási szabály, amely $ A $-t $ A ^ \prime $-vá alakítja, a következő. A $ \lambda $ betűt az $ A $ bal és jobb oldalára írjuk; az így keletkezett szóban a $ \epsilon p \xi $ alakú részt, ahol $ p \in C $, $ \epsilon \xi \in B \cup D $, a szabály szerint $ Q $ szóval helyettesítjük: Ha $ T $ – $, akkor $ Q = q \epsilon \eta $; ha $ T = 0 $, akkor $ Q = \epsilon q \eta $; ha $ T $ $ + $, akkor $ Q = \epsilon \eta q $. Az így kapott szó $ A ^ \prime $. Hivatkozásokért lásd , , , , , , , , ,
a Algoritmusok, elmélete.
A fent említett alaphipotézist általában Church-Turing-tézisnek vagy Turing-hipotézisnek nevezik. Ez a tézis azt állítja, hogy ami a hatékony folyamatról alkotott intuíciónk szerint hatékonyan kiszámítható, az egy Turing-gép, azaz egy formálisan definiált algoritmusfogalom által is kiszámítható. A Church-Turing-tézis természeténél fogva, hogy egy intuitív informális fogalmat azonosít egy formális, pontos definícióval, formálisan nem bizonyítható.
Sok formalizációról kiderült, hogy egyenértékű, és egyetlen formalizáció sem bizonyult szigorúan erősebbnek. A fent említett formalizációk mellett a következő hivatkozások a legelterjedtebbek nyugaton: Church formalizálása a számoknak és a kiszámítható függvényeknek lambda-terminusokkal, Kleene általános rekurzív sémái, valamint a J. C. Shepherdson és H. E. Sturgis által javasolt regisztergépmodell, amelyet S. A. Cook és R. A. Reckhow valósághűbb számítógépmodellé bővített. Markov és Kolmogorov változatai kevésbé ismertek. A teljesség kedvéért a Turing és Post eredeti hivatkozásait is megadjuk.
| 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 |