Modello RASP

Il modello RASP mantiene il programma in memoria e permette di modificare le istruzioni durante l'esecuzione

Caratteristiche strutturali:

• Identico set d'istruzioni ma manca l'indirizzamento indiretto

• Il programma è caricato in memoria

• Ad ogni istruzione sono associati due registri

  • il primo codifica l'istruzione e il tipo di operando
  • il secondo contiene l'indirizzo

  

  • ci sono piccole variazioni:
    • il registro lc viene automaticamente incrementato di 2 (un'istruzione occupa due registri)
    • la memoria contiene inizialmente il programma in una sequenza prefissata di registri

I concetti di stato, computazione, funzione, tempo e spazio rimangono immutati.

Così come le notazioni per i costi in tempo e spazio uniformi e logaritmici

Equivalenza tra RAM e RASP

Teorema: $\forall \phi$ programma RAM, $\exist \psi$ programma RASP tale che $\forall n \in N, \forall x \in Z^n$

• $F_\phi(x)=F_\psi(x)$
• $T_\psi(x) \leq 6*T_\phi(x)$ (6 perchè per simulare l'indirizzamento indiretto servono 6 istruzioni)

Dimostriamo che ogni istruzione RAM (code, op) può essere tradotta in una sequenza finita di al più 6 istruzioni RASP

• $op \neq \text{ ' * i' }$traduzione diretta

• $op = \text{ ' * i' }$mostriamo come si simula l'indirizzamento indiretto.

  • Il programma RASP viene memorizzato nei registri da $R_2$ a $R_1$, con $r = 12 * |\phi|+1$
  • supponiamo di simulare "MULT *k" nei registri da $R_M$ a $R_{M+11}$

  

Equivalenza tra RAM e RASP: costo logaritmico

Un teorema simile vale anche se si considera il CCL