Cuprins introducere Ce şanse am să devin un bun programator ? Legile succesului durabil (Ghidul studentului îndărătnic) 6 Probleme de judecată 8

Probleme insolvabile algoritmic

Am introdus acest capitol special din două motive. Primul motiv, pentru a trezi interesul şi pasiunea pentru informatică celor care pot acum să vadă cît de deosebite sînt descoperirile şi rezultatele din acest domeniu. Al doilea motiv, pentru ai pune în gardă pe cei care, în entuziasmul lor exagerat, îşi închipuie că pot programa calculatorul să facă orice treabă sau să rezolve orice problemă. Aşa cum am văzut şi în capitolul ce tratează despre problemele dificile ale informaticii, enunţurile problemelor foarte dificile sau chiar insolvabile sînt foarte simple şi pot uşor constitui o capcană pentru necunoscători.

În continuare vom oferi spre edificare doar cîteva exemple, urmînd ca prin studiul Complexităţii algoritmilor şi a dificultăţii problemelor să se aprofundeze acest domeniu fascinant dar atît de uşor de confundat (poţi să dai de aceste probleme chiar şi din greşeală !?) şi care este păcat să fie tratat într-un mod superficial.

1. 
   Problema Stopului. Nu există un algoritm universal valabil prin care să se poată decide dacă execuţia oricărui algoritm se opreşte vreodată sau nu.
   

Comentariu: acesta este cel dintîi şi cel mai celebru exemplu de problemă insolvabilă. Demonstraţia riguroasă a acestui fapt a fost dată pentru prima dată în 1936 de inventatorul calculatorului actual matematicianul englez Alan Mathison Turing. Odată existînd această demonstraţie, multe din următoarele probleme insolvabile algoritmic s-au redus la aceasta. Implicaţiile practice, teoretice şi filozofice ale problemei Stopului sînt foarte importante atît pentru informatică cît şi pentru matematică. Astfel, două consecinţe strategice ale problemei Stopului sînt: 1. nu poate exista un calculator oricît de puternic cu ajutorul căruia să se poată decide asupra comportamentului viitor al oricărui alt calculator de pe glob; 2. nu poate să existe în matematică o metodă generală de demonstrare inductivă-logică a propoziţiilor matematice (se închide în acest fel o mai veche căutare a matematicienilor şi logicienilor cunoscută sub numele de Entscheidungs Problem sau Problema deciziei).

2. 
   Problema ecuaţiilor diofantice. Nu există o metodă generală (un algoritm) de aflare a soluţiilor întregi ale unui sistem de ecuaţii diofantice.
   

Comentariu: sistemele de ecuaţii diofantice sînt sistemele de ecuaţii algebrice de mai multe variabile cu coeficienţi întregi şi cărora li se caută soluţii întregi. De exemplu, a fost nevoie de ajutorul calculatorului pentru a se descoperi cea mai mică soluţie a ecuaţiei diofantice p⁴+q⁴+r⁴=s⁴ şi 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 că această ecuaţie diofantică nu are soluţii întregi). Această problemă ce cere o metodă generală de rezolvare a ecuaţiilor diofantice este cunoscută sub denumirea de Problema a 10-a a lui Hilbert.

3. 
   Problema acoperirii planului (Problema pavajului sau Problema croirii). Fiind dată o mulţime de forme poligonale, nu există o metodă generală (un algoritm) care să decidă dacă cu aceste forme este posibilă acoperirea completă a planului (fără suprapuneri şi goluri).
   

Comentariu: în practică este mult mai importantă problema croirii care cere să se decupeze fără pierderi un set cît mai mare de forme date (croiuri) dintr-o bucată iniţială de material oricît de mare. Este deasemenea demonstrat că problema rămîne insolvabilă algoritmic chiar şi atunci cînd formele poligonale sînt reduse la poliomine (un fel de "mozaicuri") care se formează doar pe o reţea rectangulară caroiată. Iată cîteva exemple de mulţimi formate dintr-o singură poliomină şi, alăturat, răspunsul la întrebarea dacă cu ele se poate acoperi planul sau nu:

DA NU DA

4. 
   Problema şirurilor lui Post. Se dau două mulţimi egale de şiruri finite de simboluri ce sînt împerecheate astfel: un şir dintr-o mulţime cu şirul corespunzător din a doua mulţime. Nu există un algoritm general prin care să se decidă dacă există o ordine de concatenare a şirurilor (simultan din cele două mulţimi) astfel încît cele două şiruri lungi pereche rezultate să fie identice.
   

Comentariu: de exemplu, fie A={ 101, 010, 00 } şi B={ 010, 10, 001 } cele două mulţimi de şiruri de simboluri (pentru uşurinţă au fost alese simbolurile binare 1 şi 0). Perechile corespunzătoare de şiruri sînt 1.(101,010), 2.(010,10) şi 3.(00,001). Observăm că şirurile pereche pot avea lungimi diferite (ca în perechile 2 şi 3). În continuare, pentru a vedea cum se procedează, cele două şiruri pereche rezultante prin concatenare le vom scrie unul deasupra celuilalt sesizînd cum avansează procesul de egalizare a lor. Punctele sînt intercalate doar pentru a evidenţia perechile, ele nu contribuie la egalitate, iar comentariile ne aparţin:

00.	Concatenarea poate începe doar cu		00.101.	Obligatoriu urmează perechea 1-a
001.	perechea a 3-a,00 de "sus"  001 de "jos"		001.010.	singura care începe cu 1 "sus".
00.101.00.		Dacă am continua cu perechea	00.101.010		… nu s-ar obţine rezultatul final
001.010.001.		a 3-a …	001.010.10		oferit de perechea 2-a !

5. 
   Problema cuvintelor "egale". Se dă un anumit număr de "egalităţi" între cuvinte. Bazîndu-ne pe aceste "egalităţi" se pot obţine unele noi substituind apariţiile cuvintelor dintr-o parte a egalului cu cele din cealaltă parte. Nu există un algoritm general de a decide dacă un cuvînt oarecare A poate fi "egal" cu un altul B.
   

Comentariu: de exemplu, fie următoarele cinci egalităţi (citiţi-le în limba engleză) EAT=AT, ATE=A, LATER=LOW, PAN=PILLOW şi CARP=ME. Este CATERPILLAR egal cu MAN ? Iată şirul egalităţilor iterate care ne poate oferi răspunsul: CATERPILLAR = CARPILLAR =CARPILLATER =CARPILLOW= CARPAN= MEAN= MEATEN= MATEN= MAN.

Dar de la CARPET putem ajunge la MEAT ? Întrucît se vede că numărul total de A-uri plus W-uri şi M-uri nu se poate modifica prin nici o substituţie şi întrucît CARPET are un A (adică numărul asociat este 1) iar MEAT are un A şi un M (deci 2), rezultă că această egalitate nu este permisă.

Mai mult, se ştie că există liste particulare de cuvinte pentru care nu poate exista un algoritm ce decide dacă două cuvinte sînt egale sau nu. Iată o astfel de listă de şapte egalităţi: AH=HA, OH=HO, AT=TA, OT=TO, TAI=IT, HOI=IH şi THAT=ITHT.

Numărul problemelor cunoscute ca fiind insolvabile algoritmic este destul de mare. Cele mai multe probleme provin din matematică, subdomeniul matematicii care studiază aceste probleme se numeşte Matematica nerecursivă. De aceea ele pot fi întîlnite mai ales sub numele de probleme nedecidabile sau probleme nerecursive, în enunţul lor cuvîntul algoritm fiind înlocuit mai ales cu cuvintele metodă generală.

Studierea acestui domeniu a creat condiţii pentru apariţia de noi direcţii de cercetare prin care se încearcă explicarea raţionamentelor matematice ba chiar se încearcă descoperirea limitelor raţiunii umane în general. Unii oameni de ştiinţă contemporani, cum este celebrul matematician-fizician englez Roger Penrose, depun eforturi mari pentru a oferi o demonstraţie matematică riguroasă pentru ipoteza că, în cele din urmă şi în esenţă, raţionamentele umane nu sînt algoritmice, nici măcar cele matematice. După părera lui Penrose mintea umană nu poate fi asimilată cu un calculator ci este mai mult decît atît şi nu vor putea exista vreodată calculatoare sau roboţi mai inteligenţi decît oamenii! În ultimul capitol oferim titlurile cărţilor recent apărute ce tratează despre acest fascinant subiect .