title: Macchina RAM
text: # Macchina RAM
  
  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.
  
  ## Modello
  
  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_0,R_1,...$ $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_1,x_2,...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_0$ è chiamato accumulatore ed è l'unico sul quale si possono svolgere operazioni aritmetiche.
  
  ## Programmazione di una macchina RAM
  
  Il programma di una macchina RAM è una sequenza finita di istruzioni:
  
  $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:
  
  * =i indica l'intero i ∈ Z
  * i indica il contenuto del registro $R_i$
  * *i indica il contenuto del registro $R_j,$ dove j è il contenuto del registro $R_i$
  