it gb
it gb

L. Roversi - Computazione e Linguaggi Reversibili

I modelli della computazione possono essere visti come insiemi essenziali di azioni il cui scopo è descrivere trasformazioni meccanizzabili di strutture linguistiche opportune. Natura delle trasformazioni, strutture linguistiche manipolate e regole di applicazione delle trasformazioni stesse connotano la natura del modello. Modelli tradizionali sono catalogati come sequenziali o concorrenti: Macchine di Turing, il λ-Calcolo, le funzioni (Primitive) Ricorsive sono esempi di modelli sequenziali, mentre Reti di Petri, Modelli ad Attori, Calcoli di Processi lo sono per quelli concorrenti.

Tra gli scopi principali di un modello computazionale troviamo: (i) lo studio della sua potenza, ovvero la classe di funzioni/relazioni esprimibili in esso, (ii) l‘espressività, ovvero la facilità di definire algoritmi interessanti, (iii) la decidibilità di problemi utili all‘eventuale utilizzo del modello come base per la progettazione di linguaggi di programmazione.

In generale, i modelli computazionali classici: (i) sviluppano computazioni mono-direzionali, dall‘input verso l‘output, (ii) rendono distinguibili l‘uno dall‘altro ciascun elemento negli insiemi di configurazioni, eventualmente prodotti durante la computazione modellata, (iii) permettono una lettura della soluzione che non la altera.

Al contrario, a molti modelli non convenzionali manca almeno una delle precedenti caratteristiche.

I modelli delle computazioni reversibili sviluppano una computazione bi-direzionale che può evolvere, indifferentemente, dall‘input verso l‘output e viceversa.

Tali modelli derivano da speculazioni sulla II Legge della Termodinamica e sono il nucleo di modelli di computazione classici e quantistici.

Paolini e Roversi hanno introdotto la classe delle Permutazioni Primitive Reversibili (RPP), dimostrandone l‘equivalenza con la classe PR delle funzioni Primitive Ricorsive. Matos, Paolini e Roversi hanno studiato la decidibilità di un problema computazionale classico in una sottoclasse significativa di RPP.

Grandi, Moshiri e Roversi, stanno sviluppando un domain specific language (YAReL) a partire dalla classe RPP. Dal punto di vista metodologico, direzioni possibili di sviluppo per RPP sono, almeno: individuare primitive ancora più essenziali delle attuali per rappresentare la selezione ("if"), aumentare la potenza del modello, allargare l‘insieme dei problemi (in)decidibili.

Dal punto di vista applicativo, cioè dello sviluppo di YAReL, alcune direzioni possibili sono, almeno: estendere l‘insieme di tipi di dato disponibili per programmare, scrivere librerie che facilitino l‘uso del linguaggio, studiare l‘interazione con linguaggi classici, come JAVA, compilare nel byte-code di macchine virtuali pensate per essere implementate da processori reversibili.