Modelli astratti di calcolo: Macchine a puntatori

Borghi, Giacomo (2018) Modelli astratti di calcolo: Macchine a puntatori. [Laurea], Università di Bologna, Corso di Studio in Matematica [L-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 (2MB)

Abstract

Presentiamo la classe di modelli di computazione astratti delle Macchine a puntatori mettendole in relazione con i classici modelli computazionali.In particolare ci chiediamo se appartengano alla classe descritta della Tesi di Invarianza. A questo scopo illustriamo la simulazioni di una Macchina di Turing attraverso una Macchina di Schönhage e presentiamo alcuni teoremi riguardanti l'utilizzo dello spazio. Questi risultati mettono in luce come le macchine a puntatori possano essere considerate più potenti rispetto alle Macchine di Turing e alle RAM. Presentiamo poi le Macchine di Kolmogorv-Uspensky, le prime macchine a puntatori inventate, mettendo in luce la riflessione che ne ha portato all'ideazione. Ne presentiamo infine una implementazione biologica tramite il Physarum Polycephalum con l'intento di mostrare come questo modello, grazie alla sua particolare struttura, si presti ad essere un utile strumento per la comprensione di sistemi fisici.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Borghi, Giacomo
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
modelli di computazione macchina astratta macchine a puntatori Schönhage Kolmogorov Uspensky macchina di Turing modificazione della memoria RAM tesi di invarianza complessità computazionale Physarum
Data di discussione della Tesi
28 Settembre 2018
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^