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 trateaza 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 252c21c 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 .