Usuari:Mcapdevila/Teoria algorísmica de la informació

La teoria algorísmica de la informació és una teoria científica de les ciències de la computació teòrica, que en contrast amb la clàssica teoria de la informació, es basa en la complexitat de Kolmogórov per a la determinació del contingut de la informació. Va ser desenvolupada principalment per Gregory Chaitin, Andrei Kolmogórov i Ray Solomonoff.

Introducció

La teoria algorísmica de la informació, principalment estudis de les mesures de complexitat en les cadenes (o estructures de dades). Com que la majoria dels objectes matemàtics poden ser descrits en termes de cadenes, o com el límit d'una seqüència de cadenes, pot ser usat per estudiar una àmplia varietat d'objectes matemàtics, incloent-hi nombres enters i nombres reals.

Aquest ús del terme "informació" podria ser una mica enganyosa, ja que depèn de la noció de compressibilitat. La representació de manera informal, des del punt de vista de la teoria algorísmica de la informació, el contingut de la informació d'una cadena és equivalent a la longitud de l'auto-contingut més breu possible d'aquesta cadena. Un equip autònom de representació és essencialment un programa - en l'idioma alguns fix però d'altra banda irrellevants de programació universal - que, quan s'executa, els productes de l'original.

Des d'aquest punt de vista, de 3000 enciclopèdia pàgina en realitat conté menys informació de 3.000 pàgines de cartes completament a l'atzar, malgrat el fet que l'enciclopèdia és molt més útil. Això es deu a reconstruir tota la seqüència de lletres a l'atzar, un ha de saber, més o menys, el que cada lletra és. D'altra banda, si cada vocal van ser retirats de l'enciclopèdia, algú amb un coneixement raonable de l'idioma Anglès podia reconstruir, només com una probabilitat podria reconstruir la frase "THS sntnc hs cntnt nfrmtn LW" en el context actual i les consonants. Per aquesta raó, les cadenes d'informació d'alta i les seqüències es denominen de vegades "aleatori", la gent també a vegades es tracta de distingir entre "informació" i "informació útil" i pretén proporcionar definicions rigoroses per a aquests últims, amb la idea que les cartes a l'atzar poden tenen més informació que l'enciclopèdia, però l'enciclopèdia té més "útil" de la informació.

A diferència de la teoria clàssica d'informació, la teoria algorísmica de la informació dóna formal, definicions rigoroses d'una cadena aleatòria i una seqüència infinita a l'atzar que no depenen de la intuïció física o filosòfica sobre determinisme o la probabilitat. (El conjunt de cadenes aleatòries depèn de l'elecció de la màquina de Turing universal utilitzat per definir la complexitat de Kolmogórov, però qualsevol opció dóna els mateixos resultats asimptòtica perquè la complexitat de Kolmogórov d'una cadena és invariable fins a una constant additiva que només depèn de l'elecció de Turing universal de la màquina. Per aquesta raó, el conjunt de seqüències a l'atzar infinit és independent de l'elecció de la màquina universal.)

Alguns dels resultats de la teoria algorísmica de la informació, com el teorema d'incompletesa de Chaitin, semblen desafiar intuïcions matemàtiques i filosòfiques. El més notable d'ells és la construcció de la constant de Chaitin Ω, un nombre real que expressa la probabilitat que una de màquina universal de Turing d'auto-delimitació pot aturar-se amb dades d'entrada generades per llançaments de moneda.

Per descriure el contingut de la informació d'una cadena d'informació la teoria algorísmica de la informació té en compte la mida del algorisme més petit que pot generar la cadena. Gregory Chaitin va aclarir aquest fet conegut generalment com la complexitat de Kolmogórov màquina tipus d'una mida determinada, després l'algorisme ha de ser executable. Com podria provar Chaitin, ¿pot el contingut de la informació algorítmica d'una cadena que especifiqui no és definitiva, ja que no és demostrable, si un determinat programa és produir el que realment és el més curt. Tal com el concepte d'informació de Claude Shannon, la teoria algorísmica de la informació no fa declaracions sobre el significat, el coneixement no es defineix matemàticament i termes similars.

Exemple

Segons la definició clàssica, d'acord amb Claude Shannon, el contingut de la informació de les següents seqüències binàries és la mateixa (només aplica l'entropia de primer ordre):

1000110111100101

1111111100000000

La primera seqüència ha estat produïda per un mostreig aleatori, en la segona seqüència, però, s'utilitza la instrucció "8x1 a continuació, i llavors 8X0". Als efectes de la teoria algorísmica de la informació, la primera seqüència per tant, té més informació algorísmica, ja que és molt més complexa o no es pot comprimir. És a dir, la informació algorísmica és tant més gran, quan menys pot ser comprimida una cadena de caràcters (entre altres, per compressió de dades). Les seqüències aleatòries i el soroll blanc en general no contenen cap patró predictible i per tant no són compressibles - el contingut de la informació algorísmica és per tant major.

Antecedents matemàtics

L'enfocament d'Andrei Kolmogórov es pot aplicar també als algoritmes de programes arbitraris d'una màquina de Turing. Gregory Chaitin aplicant la complexitat de Kolmogórov a la teoria de les funcions recursives (vegeu també µ-recursion càlcul lambda i el treball relacionat de Kurt Gödel), limita les aplicacions possibles a les que es poden executar en una variant especial de la màquina universal de Turing (UTM), anomenada màquina universal de Turing amb autodelimitació.

Després de la demostració de Chaitin però, en principi no es pot determinar si una cadena es pot reduir encara més algorítmicament. Per exemple, s'han trobat nous i més eficients algorismes de compressió, però una seqüència aparentment aleatòria de nombres pot venir d'un generador pseudo-aleatori. A causa del problema de l'aturada no totes les màquines de Turing poden ser utilitzades un temps finit.

Vegeu també

Enllaços externs

Com executar algorísmica Teoria de la Informació en un equip per Gregory Chaitin (anglès)
Els límits de les matemàtiques per Gregory Chaitin, incloent-hi un intèrpret per a un estès LISP per simular autolimitada UTM (anglès)
Missatges de comprimit dels estrangers idèntic al soroll
Scholarpedia
Günter Hotz: Algorithmic Information Theory (Part 1) Informe Tècnic FB14 -97-01 de la Universitat de Saarland, FB 14 ciències de la computació, gener de 1997