Probleme insolvabile algoritmic

Probleme insolvabile algoritmic

Am introdus acest capitol special din doua motive. Primul motiv, pentru a trezi interesul si pasiunea pentru informatica celor care pot acum sa vada cît de deosebite sînt descoperirile si rezultatele din acest domeniu. Al doilea motiv, pentru ai pune în garda pe cei care, în entuziasmul lor exagerat, îsi închipuie ca pot programa calculatorul sa faca orice treaba sau sa rezolve orice problema. Asa cum am vazut si în capitolul ce tra 10310j921k teaza despre problemele dificile ale informaticii, enunturile problemelor foarte dificile sau chiar insolvabile sînt foarte simple si pot usor constitui o capcana pentru necunoscatori.

În continuare vom oferi spre edificare doar cîteva exemple, urmînd ca prin studiul Complexitatii algoritmilor si a dificultatii problemelor sa se aprofundeze acest domeniu fascinant dar atît de usor de confundat (poti sa dai de aceste probleme chiar si din greseala !?) si care este pacat sa fie tratat într-un mod superficial.

Problema Stopului. Nu exista un algoritm universal valabil prin care sa se poata decide daca executia oricarui algoritm se opreste vreodata sau nu.

Comentariu: acesta este cel dintîi si cel mai celebru exemplu de problema insolvabila. Demonstratia riguroasa a acestui fapt a fost data pentru prima data în 1936 de inventatorul calculatorului actual matematicianul englez Alan Mathison Turing. Odata existînd aceasta demonstratie, multe din urmatoarele probleme insolvabile algoritmic s-au redus la aceasta. Implicatiile practice, teoretice si filozofice ale problemei Stopului sînt foarte importante atît pentru informatica cît si pentru matematica. Astfel, doua consecinte strategice ale problemei Stopului sînt: 1. nu poate exista un calculator oricît de puternic cu ajutorul caruia sa se poata decide asupra comportamentului viitor al oricarui alt calculator de pe glob; 2. nu poate sa existe în matematica o metoda generala de demonstrare inductiva-logica a propozitiilor matematice (se închide în acest fel o mai veche cautare a matematicienilor si logicienilor cunoscuta sub numele de Entscheidungs Problem sau Problema deciziei).

Problema ecuatiilor diofantice. Nu exista o metoda generala (un algoritm) de aflare a solutiilor întregi ale unui sistem de ecuatii diofantice.

Comentariu: sistemele de ecuatii diofantice sînt sistemele de ecuatii algebrice de mai multe variabile cu coeficienti întregi si carora li se cauta solutii întregi. De exemplu, a fost nevoie de ajutorul calculatorului pentru a se descoperi cea mai mica solutie a ecuatiei diofantice p⁴+q⁴+r⁴=s⁴ si care este cvadrupletul p=95600, q=217519, r=414560, s=422461 (infirmîndu-se în acest fel "conjectura" lui Leonard Euler care în 1796 a presupus ca aceasta ecuatie diofantica nu are solutii întregi). Aceasta problema ce cere o metoda generala de rezolvare a ecuatiilor diofantice este cunoscuta sub denumirea de Problema a 10-a a lui Hilbert.

Problema acoperirii planului (Problema pavajului sau Problema croirii). Fiind data o multime de forme poligonale, nu exista o metoda generala (un algoritm) care sa decida daca cu aceste forme este posibila acoperirea completa a planului (fara suprapuneri si goluri).

Comentariu: în practica este mult mai importanta problema croirii care cere sa se decupeze fara pierderi un set cît mai mare de forme date (croiuri) dintr-o bucata initiala de material oricît de mare. Este deasemenea demonstrat ca problema ramîne insolvabila algoritmic chiar si atunci cînd formele poligonale sînt reduse la poliomine (un fel de "mozaicuri") care se formeaza doar pe o retea rectangulara caroiata. Iata cîteva exemple de multimi formate dintr-o singura poliomina si, alaturat, raspunsul la întrebarea daca cu ele se poate acoperi planul sau nu:

DA    NU DA

Problema sirurilor lui Post. Se dau doua multimi egale de siruri finite de simboluri ce sînt împerecheate astfel: un sir dintr-o multime cu sirul corespunzator din a doua multime. Nu exista un algoritm general prin care sa se decida daca exista o ordine de concatenare a sirurilor (simultan din cele doua multimi) astfel încît cele doua siruri lungi pereche rezultate sa fie identice.

Comentariu: de exemplu, fie A= si B= cele doua multimi de siruri de simboluri (pentru usurinta au fost alese simbolurile binare 1 si 0). Perechile corespunzatoare de siruri sînt 1.(101,010), 2.(010,10) si 3.(00,001). Observam ca sirurile pereche pot avea lungimi diferite (ca în perechile 2 si 3). În continuare, pentru a vedea cum se procedeaza, cele doua siruri pereche rezultante prin concatenare le vom scrie unul deasupra celuilalt sesizînd cum avanseaza procesul de egalizare a lor. Punctele sînt intercalate doar pentru a evidentia perechile, ele nu contribuie la egalitate, iar comentariile ne apartin:

Problema cuvintelor "egale". Se da un anumit numar de "egalitati" între cuvinte. Bazîndu-ne pe aceste "egalitati" se pot obtine unele noi substituind aparitiile cuvintelor dintr-o parte a egalului cu cele din cealalta parte. Nu exista un algoritm general de a decide daca un cuvînt oarecare A poate fi "egal" cu un altul B.

Comentariu: de exemplu, fie urmatoarele cinci egalitati (cititi-le în limba engleza) EAT=AT, ATE=A, LATER=LOW, PAN=PILLOW si CARP=ME. Este CATERPILLAR egal cu MAN ? Iata sirul egalitatilor iterate care ne poate oferi raspunsul: CATERPILLAR = CARPILLAR =CARPILLATER =CARPILLOW= CARPAN= MEAN= MEATEN= MATEN= MAN.

Dar de la CARPET putem ajunge la MEAT ? Întrucît se vede ca numarul total de A-uri plus W-uri si M-uri nu se poate modifica prin nici o substitutie si întrucît CARPET are un A (adica numarul asociat este 1) iar MEAT are un A si un M (deci 2), rezulta ca aceasta egalitate nu este permisa.

Mai mult, se stie ca exista liste particulare de cuvinte pentru care nu poate exista un algoritm ce decide daca doua cuvinte sînt egale sau nu. Iata o astfel de lista de sapte egalitati: AH=HA, OH=HO, AT=TA, OT=TO, TAI=IT, HOI=IH si THAT=ITHT.

Numarul problemelor cunoscute ca fiind insolvabile algoritmic este destul de mare. Cele mai multe probleme provin din matematica, subdomeniul matematicii care studiaza aceste probleme se numeste Matematica nerecursiva. De aceea ele pot fi întîlnite mai ales sub numele de probleme nedecidabile sau probleme nerecursive, în enuntul lor cuvîntul algoritm fiind înlocuit mai ales cu cuvintele metoda generala.

Studierea acestui domeniu a creat conditii pentru aparitia de noi directii de cercetare prin care se încearca explicarea rationamentelor matematice ba chiar se încearca descoperirea limitelor ratiunii umane în general. Unii oameni de stiinta contemporani, cum este celebrul matematician-fizician englez Roger Penrose, depun eforturi mari pentru a oferi o demonstratie matematica riguroasa pentru ipoteza ca, în cele din urma si în esenta, rationamentele umane nu sînt algoritmice, nici macar cele matematice. Dupa parera lui Penrose mintea umana nu poate fi asimilata cu un calculator ci este mai mult decît atît si nu vor putea exista vreodata calculatoare sau roboti mai inteligenti decît oamenii! În ultimul capitol oferim titlurile cartilor recent aparute ce trateaza despre acest fascinant subiect .