Teoria Algorísmica de la Informació

La teoria algorísmica de la informació és una branca de la informàtica teòrica que s'ocupa de la relació entre la computació i la informació d'objectes generats computacionalment (a diferència dels generats estocàsticament), com ara cadenes de caràcters o qualsevol altra estructura de dades. En altres paraules, es mostra dins de la teoria algorísmica de la informació que la incompressibilitat computacional "imita" (excepte una constant que només depèn del llenguatge de programació universal escollit) les relacions o desigualtats que es troben en la teoria de la informació. Segons Gregory Chaitin, és "el resultat de posar la teoria de la informació de Shannon i la (teoria de la computabilitat de Turing) en una coctelera i sacsejar amb força".

A més de la formalització d'una mesura universal per al contingut d'informació irreductible d'objectes generats computacionalment, alguns dels èxits principals de la teoria algorísmica de la informació van ser mostrar que: de fet, la complexitat algorísmica segueix (en el cas autodelimitat) les mateixes desigualtats (excepte una constant) que l'entropia, com en la teoria clàssica de la informació; l'aleatorietat és incompressibilitat; i, dins de l'àmbit del programari generat aleatòriament, la probabilitat d'ocurrència de qualsevol estructura de dades és de l'ordre del programa més curt que la genera quan s'executa en una màquina universal.

La teoria algorísmica de la informació estudia principalment mesures del contingut d'informació irreductible de les cadenes de caràcters (o altres estructures de dades). Com que la majoria d'objectes matemàtics es poden descriure en termes de cadenes de caràcters, o com el límit d'una seqüència de cadenes, es pot utilitzar per estudiar una gran varietat d'objectes matemàtics, inclosos els nombres enters. Una de les principals motivacions darrere de la teoria algorísmica de la informació és l'estudi de la informació que transporten els objectes matemàtics com en el camp de les metamatemàtiques, per exemple, tal com mostren els resultats d'incompletesa esmentats més endavant. Altres motivacions principals provenien de: la superació de les limitacions de la teoria clàssica de la informació per a objectes individuals i fixos; formalitzar el concepte d'aleatorietat; i trobar una inferència probabilística significativa sense coneixement previ de la distribució de probabilitat (per exemple, si és independent i distribuïda de manera idèntica, markoviana o fins i tot estacionària). D'aquesta manera, se sap que la teoria algorísmica de la informació es basa en tres conceptes matemàtics principals i les relacions entre ells: complexitat algorísmica, aleatorietat algorísmica i probabilitat algorísmica.

Visió General

La teoria algorísmica de la informació estudia principalment les mesures de complexitat en cadenes (o altres estructures de dades). Com que la majoria d'objectes matemàtics es poden descriure en termes de cadenes, o com el límit d'una seqüència de cadenes, es pot utilitzar per estudiar una gran varietat d'objectes matemàtics, inclosos els nombres enters.

De manera informal, des del punt de vista de la teoria algorísmica de la informació, el contingut d'informació d'una cadena és equivalent a la longitud de la representació autònoma més comprimida possible d'aquesta cadena. Una representació autònoma és essencialment un programa (en algun llenguatge de programació universal fix però d'altra manera irrellevant) que, quan s'executa, genera la cadena original.

Des d'aquest punt de vista, una enciclopèdia de 3000 pàgines en realitat conté menys informació que 3000 pàgines de lletres completament aleatòries, malgrat que l'enciclopèdia és molt més útil. Això és perquè per reconstruir tota la seqüència de lletres aleatòries, cal saber què és cada lletra. D'altra banda, si s'eliminés cada vocal de l'enciclopèdia, algú amb un coneixement raonable de la llengua anglesa podria reconstruir-la, de la mateixa manera que probablement es podria reconstruir l'oració "Ths sntnc hs lw nfrmtn cntnt" a partir del context i les consonants presents.

A diferència de la teoria de la informació clàssica, la teoria de la informació algorísmica dona definicions formals i rigoroses d'una cadena aleatòria i una seqüència infinita aleatòria que no depenen d'intuïcions físiques o filosòfiques sobre el no determinisme o la probabilitat. (El conjunt de cadenes aleatòries depèn de l'elecció de la màquina universal de Turing utilitzada per definir la complexitat de Kolmogorov, però qualsevol elecció dona resultats asimptòtics idèntics perquè la complexitat de Kolmogorov d'una corda és invariant fins a una constant additiva que només depèn de l'elecció de Turing universal. Per aquesta raó el conjunt de seqüències infinites aleatòries és independent de l'elecció de la màquina universal.)

Alguns dels resultats de la teoria algorísmica de la informació, com el teorema de la incompletitud de Chaitin, semblen desafiar les intuïcions matemàtiques i filosòfiques comunes. El més notable d'entre aquests és la construcció de la constant de Chaitin Ω, un nombre real que expressa la probabilitat que una màquina universal de Turing autodelimitada s'atura quan la seva entrada és subministrada per tirades d'una moneda justa (de vegades es pensa com la probabilitat que un programa informàtic finalment s'aturarà). Tot i que Ω es defineix fàcilment, en qualsevol teoria axiomatitzable consistent només es poden calcular un nombre finit de dígits de Ω, de manera que és en cert sentit incognoscible, proporcionant un límit absolut en el coneixement que recorda als teoremes d'incompletesa de Gödel. Encara que els dígits de Ω no es poden determinar, es coneixen moltes propietats de Ω; per exemple, és una seqüència algorísmicament aleatòria i, per tant, els seus dígits binaris es distribueixen uniformement (de fet és normal).

Història

La teoria algorísmica de la informació va ser fundada per Ray Solomonoff, que va publicar les idees bàsiques en què es basa el camp com a part de la seva invenció de la probabilitat algorísmica, una manera de superar problemes greus associats amb l'aplicació de les regles de Bayes a l'estadística. Va descriure per primera vegada els seus resultats en una conferència a Caltech el 1960, i en un informe, febrer de 1960, "Un informe preliminar sobre una teoria general de la inferència inductiva". La teoria algorísmica de la informació va ser desenvolupada més tard de manera independent per Andrey Kolmogorov, al 1965 i Gregory Chaitin, cap al 1966.

Hi ha diverses variants de la complexitat de Kolmogorov o de la informació algorísmica; la més utilitzada es basa en programes autodelimitats i es deu principalment a Leonid Levin (1974). Per Martin-Löf també va contribuir significativament a la teoria de la informació de seqüències infinites. Mark Burgin va introduir una aproximació axiomàtica a la teoria algorísmica de la informació basada en els axiomes de Blum (Blum, 1967) en un article presentat per a la seva publicació per Andrey Kolmogorov (Burgin, 1982). L'enfocament axiomàtic inclou altres enfocaments de la teoria algorísmica de la informació. És possible tractar diferents mesures d'informació algorísmica com a casos particulars de mesures d'informació algorísmica definides axiomàticament. En lloc de demostrar teoremes similars, com el teorema bàsic d'invariància, per a cada mesura en particular, és possible deduir fàcilment tots aquests resultats a partir d'un teorema corresponent demostrat en l'entorn axiomàtic. Aquest és un avantatge general de l'enfocament axiomàtic en matemàtiques. L'enfocament axiomàtic de la teoria de la informació algorísmica es va desenvolupar més al llibre (Burgin, 2005) i es va aplicar a mètriques de programari (Burgin i Debnath, 2003; Debnath i Burgin, 2003).

Definicions precises

Es diu que una cadena binària és aleatòria si la complexitat de Kolmogorov de la cadena és almenys la longitud de la cadena. Un simple argument de recompte mostra que algunes cadenes de qualsevol longitud són aleatòries i gairebé totes les cadenes estan molt a prop de ser aleatòries. Com que la complexitat de Kolmogorov depèn d'una elecció fixa de la màquina universal de Turing (informalment, un "llenguatge de descripció" fix en el qual es donen les "descripcions"), la col·lecció de cadenes aleatòries depèn de l'elecció de la màquina universal fixa. No obstant això, la col·lecció de cadenes aleatòries, en conjunt, té propietats similars independentment de la màquina fixa, de manera que es pot (i sovint es fa) parlar de les propietats de les cadenes aleatòries com a grup sense haver d'especificar primer una màquina universal.

Es diu que una seqüència binària infinita és aleatòria si, per a una constant c, per a tot n, la complexitat de Kolmogorov del segment inicial de longitud n de la seqüència és almenys n − c. Es pot demostrar que gairebé totes les seqüències (des del punt de vista de la mesura estàndard —"moneda justa" o mesura de Lebesgue— en l'espai d'infinites seqüències binàries) són aleatòries. A més, com que es pot demostrar que la complexitat de Kolmogorov relativa a dues màquines universals diferents difereix com a màxim en una constant, la col·lecció de seqüències infinites aleatòries no depèn de l'elecció de la màquina universal (en contrast amb les cadenes finites). Aquesta definició d'aleatorietat se sol anomenar aleatorietat de Martin-Löf, després de Per Martin-Löf, per distingir-la d'altres nocions similars d'aleatorietat. De vegades també s'anomena 1-aleatorietat per distingir-la d'altres nocions més fortes d'aleatorietat (2-aleatorietat, 3-aleatorietat, etc.). A més dels conceptes d'aleatorietat de Martin-Löf, també hi ha aleatorietat recursiva, aleatorietat de Schnorr i aleatorietat de Kurtz, etc. Yongge Wang va demostrar que tots aquests conceptes d'aleatorietat són diferents.

(Es poden fer definicions relacionades per a alfabets diferents del conjunt $\{0,1\}$ .)

Seqüència específica

La teoria de la informació algorísmica és la teoria de la informació d'objectes individuals, utilitzant la informàtica, i s'ocupa de la relació entre la computació, la informació i l'aleatorietat.

El contingut d'informació o la complexitat d'un objecte es pot mesurar per la longitud de la seva descripció més curta. Per exemple, la cadena

"0101010101010101010101010101010101010101010101010101010101010101"

té la descripció breu "32 repeticions de '01'", mentre que

"1100100001100001110111101110110011111010010000100101011110010110"

presumiblement, no té una descripció senzilla més que escriure la cadena en si.

Més formalment, la complexitat algorísmica d'una cadena x es defineix com la longitud del programa més curt que calcula o genera x, on el programa s'executa en algun ordinador universal de referència fixa.

Una noció molt relacionada és la probabilitat que un ordinador universal produeixi alguna cadena x quan és proporcionat amb un programa escollit a l'atzar. Aquesta probabilitat algorísmica "Solomonoff" és clau per abordar l'antic problema filosòfic de la inducció d'una manera formal.

El principal inconvenient de la complexitat algorísmica i de la probabilitat algorísmica és la seva incomputabilitat. La complexitat "Levin" limitada en el temps penalitza un programa lent afegint el logaritme del seu temps d'execució a la seva durada. Això condueix a variants computables de la complexitat algorísmica i de la probabilitat algorísmica i la cerca universal "Levin" resol tots els problemes d'inversió en un temps òptim (a part d'alguna constant multiplicativa poc realista).

La complexitat algorísmica i la probabilitat algorísmica també permeten una definició formal i rigorosa de l'aleatorietat de les cadenes individuals per no dependre d'intuïcions físiques o filosòfiques sobre el no determinisme o la probabilitat. Aproximadament, una cadena és aleatòria algorísmica "Martin-Löf" si és incompressible en el sentit que la seva complexitat algorísmica és igual a la seva longitud.

La complexitat algorísmica, la probabilitat algorísmica i l’aleatorietat algorísmica són les subdisciplines bàsiques de la teoria algorísmica de la informació, però aquesta genera moltes altres àrees. Serveix com a base del principi de longitud mínima de descripció (MDL), pot simplificar les demostracions en la teoria de la complexitat computacional, s'ha utilitzat per definir una mètrica de similitud universal entre objectes, resol el problema del dimoni de Maxwell i molts altres.

Vegeu també

Bibliografia addicional

Blum, M. «On the Size of Machines». Information and Control, 11, 3, 1967, pàg. 257–265. DOI: 10.1016/S0019-9958(67)90546-3.
Blum, M. «A Machine-independent Theory of Complexity of Recursive Functions». Journal of the ACM, 14, 2, 1967, pàg. 322–336. DOI: 10.1145/321386.321395.
Burgin, M. «Generalized Kolmogorov complexity and duality in theory of computations». Soviet Math. Dokl., 25, 3, 1982, pàg. 19–23.
Burgin, M. «Generalized Kolmogorov Complexity and other Dual Complexity Measures». Cybernetics, 26, 4, 1990, pàg. 481–490. DOI: 10.1007/BF01068189.
Burgin, M. Super-recursive algorithms. Springer, 2005. ISBN 9780387955698.
Calude, C.S. «Algorithmic information theory: Open problems». J. UCS, 2, 5, 1996, pàg. 439–441. Arxivat de l'original el 2021-11-28 [Consulta: 11 gener 2022].
Calude, C.S.. Information and Randomness: An Algorithmic Perspective. 2a edició. Springer-Verlag, 2013. ISBN 9783662049785.
Chaitin, G.J. «On the Length of Programs for Computing Finite Binary Sequences». Journal of the Association for Computing Machinery, 13, 4, 1966, pàg. 547–569. DOI: 10.1145/321356.321363.
Chaitin, G.J. «On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers». Journal of the Association for Computing Machinery, 16, 3, 1969, pàg. 407–412. DOI: 10.1145/321526.321530.
Chaitin, G.J. «A Theory of Program Size Formally Identical to Information Theory». Journal of the Association for Computing Machinery, 22, 3, 1975, pàg. 329–340. DOI: 10.1145/321892.321894.
Chaitin, G.J. «Algorithmic information theory». IBM Journal of Research and Development, 21, 4, 1977, pàg. 350–9. DOI: 10.1147/rd.214.0350.
Chaitin, G.J.. Algorithmic Information Theory. Cambridge University Press, 1987.
Kolmogorov, A.N. «Three approaches to the definition of the quantity of information». Problems of Information Transmission, 1, 1965, pàg. 3–11.
Kolmogorov, A.N. «Logical basis for information theory and probability theory». IEEE Trans. Inf. Theory, IT-14, 5, 1968, pàg. 662–4. DOI: 10.1109/TIT.1968.1054210.
Levin, L. A. «Laws of information (nongrowth) and aspects of the foundation of probability theory». Problems of Information Transmission, 10, 3, 1974, pàg. 206–210.
Levin, L.A. «Various Measures of Complexity for Finite Objects (Axiomatic Description)». Soviet Math. Dokl., 17, 1976, pàg. 522–526.
Li, M.; Vitanyi, P. An Introduction to Kolmogorov Complexity and its Applications. 2a edició. Springer-Verlag, 2013. ISBN 9781475726060.
Solomonoff, R.J. (1960). A Preliminary Report on a General Theory of Inductive Inference (PDF) (Technical report). Cambridge, Mass: Zator Company. ZTB-138.
Solomonoff, R.J. «A Formal Theory of Inductive Inference». Information and Control, 7, 1, 1964, pàg. 1–22. DOI: 10.1016/S0019-9958(64)90223-2.
Solomonoff, R.J. «A Formal Theory of Inductive Inference». Information and Control, 7, 2, 1964, pàg. 224–254. DOI: 10.1016/S0019-9958(64)90131-7.
Solomonoff, R.J.. Algorithmic Probability: Theory and Applications, Information Theory and Statistical Learning. Springer, 2009. ISBN 978-0-387-84815-0.
Van Lambagen «Algorithmic Information Theory». Journal of Symbolic Logic, 54, 4, 1989, pàg. 1389–1400. DOI: 10.1017/S0022481200041153.
Zurek, W.H.. «Algorithmic Information Content, Church-Turing Thesis, physical entropy, and Maxwell's demon, in». A: Complexity, Entropy and the Physics of Information. Addison-Wesley, 2018, p. 73–89. ISBN 9780429982514.
Zvonkin, A.K. and Levin, L. A. «The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms». Russian Mathematical Surveys, 256, 6, 1970, pàg. 83–124. Bibcode: 1970RuMaS..25...83Z. DOI: 10.1070/RM1970v025n06ABEH001269.