Macchina RAM

Questa voce o sezione sugli argomenti matematica e teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Il modello della macchina RAM è uno strumento classico per l'analisi delle procedure sequenziali. Questo modello è caratterizzato da una memoria ad accesso casuale formata da celle che possono contenere un intero qualsiasi; le istruzioni utilizzate sono quelle di un elementare linguaggio macchina che consente di eseguire istruzioni di input e di output, svolgere operazioni aritmetiche, accedere e modificare il contenuto della memoria, eseguire semplici comandi di salto.

La semplicità di questo modello, astrazione di un elaboratore, consente di comprendere procedure scritte mediante linguaggi ad alto livello e possono essere eseguiti su macchine RAM. Fra i limiti del modello si sottolinea che non è presente una gerarchia di memoria (memoria tampone, memoria di massa) e le istruzioni sono eseguite una alla volta su un unico processore.

Il modello della macchina RAM (macchina ad accesso casuale) è costituito da un nastro di ingresso, un nastro di uscita, un programma rappresentato da una sequenza finita di istruzioni, un contatore lc che indica l'istruzione corrente da eseguire e una memoria formata da infiniti registri R₀,R₁,... R_n. Ciascuno dei due nastri è rappresentato da infinite celle, numerate a partire dalla prima, ognuna delle quali può contenere un numero intero. Il nastro di ingresso è dotato di una testina di sola lettura mentre quello di uscita dispone di una testina di sola scrittura. Le due testine si muovono sempre da sinistra verso destra e nello stato iniziale sono posizionate sulla prima cella. Inizialmente tutte le celle del nastro di uscita sono vuote mentre il nastro di ingresso contiene l'input della macchina; questo è formato da un vettore di n interi x₁,x₂,...x_n disposti ordinatamente nelle prime n celle del nastro.

Il programma è fissato e non può essere modificato durante l'esecuzione. Ciascuna istruzione è etichettata e il registro lc (Location counter) contiene l'etichetta dell'istruzione da eseguire. Le istruzioni molto semplici, si avvicinano molto ad un linguaggio Assembler.

Ogni registro R_k può contenere un numero arbitrario intero relativo. L'indirizzo del registro R_k è l'intero k. Il registro R₀ è chiamato accumulatore ed è l'unico sul quale si possono svolgere operazioni aritmetiche.

Il programma di una macchina RAM è una sequenza finita di istruzioni:

${\displaystyle P=istr_{1};istr_{2};...istr_{m}}$

ciascuna delle quali è una coppia formata da un codice di operazione e da un indirizzo. Un indirizzo a sua volta può essere un operando o un'etichetta. Le etichette sono associate solo a comandi di salto e servono per indicare istruzioni del programma cui passare eventualmente il controllo. Un operando può assumere tre forme diverse:

1. =i indica l'intero i ∈ Z
2. i indica il contenuto del registro R_i
3. *i indica il contenuto del registro R_j, dove j è il contenuto del registro R_i

• Macchina di Turing
• Macchina RASP

Portale Informatica

Portale Matematica