Libro · 2013 · Ming Li, Paul Vitanyi

An Introduction to Kolmogorov Complexity and Its Applications

In breve, rivediamo gli elementi di base della teoria della computabilità e della teoria della probabilità necessari. Infine, per collocare l'argomento nel contesto storico e concettuale appropriato, tracciamo le principali radici della complessità di Kolmogorov. In questo modo si prepara il terreno per i Capitoli 2 e 3, dove introduciamo la nozione di descrizioni efficaci ottimali di oggetti. La lunghezza di tale descrizione (o il numero di bit di informazione in essa) è la sua complessità di Kolmogorov. Trattiamo tutti gli aspetti della teoria matematica elementare della complessità di Kolmogorov. Questo insieme di conoscenze può essere chiamato teoria della complessità algoritmica. La teoria dei test di Martin-Lof per la casualità di oggetti finiti e sequenze infinite è indissolubilmente intrecciata con la teoria della complessità di Kolmogorov ed è trattata in modo completo. Investigiamo anche le proprietà statistiche delle stringhe finite con alta complessità di Kolmogorov. Entrambi questi argomenti sono estremamente utili nella parte applicativa del libro. Esploriamo anche le proprietà ricorsive della complessità di Kolmogorov (relazioni con il risultato di incompletezza di Gödel) e la versione della teoria dell'informazione della complessità di Kolmogorov, che possiamo chiamare "teoria dell'informazione algoritmica" o "teoria dell'informazione assoluta". Il trattamento della teoria della probabilità algoritmica nel Capitolo 4 presuppone le Sezioni 1.6, 1.11.2 e il Capitolo 3 (almeno le Sezioni 3.1 fino a 3.4).