Modelli astratti di calcolo: Macchine a puntatori

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.