Macchine a registri
RAM (Random Access Machines)
•
•
•
•
•
•
Introdotte da Shepherdson e Sturgis nel 1963 per sviluppare la teoria della
calcolabilità con un modello astratto di un reale calcolatore (macchina di von
Neumann)
Memoria costituita da un numero fnito ma arbitrario di celle (registri)
direttamente indirizzabili: R1, R2, ..., Rn
Una cella può contenere un intero non negativo
Registri speciali: accumulatore
R0
contatore istruzioni
CI
Nastri di ingresso e di uscita
Unità centrale in grado di eseguire semplici istruzioni logico-aritmetiche
R1
ALU
R2
R3
ACCUMULATORE
............
CONT. ISTRUZIONI
Repertorio istruzioni
LOAD, STORE: trasferimenti da registri ad accumulatore e viceversa
READ, WRITE: trasferimenti da nastro di input a registri e da registri a nastro di output
ADD, SUB, MULT, DIV: operazioni aritmetiche tra accumulatore e registri; il risultato
resta nell'accumulatore
JGTZ, JEQZ: salti condizionati dal contenuto dell' accumulatore
JUMP: salto incondizionato
HALT: terminazione
U n programma non e' contenuto in memoria ma è 'cablato' (una macchina - un
programma).
Es. Programma per il calcolo di xy
5
14
READ
READ
LOAD
STORE
LOAD
JEQZ
LOAD
MULT
STORE
LOAD
SUB
STORE
JUMP
WRITE
HALT
1
2
=1
3
2
14
1
3
3
2
=1
2
5
3
lettura di x dal nastro di ingresso
lettura di y dal nastro di ingresso
inizializzazione del risultato
fne ciclo
R[3] = x * R[3]
stampa del risultato
Sintassi delle istruzioni
LOAD
STORE
ADD
SUB
MULT
DIV
READ
WRITE
JUMP
JGTZ
JEQZ
HALT
operando:
etichetta:
n
*n
=n
[ = | * ] operando
[ * ] operando
[ = | * ] operando
[ = | * ]operando
[ = | * ]operando
[ = | * ]operando
[ * ] operando
[ = | * ]operando
etichetta
etichetta
etichetta
etichetta
:
:
:
indirizzamento diretto al registro n
indirizzamento indiretto al registro R[n]
operando immediato
numero di un'istruzione
Semantica delle istruzioni
ADD
n
R[0] := R[0]+R[n]
CI := CI+1
ADD *n
R[0] := R[0]+R[R[n]]
CI := CI+1
ADD
R[0]:= R[0]+n
CI:=CI+1
=n
JGTZ m
if R[0] > 0 then CI := m else CI := CI+1
Modelli di costo per RAM
•
Modello a costi uniformi
- costo unitario per l'esecuzione di ogni istruzione
Es. Eseguire il programma per calcolare xy costa O(y); infatti le 9 istruzioni del ciclo
vengono eseguite y volte
Critiche:
- calcolare 10 x 10 costa quanto calcolare 1.000.000 x 1.000.000
- accedere ad un registro su 10 costa quanto accedere ad un registro su 1.000.000
•
Modello a costi logaritmici
- l'elaborazione di un intero n ha costo l(n)
- l'accesso al registro i ha costo l(i)
l(n) = 1
se n = 0
l(n) = ⎣log2 n⎦ +1
se n > 0
così l(n) indica il numero di bits necessari a rappresentare n in base 2.
Es. Per eseguire l'istruzione ADD *3 si paga l(3) + l(R[3]) (per accedere a due registri)
+ l(R[R[3]]) + l(R[0]) (per eseguire della somma).
Es. Eseguire il programma per calcolare xy con modello a costi logaritmici.
5
14
READ
READ
LOAD
STORE
LOAD
JGTZ
LOAD
MULT
STORE
LOAD
SUB
STORE
JUMP
WRITE
HALT
1
2
=1
3
2
14
1
3
3
2
=1
2
5
3
1
l(1)+l(x)
l(2)+l(y)
l(1)
l(3)+l(1)
l(2)+l(y)
l(y)
l(1)+l(x)
l(3)+l(x)+l(xy)
l(3)+l(xy)
l(2)+l(y)
l(1)+l(y)
l(2)+l(y)
1
l(3)+l(xy)
O(log x)
O(log y)
O(1)
O(1)
O(log y)
O(log y)
O(log x)
O(log x + y log x)
O(y log x)
O(log y)
O(log y)
O(log y)
O(1)
O(y log x)
O(1)
La porzione di codice dentro la cornice viene eseguita O(y) volte
Costo di esecuzione totale: O(y2 log x).
Calcolabilità di funzioni mediante RAM
e relazione tra RAM e MT
Def. Una funzione f: Nn →N è calcolabile da una RAM se esiste un programma P tale
che:
- se f(x1,..., xn) = y, allora P, inizializzato con x1,...,xn sul nastro di input, termina
con y sul nastro di output
- se f(x1,..., xn) non e' defnita, allora P non termina
Teorema. Sia M una MT con nastro semi infnito ed alfabeto di nastro {1, 0}.
Esistono una RAM ed un programma P tali che, se per M vale che q 0x |—* qFy in t passi,
allora la RAM, con la stringa x nelle celle 2,....,|x|+1, al termine della computazione ha
la stringa y nelle celle 2,....,|y|+1.
Inoltre se M compie t passi allora la RAM simula t passi di M in tempo O(t log t) nel
modello a costi logaritmici.
Dim. Usiamo il registro 1 per indirizzare il registro che corrisponde alla cella letta dalla
testina di M e quindi stabiliamo una corrispondenza tra la cella i del nastro di M ed il
registro i+1 della RAM.
All'inizio il registro 1 della RAM contiene il valore 2 (il registro 2 della RAM
corrisponde alla prima cella letta da M all’inizio del calcolo).
Per ogni stato qi di M, P contiene due sequenze di istruzioni corrispondenti alle due
transizioni δ(qi,1) e δ(qi,0).
Esempio.
Se δ(qi, 0) = <q2, 1, d> e δ(qi, 1)=<q3, 0, s> allora P contiene il seguente frammento:
....................
qi
LOAD
*1
acquisizione del contenuto del nastro
JGTZ
qi'
lettura di un 1 o di uno 0?
LOAD
=1
STORE
*1
scrittura di un 1 sul nastro
LOAD
1
ADD
=1
STORE
1
movimento a destra della testina
JUMP
q2
aggiornamento dello stato
qi'
LOAD
=0
STORE
*1
scrittura di uno 0 sul nastro
LOAD
1
SUB
=1
STORE
1
movimento a sinistra della testina
JUMP
q3
aggiornamento dello stato
....................
Ogni passo di M e' simulato da al più 8 istruzioni ognuna con costo O(log tmax), dove
tmax è il massimo numero di celle usate da M.
Se M esegue t passi allora tmax ≤ t+1. Costo complessivo O(t log t).
Un analogo teorema puo' essere dimostrato per una macchina di Turing multinastro o
con alfabeto di nastro qualunque.
Teorema. Sia P un programma di una RAM che calcola una funzione f: Nn →N.
Esiste una MT M tale che, se sul nastro di input sono memorizzati in binario gli interi
x1,..., xn , allora M termina con la rappresentazione binaria di f(x 1,..., xn) sul nastro di
output se f(x1,..., xn) e' defnita mentre se f(x1,..., xn) non e' defnita M non termina.
Inoltre se la computazione della RAM ha costo t nel modello a costi logaritmici allora M
la simula in O(t2) passi.
Dim. M ha tre nastri di lavoro, più uno di input ed uno di output.
Sul nastro 1 sono memorizzati in binario i dati memorizzati nei registri effettivamente
usati dalla RAM, preceduti dal proprio indirizzo rappresentato in binario, cioè:
#i1#R[i1]#i2#R[i2]#i3#R[i3] ... #im#R[im].
Sul nastro 2 è rappresentato il contenuto dell'accumulatore.
Il nastro 3 è usato come memoria di lavoro.
(Fig. 6.2 a pag. 260)
Per ogni istruzione del programma della RAM, M ha un insieme di stati per eseguire
l'istruzione.
•
Per istruzioni RAM che modifcano il contenuto della memoria, STORE, READ:
M trascrive sul nastro 3 il contenuto del nastro 1 a destra del registro da
modifcare, se c'è; poi esegue l'operazione modifcando sul nastro 1 il contenuto
del registro da modifcare; infne ricopia sul nastro 1, a destra della cella
modifcata, il contenuto del nastro 3 che non è stato modifcato.
•
Per istruzioni RAM che non modifcano il contenuto della memoria, LOAD,
ADD, SUB, MULT, DIV, WRITE:
M cerca sul nastro 1 il registro su cui deve operare e poi esegue l'operazione tra il
contenuto del registro e l'accumulatore od il nastro di output, modifcando di
conseguenza il contenuto dell'accumulatore o del nastro di output.
•
Per istruzioni RAM di salto, JUMP, JGTZ, JZERO, HALT:
M controlla se il contenuto dell'accumulatore verifca le condizioni di salto e, se
si, esegue una opportuna transizione di stato.
Analisi di complessità.
i) Ogni sequenza di transizioni relativa ad una singola operazione di RAM costa ad M,
nel caso peggiore, un tempo dell’ordine della massima lunghezza lungmax1 del nastro 1
e se la RAM opera con costo totale t allora vediamo che lungmax1 ≤ t. Infatti nel
modello a costi logaritmici:
• se sul nastro 1 è presente l' indirizzo i vuol dire che la RAM ha acceduto almeno una
volta al registro Ri e quindi ha pagato almeno una volta log i; d'altro canto l'indirizzo i
occupa sul nastro 1 proprio log i celle
• se sul nastro 1 compare il contenuto del registro i allora la RAM ha pagato almeno
una volta log(R[i]); d'altro canto R[i] occupa sul nastro 1 proprio log(R[i]) celle
ii) Se la RAM opera con costo totale t le operazioni che essa esegue sono al più t.
In conclusione la MT M opera in tempo O(t lungmax1) = O(t2).
NOTA 1
• Tutto ciò che si può fare (calcolo di funzioni, riconoscimento o accettazione di
linguaggi, ecc.) con una MT si può fare anche con una RAM e viceversa (adottando
le opportune convenzioni per la rappresentazione dell’input e dell’output).
Considerato che le RAM corrispondono a semplici programmi Assembler e chiaro
che il loro potere computazionale coincide con quello dei linguaggi di
programmazione ad alto livello, in quanto un compilatore traduce un programma di
alto livello in un programma assembler.
• Tesi di Church-Turing: tutti i modelli di calcolo introdotti per defnire la calcolabilità
hanno al massimo lo stesso potere computazionale delle MT.
NOTA 2
• Una MT ed una RAM con modello a costi logaritmici possono simularsi a vicenda in
tempo polinomiale.
• Quindi per stabilire se un problema ammette una soluzione calcolabile in tempo
polinomiale possiamo indifferentemente far riferimento ad una MT o ad una RAM a
costi logaritmici.
Tesi di Cobham
Tutti i modelli di calcolo introdotti per defnire la calcolabilità in tempo polinomiale
("trattabilita' computazionale") hanno al più lo stesso potere computazionale delle
MT operanti in tempo polinomiale.
Macchine a registri elementari (MREL)
Modello di calcolo
più elementare delle RAM ma dotato dello stesso potere
computazionale di una MT o di un programma C.
Semplifcazione spinta all'estremo limite.
Semplifcazioni:
- eliminazione di nastri di ingresso e uscita
- eliminazione dell'accumulatore
- eliminazione dell'indirizzamento indiretto
Convenzioni:
- all'inizio l'input e' nei registri 1, ..., n
- tutti gli altri registri contengono 0
- al termine l'output e' nel registro 1
- la macchina si arresta se si richiede un salto ad un'istruzione che non esiste (ad
esempio all’istruzione 0).
- Due sole istruzioni di incremento/decremento del contenuto di registri:
R[i] := R[i] + 1
R[i] := R[i] – 1
(se il contenuto e' 0 il decremento lascia 0).
- Una sola istruzione di salto:
IF R[i] = 0 THEN GOTO n
(altrimenti prosegui).
Es. programma MREL per il calcolo della funzione f(x,y)=x+y:
1
2
3
4
IF R[2] = 0 THEN GO TO 0
R[2] := R[2] - 1
R[1] := R[1] + 1
IF R[3] = 0 THEN GO TO 1
(il fatto che R[3]=0 ci permette di simulare un salto incondizionato)
Es. programma MREL che simula le seguenti istruzioni di una RAM:
LOAD
ADD
STORE
1
2
1
è il seguente:
1
2
3
4
5
6
7
8
9
IF R[2] = 0 THEN GO TO 6
R[2] := R[2] - 1
R[1] := R[1] + 1
R[3] := R[3] + 1
IF R[4] = 0 THEN GO TO 1
IF R[3] = 0 THEN GO TO 0
R[3] := R[3] – 1
R[2] := R[2] + 1
IF R[4] = 0 THEN GO TO 6
// rimetto in R[2] il valore originale
Non è diffcile convincersi che, poichè ogni passo di una RAM può essere sostituito da
uno o più passi di una MREL, vale il seguente risultato.
Teorema. Ogni funzione f: N → N calcolabile con una RAM e calcolabile con una
MREL e viceversa.
Aritmetizzazione delle MREL
Stabiliamo una corrispondenza biunivoca, detta aritmetizzazione (o godelizzazione), tra
MREL e l'insieme dei numeri naturali N.
Ad ogni istruzione facciamo corrispondere un intero:
c(R[i] := R[i] + 1)
c(R[i] := R[i] - 1)
c(IF R[i] = 0 THEN GOTO n)
=
=
=
3 (i - 1) + 1
3 (i - 1) + 2
3 J(i-1,n)
(dove J e' la funzione biunivoca:
J(x,y) = [(x+y)(x+y+1)]/2+x+1
coppia di Cantor con la piccola modifca: J(0,0) = 1).
, cioè la funzione
Tecnicalità: aggiungiamo un'istruzione NOPE (che non esegue nessuna operazione) cui
facciamo corrispondere 0.
Allora ad un programma di k istruzioni:
PROG = istr1, istr2, ... , istrk
facciamo corrispondere:
c(PROG) = 2c(istr1) 3c(istr2) ... pkc(istrk) = < c(istr1), c(istr2), …., c(istrk) >
dove p1 e' 2 e pk e' il k-esimo numero primo.
Es. Al programma
IF R[2] = 0 THEN GOTO 0
R[2] := R[2] - 1
R[1] := R[1] + 1
IF R[3] = 0 THEN GOTO 1
facciamo corrispondere l'intero 29 35 51 727.
All'intero 9800 corrisponde la decomposizione 23 30 52 72 e quindi il programma:
IF R[1] = 0 THEN GOTO 0
NOPE
R[1] := R[1] - 1
R[1] := R[1] – 1
All'intero 600 corrisponde la decomposizione 23 3 52 e quindi il programma:
IF R[1] = 0 THEN GOTO 0
R[1] := R[1] + 1
R[1] := R[1] – 1
che calcola la funzione che vale 0 in 0 ed è indefnita altrove.
© Copyright 2024 ExpyDoc
