1.2 Macchine ad accesso random (RAM – Random Access Machines)

Una macchina ad accesso random (RAM) modella un computer con un accumulatore in cui le istruzioni non sono abilitate a modificare se stesse.
Una RAM consiste di un nastro di input a sola lettura, un nastro di output a sola scrittura e una memoria (Fig. 1.3). Il nastro di input è una sequenza di quadratini, ognuno dei quali contiene un intero (possibilmente negativo). Quando viene letto un simbolo dal nastro di input, il nastro sposta la testa un quadratino verso destra. L'output è un nastro a sola scrittura diviso in quadratini che inizialmente sono tutti vuoti. Quando viene eseguita un'operazione di scrittura, un intero viene stampato nel quadratino del nastro di output che in quel momento è puntato dalla testa di output, e la testa di output viene spostata un quadratino verso destra. Una volta che un simbolo di output è stato scritto, non può essere cambiato.


La memoria consiste di una sequenza di registri, r_0 , r_1 , ..., r_i , ..., ognuno dei quali può contenere un intero di dimensione arbitraria. Non poniamo un limite superiore al numero di registri che possono essere utilizzati. Questo modello di astrazione va bene nei casi in cui:


Il programma per la RAM non è immagazzinato nella memoria. Questo perché assumiamo che il programma non modifica se stesso. Il programma è meramente una sequenza di (in maniera opzionale) istruzioni etichettate. L'esatta natura delle istruzioni utilizzate nel programma non è molto importante, affinché le istruzioni somiglino a quelle che di solito si trovano realmente all'interno del computer. Assumiamo che ci sono istruzioni aritmetiche, istruzioni di input-output, indirizzamento indiretto (come per gli indici di un array, ecc.) e istruzione di ramificazione. Tutta la computazione prende luogo nel primo registro r_0, chiamato accumulatore, che come tutti gli altri registri di memoria può contenere un intero arbitrario. Un insieme di istruzioni esemplificativo per una RAM è mostrato in Fig. 1.4. Ogni istruzione consiste di due parti: un codice di operazione e un indirizzo.


In linea di principio, potremmo aumentare il nostro insieme con ogni altra funzione che si trovi all'interno di reali computer, come operatori logici o operazioni sui caratteri, senza alterare l'ordine di grandezza della complessità dei problemi. Il lettore può immaginare l'insieme delle istruzioni aumentato di tanto quanto vuole.
Un operatore può essere uno dei seguenti:


Queste istruzioni dovrebbero risultare familiari a chiunque abbia programmato in linguaggio assembler. Possiamo definire il significato di un linguaggio P con l'aiuto di due quantità, una funzione c da interi non negativi a interi ed un “posizione di contatore” che determina la prossima istruzione da eseguire. La funzione c è una memoria mappa; c(i) è l'intero memorizzato nel registro i (il contenuto del registro i).
Inizialmente, c(i) = 0 per tutte le i ≥ 0, la posizione del contatore è settata alla prima istruzione in P, e il nastro di output è tutto vuoto. Dopo l'esecuzione della k-esima istruzione in P, la posizione del contatore è automaticamente settata a k + 1 (l'istruzione successiva), fino a quando l'istruzione è JUMP, HALT, JGTZ, o JZERO.
Per specificare il significato di un'istruzione definiamo v(a), il valore dell'operatore a, come segue:


La tavola di Fig. 1.5 definisce il significato di ciascuna istruzione in Fig. 1.4. Istruzioni non definite, come STORE = i, possono essere considerate equivalenti all'HALT. Inoltre, la divisione per zero ferma la macchina.

QUA SERVIREBBE INFILARE L'IMMAGINE 1.5

Durante l'esecuzione di ciascuno delle prime otto istruzioni la posizione del contatore è incrementata di uno. Queste istruzioni sono eseguite nel programma in ordine sequenziale finché un'istruzione JUMP o HALT è incontrata, si incontra JGTZ con il contenuto dell'accumulatore più grande di zero, o si incontra un'istruzione JZERO con il contenuto dell'accumulatore uguale a zero.
In generale, un programma RAM definisce una mappatura da un nastro di input ad uno di output. Finché il programma non si ferma su tutto il nastro di input, la mappatura è una mappatura parziale (la mappatura potrebbe essere indefinita per certi input). La mappatura può essere interpretata in diversi modi. Due importanti interpretazioni sono come una funzione o come un linguaggio.
Supponiamo che un programma P legga sempre n interi dal nastro di input e scrive almeno un intero sul nastro di output. Se, quando x_1 , x_2 , ..., x_n sono gli interi nei primi n quadratini nel nastro di input, P scrive y per primo quadratino del nastro di output e susseguentemente si arresta, poi diciamo che P computa la funzione f(x_1 , x_2 , ..., x_n) = y. E' mostrato chiaramente che una RAM, come ogni altro ragionevole modello di computer, può computare esattamente le funzioni ricorsive parziali. Questo vuol dire che data una qualsiasi funzione parziale ricorsiva f possiamo definire un programma Ram che calcola f e dato un qualsiasi programma Ram possiamo definire una funzione parziale ricorsiva equivalente.

QUA SERVIREBBE INFILARE IL RESTO

---

Torna ad Algoritmi e Strutture dati