Probleme insolvabile algoritmic: Problema Stopului, problema ecuatiilor diofantice

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

In continuare vom oferi spre edificare doar citeva exemple, urmind ca prin studiul Complexitatii algoritmilor si a dificultatii problemelor sa se aprofundeze acest domeniu fascinant dar atit de usor de confundat (poti sa dai de aceste probleme chiar si din greseala !?) si care este pacat sa fie tratat intr-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 dintii si cel mai celebru exemplu de problema insolvabila. Demonstratia riguroasa a acestui fapt a fost data pentru prima data in 1936 de inventatorul calculatorului actual matematicianul englez Alan Mathison Turing. Odata existind aceasta demonstratie, multe din urmatoarele probleme insolvabile algoritmic s-au redus la aceasta. Implicatiile practice, teoretice si filozofice ale problemei Stopului sint foarte importante atit pentru informatica cit si pentru matematica. Astfel, doua consecinte strategice ale problemei Stopului sint: 1. nu poate exista un calculator oricit de puternic cu ajutorul caruia sa se poata decide asupra comportamentului viitor al oricarui alt calculator de pe glob; 2. nu poate sa existe in matematica o metoda generala de demonstrare inductiva-logica a propozitiilor matematice (se inchide in 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 intregi ale unui sistem de ecuatii diofantice.

Comentariu: sistemele de ecuatii diofantice sint sistemele de ecuatii algebrice de mai multe variabile cu coeficienti intregi si carora li se cauta solutii intregi. 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 (infirmindu-se in acest fel 'conjectura' lui Leonard Euler care in 1796 a presupus ca aceasta ecuatie diofantica nu are solutii intregi). 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: in practica este mult mai importanta problema croirii care cere sa se decupeze fara pierderi un set cit mai mare de forme date (croiuri) dintr-o bucata initiala de material oricit de mare. Este deasemenea demonstrat ca problema ramine insolvabila algoritmic chiar si atunci cind formele poligonale sint reduse la poliomine (un fel de 'mozaicuri') care se formeaza doar pe o retea rectangulara caroiata. Iata citeva exemple de multimi formate dintr-o singura poliomina si, alaturat, raspunsul la intrebarea daca cu ele se poate acoperi planul sau nu:

DA NU DA

Proiect: Fisa de lucru - operatii cu numere intregi Referat: Jocuri didactice matematica - lantul buclucas

Problema sirurilor lui Post. Se dau doua multimi egale de siruri finite de simboluri ce sint imperecheate 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 incit 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 sint 1.(101,010), 2.(010,10) si 3.(00,001). Observam ca sirurile pereche pot avea lungimi diferite (ca in perechile 2 si 3). In continuare, pentru a vedea cum se procedeaza, cele doua siruri pereche rezultante prin concatenare le vom scrie unul deasupra celuilalt sesizind cum avanseaza procesul de egalizare a lor. Punctele sint 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' intre cuvinte. Bazindu-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 cuvint oarecare A poate fi 'egal' cu un altul B.

Comentariu: de exemplu, fie urmatoarele cinci egalitati (cititi-le in 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 ? Intrucit se vede ca numarul total de A-uri plus W-uri si  M-uri nu se poate modifica prin nici o substitutie si intrucit 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 sint 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 intilnite mai ales sub numele de probleme nedecidabile sau probleme nerecursive, in enuntul lor cuvintul algoritm fiind inlocuit mai ales cu cuvintele metoda generala.

Studierea acestui domeniu a creat conditii pentru aparitia de noi directii de cercetare prin care se incearca explicarea rationamentelor matematice ba chiar se incearca descoperirea limitelor ratiunii umane in 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, in cele din urma si in esenta, rationamentele umane nu sint algoritmice, nici macar cele matematice. Dupa parera lui Penrose mintea umana nu poate fi asimilata cu un calculator ci este mai mult decit atit si nu vor putea exista vreodata calculatoare sau roboti mai inteligenti decit oamenii! In ultimul capitol oferim titlurile cartilor recent aparute ce trateaza despre acest fascinant subiect .