Stocasticità e incomprimibilità algoritmica

Partiamo dal lavoro di Kolmogorov per definire una misura della quantità di informazione contenuta in una stringa tramite un approccio computazionale: la complessità di una stringa è la lunghezza del più corto programma capace di produrla. Vediamo poi gli sviluppi moderni di questa teoria, in particolare i contributi di Chaitin, e notiamo subito i forti legami con la teoria della probabilità e con l'entropia di Shannon. Successivamente proponiamo di identificare le stringhe casuali (nel senso intuitivo) con quelle algoritmicamente incomprimibili, seguendo l'idea che minore comprimibilità significhi minore regolarità e dunque maggiore casualità. Infine vediamo che, in effetti, le stringhe incomprimibili soddisfano tutte le proprietà stocastiche effettivamente verificabili, cioè le proprietà che la teoria della probabilità attribuisce a successioni di variabili aleatorie indipendenti e identicamente distribuite. Facciamo ciò in maniera generale utilizzando la notevole teoria di Martin-Löf e poi vediamo in dettaglio l'aspetto della normalità di Borel.

Funzioni BV e disuguaglianze isoperimetriche

All'interno della mia tesi verrà introdotta la teoria delle funzioni in R^{n} a variazione limitata (BV), seguendo le presentazioni di Lawrence C.Evans e Ronald F.Gariepy nel libro Measure Theory and Fine Properties of Functions e di Enrico Giusti nell'opera Minimal Surfaces and Functions of Bounded Variation. Le funzioni BV sono funzioni le cui derivate prime deboli sono misure di Radon, ossia misure di Borel regolari finite sui compatti. In particolare verranno anche analizzati gli insiemi E che hanno perimetro finito, ossia tali che la funzione indicatrice dell’insieme E sia una funzione BV. Nello specifico, nel primo capitolo verranno date le definizioni di funzioni BV e insiemi di perimetro finito, sia in una versione globale che in una locale, verrà enunciato un primo importante teorema per le funzioni BV e verrà analizzata la relazione tra funzioni di Sobolev e funzioni BV. Nel secondo capitolo, invece, verranno analizzate la semicontinuità inferiore, l'approssimazione con funzioni lisce e la compattezza di funzioni BV, mentre nel terzo capitolo verranno elencati alcuni risultati sulle funzioni BV riguardanti la Traccia, l'Estensione e la formula di Coarea. Infine, nel quarto ed ultimo capitolo, verranno studiate le disuguaglianze di Sobolev e Poincaré e le disuguaglianze isoperimetriche per funzioni BV.