Există două aspecte despre matematică care sunt adesea trecute cu vederea: în primul rând, unele probleme sunt pur și simplu imposibil de rezolvat. Nu este vorba că nu suntem destul de inteligenți sau că folosim metoda greșită; întrebarea, conjectura sau conceptul nu vor fi niciodată rezolvate de nimeni, niciodată.
În al doilea rând, inspirația pentru idei matematice de înalt nivel poate veni uneori din cele mai neașteptate locuri.
Misterul despre Super Mario Bros
Un exemplu relevant este un articol recent referitor la… Super Mario Bros.
„Din jocurile Mario 2D lansate de la New Super Mario Bros., am demonstrat că toate, cu excepția Super Mario Wonder, sunt indecidabile”, raportează articolul, redactat de o echipă de cercetători de la Grupul de Dificultate din cadrul Laboratorului de Științe Computerizate și Inteligență Artificială al MIT.
Chiar și pentru Super Mario Wonder, „există indicii care sugerează că ar putea fi, bazat pe prezența evenimentelor și a Goombas-urilor care apar infinit”, adaugă ei, „dar jocul este încă foarte nou, și sunt necesare mai multe cercetări pentru a înțelege suficient de bine mecanicile jocului pentru a face alte afirmații despre indecidabilitate”.
Ce înseamnă asta în practică? O problemă indecidabilă, practic, este ceea ce sună: o întrebare pentru care este imposibil să găsești un răspuns corect de tipul da sau nu. În acest caz, problema este una pe care, ca jucător, ai spera să fie mai simplă – este, pur și simplu, „Poate fi jocul terminat?”
„Nu se poate obține ceva mai dificil decât asta”, a declarat Erik Demaine, profesor de informatică la MIT și unul dintre autorii articolului, pentru New Scientist.
„Poți ajunge la final? Nu există niciun algoritm care să poată răspunde la această întrebare într-un timp finit”.
Știința din spate
Acum, a dovedi ceva de genul acesta nu este o sarcină ușoară – la urma urmei, simpla joacă a jocului la nesfârșit, deși ar fi o utilizare amuzantă a unui grant de cercetare, este evident exclusă. Așadar, echipa a folosit o tehnică deja utilizată cu un deceniu în urmă de studentul absolvent de la MIT, Linus Hamilton, pentru jocul Braid.
„Ideea centrală a fost să reprezinte valoarea fiecărui contor dintr-un nivel Braid prin numărul de inamici care ocupă o anumită locație în nivel”, explică articolul, „exploatând faptul că acest număr poate fi arbitrar de mare chiar și într-un nivel de dimensiuni limitate”.
În limbaj formal, echipa a creat o mașină de contorizare: o mașină teoretică ce modelează modul în care funcționează un computer prin manipularea unui set de „contoare”. Sunt foarte simple – un contor în Super Mario Bros. era echipat doar cu instrucțiunile „sus”, „jos” și „sari”, nimic mai mult – dar incredibil de utile, putând reduce problema Goombas-urilor potențial infinite la ceva mult mai ușor: problema opririi.
Ce înseamnă asta? Ei bine, pornești un program de calculator și apeși „start” – se va termina vreodată? Sau va continua să ruleze pentru totdeauna? Poate suna ca o întrebare banală, dar aceasta este problema opririi – un exemplu clasic de problemă indecidabilă. Dacă un joc poate fi redus la problema opririi – așa cum poate fi Braid și atât de multe dintre jocurile Super Mario Bros. – atunci și acesta este indecidabil.
„Ideea este că vei putea rezolva acest nivel Mario doar dacă această anumită calculare se va termina, și știm că nu există nicio modalitate de a determina asta”, a spus Demaine pentru New Scientist, „așa că nu există nicio modalitate de a determina dacă poți rezolva nivelul.”
Cu alte cuvinte: data viitoare când cineva spune că îți pierzi timpul jucând jocuri video, nu-ți face griji – poți să-i informezi că, de fapt, rezolvi o problemă indecidabilă în domeniul teoriei complexității. Goombas-urile și dinozaurii senzitiv sunt doar decor.
