Instrucțiuni detaliate care definesc un proces de calcul (despre care se spune atunci că este algoritmic), care începe cu o intrare arbitrară (dintr-un anumit număr de intrări care sunt posibile pentru algoritmul dat) și cu instrucțiuni menite să obțină un rezultat (sau ieșire) care este determinat în totalitate de intrarea respectivă. De exemplu, regulile predate în școlile primare pentru adunarea, scăderea, înmulțirea și împărțirea pe coloane sunt algoritmi; în acești algoritmi, rezultatele posibile sunt numere întregi nenulegative scrise în sistemul zecimal, în timp ce intrările posibile sunt perechi ordonate de astfel de numere. În general, nu se presupune că rezultatul este obținut în mod necesar: procesul de aplicare a unui algoritm la o intrare posibilă (adică un proces algoritmic care se desfășoară pornind de la această intrare) se poate încheia, de asemenea, fără a se obține un rezultat (în acest caz, există o oprire fără rezultat) sau poate să nu se încheie deloc. Dacă procesul se termină (nu se termină), atunci se spune că intrarea este potrivită (nu este potrivită) pentru algoritmul în cauză.
Un rezultat important în acest domeniu este indecidabilitatea așa-numitei probleme de oprire. Este posibil să se construiască un algoritm $ \alpha $ astfel încât să nu existe un algoritm care să decidă dacă o intrare arbitrară care este posibilă pentru $ \alpha $ este sau nu potrivită și pentru $ \alpha $. În particular, se poate găsi un astfel de algoritm $ \alpha $pentru care setul intrărilor sale posibile este setul numerelor naturale.
Noțiunea de algoritm este unul dintre conceptele centrale în matematica modernă, în special în domeniul calculelor. Un exemplu este dat mai jos. Găsirea soluției numerice a ecuațiilor de un anumit tip echivalează cu construirea unui algoritm care convertește o ecuație arbitrară de acest tip și un număr rațional pozitiv arbitrar $ \epsilon $într-un număr (sau un set de numere) care diferă de rădăcina (rădăcinile) acestei ecuații cu mai puțin de $ \epsilon $. Cu toate acestea, termenul „proces de calcul” , așa cum este folosit în contextul unui algoritm, nu trebuie înțeles ca însemnând doar calcule numerice: chiar și în algebra elementară se folosesc calcule cu litere. Calculele aritmetice standard implică unele simboluri care nu sunt numere (paranteze, semne de egalitate, simboluri pentru operatorii aritmetici). Prin urmare, este oportun să se ia în considerare algoritmii care implică simboluri arbitrare și obiecte compuse din simboluri. Cel mai simplu exemplu de astfel de obiect este o secvență liniară de simboluri care formează un cuvânt. De asemenea, este posibil să se ia în considerare obiecte „neliniare” – matrici algebrice, arbori de derivare a unui limbaj formal și grafuri generale. Intuitiv, cea mai mică cerință privind intrările și rezultatele algoritmilor este ca acestea să fie obiecte constructive (cf. Obiect constructiv). Astfel, conceptul de algoritm este foarte general. Se poate vorbi de un algoritm de traducere dintr-un limbaj în altul, de un algoritm al unui controlor de trafic aerian (care prelucrează informații privind mișcările aeronavelor în conformitate cu reguli fixe) și de alte exemple de procese de control descrise algoritmic. În consecință, conceptul de algoritm este una dintre ideile centrale în cibernetică și informatică.
Exemplu de algoritm.
Să se considere că intrările posibile și rezultatele posibile sunt toate cuvintele posibile din alfabetul $ \{ a, b \} $. Tranziția de la un cuvânt $ X $ la un cuvânt $ Y $ este „permisă” în următoarele două cazuri (unde $ P $ desemnează un cuvânt arbitrar): 1) $ X $ este de forma $ aP $, iar $ Y $ este de forma $ Pb $; sau 2) $ X $ este de forma $ baP $, în timp ce $ Y $ este de forma $ Paba $. Instrucțiunile se formulează astfel: 1) $ X $ este de forma $ aP $, iar $ Y $ este de forma $ Paba $: „desemnând un cuvânt ca intrare, se execută tranzițiile permise până când se obține un cuvânt de forma aaP; apoi se oprește și se lasă cuvântul P ca rezultat” . Aceste instrucțiuni constituie un algoritm, care va fi notat cu $ \mathfrak A $. Să luăm cuvântul $ babaa $ca intrare. După o tranziție se obține $ baaaba $; după a doua, se obține $ aabaaba $. Aici algoritmul se oprește cu $ baaba $ ca rezultat. Se consideră o altă intrare $ baaba $. Se obțin, în succesiune, $ abaaba, baababa, baababa, abababa, babababa, babababa, babababa , . . . . $. Se poate demonstra că acest proces nu se va termina niciodată (adică niciunul dintre cuvintele generate nu va începe vreodată cu $ aa $). Luați acum $ abaab $ca intrare. Se obține $ baabb, abbaba, bbabab $; nu mai sunt posibile alte tranziții admisibile și, în același timp, condiția de terminare nu este îndeplinită. Se are o oprire fără rezultat. Astfel, intrarea $ babaa $ este potrivită pentru $ \mathfrak A $, iar intrările $ baaba $și $ abaab $nu sunt.
Semnificația algoritmilor.
În știință, algoritmii se întâlnesc peste tot: o soluție „generală” a unei probleme necesită un algoritm. Capacitatea omului de a aduna numere este un exemplu în acest sens. Nu în sensul că el poate găsi, mai devreme sau mai târziu, suma oricăror două numere, ci mai degrabă în sensul că el posedă o metodă pentru adunarea unică a oricăror două numere date în scris, adică un algoritm de adunare, cum ar fi binecunoscuta metodă de adunare pe coloane. „În general” rezolvarea unei probleme este formalizată ca rezolvarea unei probleme algoritmice. O problemă algoritmică este formată din cazuri de probleme separate, iar pentru rezolvarea tuturor acestora trebuie găsit un singur algoritm. Dacă nu există un astfel de algoritm, se spune că problema algoritmică este nesoluționabilă. Astfel, problema rezolvării numerice a ecuațiilor de un anumit tip și problema traducerii automate sunt probleme algoritmice. Instanțele problemelor lor sunt, respectiv, găsirea soluției numerice a ecuațiilor individuale de tipul dat și traducerea frazelor individuale. Alte exemple sunt verificarea egalităților algebrice în algebră; problema algoritmică de recunoaștere a deductibilității propozițiilor din axiome date în logica matematică. (În logica matematică, conceptul de algoritm este, de asemenea, important, deoarece servește ca bază a conceptului-cheie de calcul, care este o generalizare și o formă mai precisă a conceptelor intuitive de „dovadă” și „demonstrație” .) Stabilirea nerezolvabilității unei probleme algoritmice date (de exemplu, problema stabilirii adevărului sau demonstrabilității propozițiilor într-un anumit limbaj logico-matematic) este importantă, deoarece arată că, în principiu, instanțele specifice ale acelei probleme pot fi rezolvate numai prin metode care sunt specifice fiecărei instanțe individuale a problemei.
Importanța științifică a conceptului de algoritm a fost recunoscută de mult timp. Încă din cele mai vechi timpuri, oamenii au căutat metode constructive pentru a rezolva probleme matematice. Astfel de eforturi au beneficiat, de obicei, de noua disponibilitate a unor notații simbolice adecvate. Acest proces a adus o contribuție semnificativă la cunoașterea științifică, mai ales după ce a devenit clar că unele probleme sunt în mod inerent nesoluționabile (pătratul cercului etc.). După ce a fost recunoscut faptul că anumite probleme nu pot fi rezolvate prin calcule directe, în secolul al XIX-lea a luat naștere conceptul teoretic de ansamblu. Abia după o perioadă de dezvoltare rapidă a acestui concept (care nu a implicat probleme de metode constructive în sensul lor modern), a fost posibil ca la mijlocul secolului al XX-lea să se revină la problemele constructive, dar acest lucru s-a făcut la un alt nivel, îmbogățit de conceptul de algoritm care s-a cristalizat între timp. Acest concept stă la baza curentului constructiv în matematică.
Cuvântul „algoritm” provine din cuvântul „algoritmi” , acesta din urmă fiind transliterarea în latină a numelui matematicianului arab din secolul al IX-lea Al-Khwarizmi. Un „algoritm” în Europa Evului Mediu era „sistemul pozițional zecimal și arta de a calcula cu el” , deoarece prin traducerea în latină (secolul al XII-lea) a tratatului lui Al-Khwarizmi a fost introdus în Europa sistemul pozițional.
Structura unui proces algoritmic.
Un proces algoritmic este un proces de conversie consecutivă a obiectelor constructive prin „pași” discreți , fiecare pas constând în înlocuirea unui obiect constructiv cu un altul. Astfel, la aplicarea algoritmului $ \mathfrak A $ la cuvântul $ baaba $, urmează, succesiv, cuvintele $ baaba, abaaba, baabab $, etc. Dacă se aplică, să zicem, algoritmul de scădere în coloană la perechea de numere <307, 49 >, atunci se obțin, succesiv, următoarele obiecte constructive:
$ $$ \begin{array}{rrrr}307 &3 \dot{0} 7 &\dot{3} \dot{0} 7 &\dot{3} \\dot{0} 7 \\\\\linesubliniază{- 49 } &\underline{- 49} & Subliniere{- 49} &\underline{- 49} \\{} & 8 &58 &258 \\end{array}$$
Se va observa că, într-o serie de obiecte constructive succesive, fiecare obiect constructiv succesiv este pe deplin determinat (în cadrul algoritmului dat) de obiectul constructiv care îl precede imediat. În abordarea mai riguroasă, se presupune, de asemenea, că tranziția de la orice obiect constructiv la cel imediat următor este suficient de „elementară” – în sensul că transformarea într-un singur pas a obiectului precedent în obiectul imediat următor este locală (nu întregul obiect constructiv este transformat, ci doar partea sa limitată de algoritm; mai mult, această transformare însăși nu este determinată de întregul obiect precedent, ci doar de o parte limitată a acestuia).
În consecință, se are nu numai un set de intrări posibile și un set de rezultate posibile, ci și un set de rezultate intermediare posibile, reprezentând mediul de lucru în care evoluează procesul algoritmic. În ceea ce privește $ \mathfrak A $, toate aceste trei seturi coincid, dar acest lucru nu este valabil și în cazul algoritmului de scădere în coloană – intrările posibile sunt perechi de numere, rezultatele posibile sunt numere (toate în sistem zecimal), în timp ce rezultatele intermediare posibile sunt înregistrări „cu trei etaje” de tipul
$$$ \begin{array}{r} p \\\\\underline{- q } \\ r \\end{array}$$$
unde $ q $ este înregistrarea scrisă a numărului în sistemul zecimal, $ r $ este o înregistrare similară sau cuvântul gol, în timp ce $ p $ este înregistrarea scrisă a unui număr în sistemul zecimal, cu puncte peste unele dintre cifre. De regulă, se pot distinge mai mulți parametri (nu independenți) caracteristici unui algoritm: 1) setul de intrări posibile; 2) setul de rezultate posibile; 3) setul de rezultate intermediare posibile; 4) regula de pornire; 5) regula de tranziție directă; 6) regula de terminare; și 7) regula de recuperare a rezultatului.
Formalizarea conceptului de algoritm.
Noțiunea de algoritm, în forma sa generală, este un concept matematic fundamental care nu poate fi definit în termeni de concepte mai simple. Strict vorbind, formalizările conceptului de algoritm îl restrâng de fapt într-o oarecare măsură. În fiecare astfel de formalizare este dată o definiție exactă a unei clase în cadrul căreia fiecare dintre parametri poate varia. Diferitele formalizări diferă între ele prin selectarea unor astfel de clase. Deoarece parametrii definesc fără ambiguitate un anumit algoritm, o alegere a domeniilor de parametri determină o anumită clasă de algoritmi. Cu toate acestea, o astfel de alegere poate pretinde că este o formalizare a conceptului intuitiv de algoritm, numai dacă se poate fi sigur că pentru orice algoritm „intuitiv” există un algoritm echivalent în clasa de algoritmi definită de alegerea luată în considerare. Această cerință este formulată pentru fiecare formalizare ca o ipoteză fundamentală, care, în stadiul actual al cunoștințelor, nu poate fi demonstrată matematic.
Primele formalizări de acest tip se datorează lui E.L. Post
și lui A.M. Turing , , ale cărui construcții au anticipat în multe privințe ideile pe care se bazează calculatoarele moderne. Există, de asemenea, versiuni formulate de A.A. Markov ,
(cf. Algoritmul normal) și de A.N. Kolmogorov , , care a bazat abordarea pe complexe topologice constructive de un anumit tip, ceea ce face posibilă exprimarea mai precisă a proprietății de „a fi local” a unei transformări. În fiecare dintre aceste formalizări, ipoteza fundamentală este în acord satisfăcător cu practica. Un alt argument în favoarea acestei ipoteze este faptul că, după cum se poate demonstra, toate versiunile formale (ale calculabilității efective) care au fost propuse sunt echivalente.
Ca exemplu, să considerăm formalizarea propusă de Turing. În forma sa originală, aceasta era o descriere a unui anumit calculator teoretic constând din 1) o bandă infinită, împărțită în celule consecutive, fiecare celulă fiind capabilă să conțină un anumit simbol din „alfabetul benzii” mașinii; și 2) o „comandă finită”, care la fiecare moment de timp se află într-o anumită „stare” (dintr-o listă finită dată de stări). Comanda finită se poate deplasa de-a lungul benzii, câte o celulă la un moment dat, și poate modifica conținutul celulelor pe lângă care trece. Un program care monitorizează mișcarea controlului finit constituie algoritmul pentru calculele efectuate pe o astfel de mașină (un „algoritm Turing” ). Pentru o descriere mai exactă și mai detaliată, a se vedea mașina Turing. Aici este prezentată o expunere modernizată a construcției lui Turing. Pentru a defini un algoritm Turing, se specifică a) alfabete disjuncte pe perechi $ B, D, C $, cu o literă distinctă $ \lambda $în $ D $și literele distincte $ \alpha $și $ \omega $în $ C $; și b) un set de perechi de forma $ \langle p \xi , \eta Tq \rangle $în care $ p, q \în C $, $ \xi , \eta \în B \cup D $, în timp ce $ T $este unul dintre cele trei simboluri $ -, 0, + $; în acest set (care se numește program) nu există două perechi cu aceeași primă coordonată. Posibilele intrări și posibilele ieșiri sunt cuvinte peste $ B $, în timp ce posibilele rezultate intermediare sunt cuvinte peste $ B \cup D \cup C $care nu conțin mai mult de o literă din $ C $. Regula de pornire este că cuvântul inițial $ P $ este convertit în cuvântul $ \lambda \alpha P \lambda $. Regula de terminare este că un rezultat intermediar care conține $ \omega $ este final. Regula de regăsire a ieșirii este aceea că ieșirea este secvența de litere din rezultatul intermediar final care urmează după $ \omega $și precede prima literă care nu aparține lui $ B $. Regula de transformare care convertește $ A $în $ A ^ \prime $este după cum urmează. Litera $ \lambda $ se scrie la stânga și la dreapta lui $ A $; în cuvântul astfel format, partea de forma $ \epsilon p \xi $, unde $ p \în C $, $ \epsilon \xi \în B \cup D $, este înlocuită cu un cuvânt $ Q $ în conformitate cu regula: se caută în program o pereche cu primul termen $ p \xi $; fie al doilea termen al acestei perechi $ \eta Tq $; dacă $ T $ este $ – $, $ Q = q \epsilon \eta $; dacă $ T = 0 $, $ Q = \epsilon q \eta $; dacă $ T $ este $ + $, $ Q = \epsilon \eta q $. Cuvântul produs de acest schimb este $ A ^ \prime $. Pentru referințe, vezi , , , , , , ,
de Algoritmi, teoria algoritmilor.
Ipoteza fundamentală menționată mai sus este numită de obicei teza Church-Turing sau ipoteza lui Turing. Această teză afirmă că ceea ce poate fi calculat în mod eficient, în conformitate cu intuiția cuiva despre ceea ce constituie un proces eficient, poate fi calculat și de o mașină Turing, adică de o noțiune definită formal de algoritm. Prin însăși natura sa de a identifica o noțiune intuitivă informală cu o definiție formală precisă, teza Church-Turing nu poate fi demonstrată formal.
Multe formalizări s-au dovedit a fi echivalente și nicio formalizare nu s-a dovedit a fi strict mai puternică. În afară de formalizările menționate mai sus, următoarele referințe sunt cele mai standard în Occident: Formalizarea lui Church a numerelor și a funcțiilor calculabile prin termeni lambda, schemele recursive generale ale lui Kleene și modelul mașinii cu registre propus de J.C. Shepherdson și H.E. Sturgis, care a fost extins într-un model de calculator mai realist de către S.A. Cook și R.A. Reckhow. Versiunile lui Markov și Kolmogorov sunt mai puțin cunoscute. Pentru a fi complete sunt date și referințele originale ale lui Turing și 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) 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 |
.