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 2025 ExpyDoc