spyked bricks in the wall

codul qr și game of life

Așa-zisul cod QR reprezintă o metodă de codificare a informației digitale astfel încât aceasta să poată fi decodificată ulterior cu ușurință — rapid și fără erori — cu ajutorul unui senzor optic, e.g. o cameră foto. Nu-i cu nimic diferit conceptual de un cod de bare, având însă avantajul că admite o densitate a informației ceva mai ridicată. În particular, e mult mai ușoară stocarea unui șir de caractere ASCII sau Unicode sub forma QR decât cu ajutorul codurilor de bare clasice, cum ar fi EAN sau ce se mai găsește în mod normal pe etichetele produselor aflate în comerț.

Game of Life este un automat celular faimos, descoperit de către matematicianul John Horton Conway. Regulile automatului sunt oarecum intuitive, și în plus configurațiile inițiale pot duce la evoluții „haotice”, posibil utile pentru modelarea în domenii precum cel al biologiei, economiei sau fizicii — numele „Game of Life” nu e ales tocmai la întâmplare. O particularitate interesantă pentru calculatoare și teoria informației este aceea că unele din „structurile” simple din Game of Life pot fi folosite pentru a construi mașini Turing. Dincolo de asta, e greu de zis ce mai ascunde automatul cu pricina.

Ce au cele două în comun? În primul rând, ambele lucrează cu alfabetul binar, deci cu celule formate din biți. În al doilea rând, ambele folosesc reprezentări bidimensionale, adică matriciale și (eventual) pătratice, unde dimensiunea matricei poate ajunge teoretic să fie infinită (mai greu în cazul QR, foarte ușor pentru Game of Life). În al treilea rând, ambele pot fi folosite pentru a reprezenta informație: codul QR oferă în plus facilități de corectare a erorilor; Game of Life e o mașină, deci poate face mult mai mult decât să stocheze propriu-zis informație, o poate prelucra. Astfel, cele două instrumente ar putea fi lejer confundate la o primă vedere, cu toate că servesc în principiu scopuri diferite, primul de mediu de stocare fiabilă a bucăților de informație pe toate gardurile, al doilea de model teoretic de calcul.

Ei, iată că un individ pe nume Roland Mas a dat curs unei provocări foarte interesante, care este îmbinarea celor două funcționalități într-un singur program. Funcționarea programului este simplă: acesta primește la intrare un text oarecare, pe care îl codifică sub forma unui QR, care va fi folosit mai apoi ca stare inițială pentru Game of Life. Un alt individ, purtând numele Jurij Smakov a răspuns deja provocării, programând în Javascript un astfel de QR-Game of Life. Interesant, și în plus perfect inutil, nu? Eu zic că nu.

Un alt fapt interesant legat de Game of Life este acela că mai toate „programele” — adică evoluțiile în funcție de starea inițială — par să conveargă la stări care sunt fie stabile, fie cvasi-stabile. Cele complet stabile sunt „still life”. Cele cvasi-stabile sunt oscilatori, sau mai rar glidere/LWSS-uri care se plimbă la infinit pe tablă, deci șiruri de stări care se repetă cu o perioadă fixă. Atât numărul de pași până la convergență cât și perioada de repetiție variază în funcție de starea inițială, deci în particular de informația codificată în codul QR.

Întrebările mele sunt următoarele: poate fi găsită oare o legătură între entropia datelor de intrare și /? Dacă da, care ar fi aceasta? Intuiția îmi zice că timpii de convergență/repetare cresc în funcție de entropie, dar e posibil să nu existe nici un fel de legătură între cele două. Ar fi și mai fain dacă cineva ar avea timpul și răbdarea să demonstreze formal legătura, sau lipsa acesteia. Provocarea este deci lansată.