Casualità algoritmica e dimensione effettiva.

Fiorillo, Guido (2020) Casualità algoritmica e dimensione effettiva. [Laurea magistrale], Università di Bologna, Corso di Studio in Matematica [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato

Download (401kB)

Abstract

Nel capitolo 1 della tesi introduciamo dapprima lo "spazio di Cantor'', uno spazio topologico che contiene tutte le successioni infinite di bit. Affrontiamo poi alcuni concetti classici di teoria della misura, individuando, in particolare, due modalità di introdurre una misura sullo spazio di Cantor. Il primo, basato sul teorema di estensione di Carathéodory, porta a definire la misura di Lebesgue, mentre il secondo permette di definire le misure e la dimensione di Hausdorff. In seguito richiamiamo alcune idee di teoria della computabilità e caratterizziamo le misure immagine della misura di Lebesgue tramite un funzionale di Turing. Questa discussione ci porta a definire la "complessità a priori" di una stringa. Nel secondo capitolo presentiamo la teoria della casualità di Martin-Lof, presentandone tre caratterizzazioni equivalenti. Esaminiamo poi le proprietà computazionali delle successioni casuali. Dimostriamo, in primo luogo che ogni classe effettivamente chiusa di misura positiva contiene rappresentanti per tutti i gradi di Turing di sequenze casuali. In seguito, descriviamo una procedura uniforme che permette di codificare una successione qualunque in una successione casuale (teorema di Kucera). Infine, introduciamo la nozione di stocasticità secondo von-Mises-Church e mostriamo che tutte le sequenze casuali nel senso di Martin-Lof sono stocastiche in questa accezione. Nel terzo capitolo introduciamo il concetto di dimensione effettiva e casualità rispetto alla misura di Hausdorff. Parallelamente, introduciamo una diversa e più forte nozione di casualità per la misura di Hausdorff, che si presta a essere caratterizzata tramite le supermartingale e la complessità a priori definita nel capitolo 1. In base a questi risultati, si ottiene una formula per calcolare la dimensione effettiva: $$\dim_H^1(A)= \lim \inf \frac{K(A|_n)}{n}.$$ La tesi si chiude con due esempi che mostrano che per ogni razionale r esiste una successione di dimensione effettiva r.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Fiorillo, Guido
Relatore della tesi
Correlatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum A: Generale e applicativo
Ordinamento Cds
DM270
Parole chiave
casualità randomness Martin-Lof dimensione effettiva computabilità complessità
Data di discussione della Tesi
30 Ottobre 2020
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^