Mașini Turing cu bandă finită, compresie, etc
(aberații informatice)
Problema opririi mașinii Turing este nedecidabilă. Dacă nu știți despre ce vorbesc, atunci e bine să vă opriți aici. Vorbesc serios !
Tocmai când mă decisesem să scriu mai pe înțelesul oamenilor mi-a trăsnit o idee mult prea creață, poate și greșită (am cam uitat teoria de la Matematică - Informatică).
Mașina Turing clasică operează cu un număr finit de stări și o bandă infinită. În realitate nu pot exista decât mașini (calculatoare) finite. Problema opririi unei mașini Turing cu bandă finită este însă decidabilă ! Demonstrația este simplă, mașina cu bandă finită are un număr finit de stări (chiar dacă foarte multe), iar după cel mult acest număr de tranziții va trebui să cicleze printr-o stare anterioară, deci va intra într-o buclă infinită. Dacă se oprește mai înainte, atunci ... se oprește, dacă nu atunci sigur nu se va opri niciodată.
Pentru a decide că orice mașină Turing cu o anumită lungime de bandă se oprește, este suficientă o mașină Turing cu bandă ceva mai mare (dar tot finită). Mașina care decide o va rula pe cea "testată" cel mult N pași (numărul maxim de stări posibile). Dacă mașina nu s-a oprit până la N, atunci răspunsul este că nu se oprește niciodată. Dacă s-a oprit atunci ... se oprește.
Bun și ce-i cu asta ?
Păi există o consecință interesantă - probabil doar pentru mine :)
Mă întrebam la un moment dat care este cea mai mică compresie posibilă a unui fișier (șir de biți). Practic poți comprima orice fișier într-un singur bit (0), dacă ascunzi biții lui în programul de decomprimare, iar celelalte fișiere "comprimate" încep toate cu (1). Pe de altă parte, dacă vrei să comprimi toate fișierele posibile de lungime X, îți vor trebui în total cel puțin la fel de mulți biți precum suma lungimii în biți a fișierelor comprimate. Ca și la energie, biții se conservă, nu poți înghesui informația. Ce economisești de la unul trebuie să pui în plus la altul (fișier, șir de biți).
Dacă unele fișiere se vor comprima în mai puțini biți decât originalul, altele se vor comprima obligatoriu în mai mulți biți. Nevoia de a avea mai mulți biți vine din nevoia de a avea în mulțimea "comprimărilor" un număr cel puțin egal cu numărul fișierelor "de comprimat", altfel nu ar exista suficiente comprimări pentru toate fișierele "de comprimat". De exemplu nu poți comprima toate fișierele de 8 biți (256 la număr) ca fișiere de 7 biți (128 la număr), deoarece din 128 de fișiere distincte comprimate nu putem să decomprimăm toate cele 256 fișiere distincte.
Oricum, de reținut este faptul că un fișier care se comprimă în ceva foarte mic nu spune neapărat ceva despre cât de redundant este fișierul, atâta timp cât îl putem ascunde în programul de decomprimare. Astfel, o definiție mai bună a nivelului de compresie este să ia în considerare și mărimea programului de decompresie. Am putea considera că lungimea comprimatului este lungimea arhivei sale "self extract" (care conține și programul de decompresie).
Buuun...
Legătura este că putem considera ca și arhivă "self extract" mașina Turing cu bandă finită care generează la final fișierul "de comprimat". Întotdeauna există o mașină Turing de lungimea fișierului inițial care îl produce : este mașina care pornește într-o stare finală având fișierul "de comprimat" pe bandă. De fapt dimensiunea va fi un pic mai mare, dar nesemnificativ. Dimensiunea mașinii Turing o definesc ca lungimea în biți a reprezentării ei naive : șirul de biți de pe bandă la pornire plus reprezentarea automatului cu stări finite asociat.
Putem (teoretic) testa toate mașinile Turing de bandă finită care au lungimea mai mică decât a fișierului inițial și să vedem dacă există una și mai mică care generează fișierul inițial. Bineînțeles asta înseamă și testarea tuturor automatelor cu stări finite posibile asociate (sub un anumit număr de stări). Poate să fie nefezabil practic, dar vorbim teoretic.
Întrucât oprirea cu bandă finită este decidabilă, vom putea testa complet toate aceste mașini Turing (bandă finită), nu vom rămâne niciodată cu o mașină care pare să nu se oprească, dar la care să nu putem decide dacă nu cumva se va opri totuși la un moment dat, exact cu rezultatul așteptat.
Notă: o consecință interesantă a indecidabilității la bandă infinită este că oricât de mare ai stabili mărimea benzii (ex: N*sir_de_comprimat"), pot exista cazuri în care compresia minimală să pornească de la o dimensiune mai mică decât "sir_de_comprimat", să folosească obligatoriu spațiu temporar mult mai mare și să ajungă la final la "sir_de_comprimat". Alternativa ar fi ca toate problemele de mai sus sunt decidabile și cu bandă infinită. Este un subiect care ar merita investigat.
Concluzia ar fi că cel puțin teoretic, putem calcula pentru orice informație (șir de biți) o "cea mai mică compresie posibilă" pentru o lungime maximă a benzii, ca mărime a redundanței intrinseci a acelui șir de biți. Mărimea redundanței s-ar putea difini ca raportul dintre mărimea șirului necomprimat și lungimea compresiei minime. Am putea deci ordona diverse șiruri de biți în funcție de câtă informație neredundantă conțin. Întrucât orice șir de biți determină un număr natural, putem extinde măsurarea redundanței la numere.
Baza 2 folosită în exemplu nu este în sine relevantă, este vorba de o proprietate care ține foarte mult de număr în sine. Dacă numărul este foarte ușor comprimabil în baza 2, dar arată foarte neregulat în baza 3 de exemplu, putem totuși comprima ușor reprezentarea în baza 3 în doi pași : transformăm numărul în baza 2 și apoi îl comprimăm. Pentru numere mari, overheadul de transformare dintr-o bază în alta va fi nesemnificativ.
Un exemplu de comprimare care nu depinde prea mult de baza de numerație este reprezentarea ca produs de numere prime ridicate la o putere. De exemplu un număr se poate descompune ca :
3 * 7^22222. Acest număr este foarte lung ca reprezentare în orice bază, dar devine foarte scurt (comprimat) prin identificarea redundanțelor sale, mai ales faptul că se poate obține pornind cu 3 și înmulțind cu 7 de 22222 de ori. Toate operațiile matematice au echivalent în mașina Turing, deci pot face o mașină Turing relativ mică care să-i genereze reprezentarea zecimală pornind de la reprezentarea concisă 3*7^22222. O întrebare mare ar fi dacă vom găsi compresii puternice care să nu se bazeze pe operații matematice cunoscute, ceea ce ar duce poate la descoperirea unor operații matematice noi.
Bineînțeles valoarea redundanței este ușor relativă, este măsurată în mulțimea mașinilor Turing cu acea lungime maximă de bandă (dimensiune aleasă), cu un anumit număr maxim de stări, tranziții, etc. Am putea alege alte sisteme automate Turing echivalente. Totuși alegând limite destul de mari, se poate decide în ultimă analiză care șiruri de biți au o redundanță ascunsă și care nu. Schimbând reprezentarea mașinii Turing s-ar putea inversa unele scoruri, dar mă aștept ca la șiruri mari de biți să se păstreze inegalitatea ca "nivel al redundanței".
Update2 (schimbat exemplul cu unul mai relevant, adăugat Kolmogorov):
Mai bulversant este că putem spune chiar despre numere cât de complexe sunt. Un număr de peste 3000 cifre zecimale precum 1024^1024 (1024 la puterea 1024) se poate exprima într-un limbaj matematic în doar 9 caractere, în ciuda faptului că în reprezentarea zecimală nu pare să conțină prea multă redundanță:
1024^1024 =
35249714121083826571348148398002815464391421343966471060391382605731\
07027685474936504833029647366386245696815539529837397325904947594311\
36198883386731161336668147068707652719076562056460186083699855587212\
67670321739031938633833281889192620158426531806923144239269726876399\
95196119198034802329170347230576378241039458975893458563111107812043\
53030326888187514464352913713571717556327753629326947950763134366874\
69638004327689390246735321855830610856865924913760826763776003265851\
71655733421064227734347575779978049902155982241243427508708431729345\
51295704067075900020717046731355275335432173559875681076975779467857\
96412456048360072965616871024866244650081059068183038134518514222987\
18683739459801985951299360037923619019757683890508073335998909468700\
89994162477220200619925599314018723573797084885850036669659306097304\
30774107407494018065365845077094320534700692354400169824131578389153\
65691675468225242556274289502682208611223618576893194043332407869238\
64636423780292915823845509040122842652771246674528169856593374975809\
91592510201479766500877427834566619156314388107585743546289067551052\
43407567819534537336391957132321011362261551176513432962720795579360\
53768928759383576728708813056793055212933599754278019219975348914740\
90868113467357784359783383091085717100807228425031226776985197364359\
40468304150661394364666619945489936368580184877672968583780322821611\
38338547424434092214804502325631304177096253207949716727377373859839\
75520047739978165124906916857931960902407397841536657650378758012409\
15720593951308532428243929010890906903651543069035996315298658774993\
05168806703261450369876070529616967815564185509662018228218579780200\
62536824015697620957222738065538832187097409859502669196589025961199\
44875899737379297319172333554977239487887405085453278592247582283640\
37939866231931740209314323814184370227604126822763829893548396254532\
41289807108260905134234679130954867570447354549760174691007078528452\
74502799494385322948054451236883137876111968161671932763730814231510\
51205287046835151820383202250786653139117317493642556212844343049454\
37214609406008640520972029509955435568094888815701470419410889156523\
97118217281442327414095542807059432838166704828677197285770343552580\
35447078345677740272066141434199824101092619306983110108578748668407\
43851472857645330929169548403751084494725893729355450473771059986801\
05834202190273536762790097487236813783899639737989816145482597091073\
28582027812829739376428479733818386729806933990394293426130015951489\
68082010016061022316242842367672741265405434553107296623559604413326\
35214052961817117545065788425509933461872273169792018558243718239139\
76733011681606825166392147065669814659617313748089491317423647529930\
78326367714117001404210930251538132442219335072672096865184691303027\
15696243977705370728658394976405515129181640254646245271913479717909\
92102335775962779256460318241722748740845621134400433973951910654736\
20717104250686040896580928700842593919173283844531470952205600874482\
30248852386707453290778126499086535184468480701220803910828756453485\
45004863915388760636114766656202302948114683518353740720605302159079\
09311281816131942219776
În ciuda acestei reprezentări complexe în baza zece, putem observa această compresibilitate și textual, dacă transformăm puțin numărul: 1024^1024 se scrie în baza 2 ca 1 urmat de 10240 de zerouri. Dacă am fi pornit cu șirul de cifre zecimale, nu am fi putut probabil să observăm această redundanță, însă considerând numărul asociat am putut găsi o descompunere foarte simplă.
Se pare că am încercat să reinventez complexitatea Kolmogorov. Am scris acest articol înainte de a studia această teorie, care formalizează mult mai bine problematica compresiei. Un număr foarte mare, care are o expresie matematică foarte simplă, va avea și o complexitate Kolmogorov foarte mică, întrucât se poate crea o mașină Turing relativ simplă care să calculeze orice expresie matematică. E posibil ca și reciproca să fie adevărată, însă nu am în acest moment o demonstrație simplă în minte. Un argument este că mașinile Turing sunt echivalente ca și putere de expresie cu mulțimea funcțiilor calculabile.
Update : un prieten mi-a trimis link la demonstrația în versuri a faptului că problema opririi mașinii Turing este nedecidabilă. Aceasta nu contrazice însă ceea ce spun mai sus. Cele două împreună spun că : problema opririi mașinii Turing este decidabilă pentru orice clasă de programe care se încadrează într-o anumită dimensiune, dar mașina Turing care poate face asta este mult mai mare decât dimensiunea clasei de programe. Teorema indecidabilității se poate demonstra doar pentru că ia ca input un program de dimensiune aproximativ egală cu mașina care decide oprirea.
Dacă v-a plăcut articolul, daţi vă rog un share :