La versione più recente è stata modificata il 2006-06-22 00:12:34 da FulVio
Aggiunzioni:
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.
Omissioni:
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 23:33:25 da GaS
Aggiunzioni:
Omissioni:
QUA SERVIREBBE INFILARE L'IMMAGINE 1.4
Modificato il 2006-03-07 22:30:17 da GaS
Aggiunzioni:
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.
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.
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Omissioni:
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.
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.
QUA SERVIREBBE INFILARE L'IMMAGINE 1.4
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
Omissioni:
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, r0, r1, ..., ri, ..., 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 r0, 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.
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.
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 x1, x2, ..., xn 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(x1, x2, ..., xn) = y. E' mostrato chiaramente che una RAM, come ogni altro ragionevole modello di computer, può computare esattamente le funzioni ricorsive parziali. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 22:19:21 da GaS
Aggiunzioni:
1. la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
Modificato il 2006-03-07 22:18:10 da GaS
Aggiunzioni:
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, r0, r1, ..., ri, ..., 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:
1.la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
2.gli interi utilizzati nella computazione sono piccoli abbastanza da poter essere contenuti in un'unica stringa
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 r0, 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:
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.
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 x1, x2, ..., xn 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(x1, x2, ..., xn) = y. E' mostrato chiaramente che una RAM, come ogni altro ragionevole modello di computer, può computare esattamente le funzioni ricorsive parziali. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Omissioni:
Work in progress...
La versione più vecchia di questa pagina è stata modificata il 2006-03-07 22:13:05 da GaS []
Work in progress...
Torna ad Algoritmi e Strutture dati
Aggiunzioni:
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.
Omissioni:
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 23:33:25 da GaS
Aggiunzioni:
Omissioni:
QUA SERVIREBBE INFILARE L'IMMAGINE 1.4
Modificato il 2006-03-07 22:30:17 da GaS
Aggiunzioni:
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.
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.
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Omissioni:
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.
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.
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 22:29:04 da GaS
Aggiunzioni:
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: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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 22:29:04 da GaS
Aggiunzioni:
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.
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.
QUA SERVIREBBE INFILARE L'IMMAGINE 1.4
1. =i, indicando l'intero i stesso.
2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i.
Se j < 0, allora la macchina si arresta.
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).2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i.
Se j < 0, allora la macchina si arresta.
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:v(=i) = i
v(i) = c(i)
v(*i) = c(c(i))
v(i) = c(i)
v(*i) = c(c(i))
QUA SERVIREBBE INFILARE L'IMMAGINE 1.5
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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
QUA SERVIREBBE INFILARE IL RESTOSupponiamo 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. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Omissioni:
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, r0, r1, ..., ri, ..., 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 r0, 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.
1. =i, indicando l'intero i stesso.
2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
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).2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
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:
v(=i) = i
v(i) = c(i)
v(*i) = c(c(i))
v(i) = c(i)
v(*i) = c(c(i))
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 x1, x2, ..., xn 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(x1, x2, ..., xn) = y. E' mostrato chiaramente che una RAM, come ogni altro ragionevole modello di computer, può computare esattamente le funzioni ricorsive parziali. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Modificato il 2006-03-07 22:19:21 da GaS
Aggiunzioni:
1. la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
2. gli interi utilizzati nella computazione sono piccoli abbastanza da poter essere contenuti in un'unica stringa
1. =i, indicando l'intero i stesso.
2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
Omissioni:
1.la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
2.gli interi utilizzati nella computazione sono piccoli abbastanza da poter essere contenuti in un'unica stringa1. =i, indicando l'intero i stesso.
2. Un intero non negativo i, indicando il contenitore di registro i.
3. *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
Omissioni:
1.la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
- =i, indicando l'intero i stesso.
- Un intero non negativo i, indicando il contenitore di registro i.
- *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
Modificato il 2006-03-07 22:18:10 da GaS
Aggiunzioni:
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.
1.la taglia del problema è piccola abbastanza da poter essere contenuta nella memoria principale di un computer
2.gli interi utilizzati nella computazione sono piccoli abbastanza da poter essere contenuti in un'unica stringa
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 r0, 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:
- =i, indicando l'intero i stesso.
- Un intero non negativo i, indicando il contenitore di registro i.
- *i, indicando un indirizzamento indiretto. In questo, l'operatore è il contenitore del registro j, dove j è l'intero trovato nel registro i. Se j < 0, allora la macchina si arresta.
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:
v(=i) = i
v(i) = c(i)
v(*i) = c(c(i))
v(i) = c(i)
v(*i) = c(c(i))
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 x1, x2, ..., xn 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(x1, x2, ..., xn) = y. E' mostrato chiaramente che una RAM, come ogni altro ragionevole modello di computer, può computare esattamente le funzioni ricorsive parziali. Ciò significa, dando qualche funzione parziale ricorsiva f possiamo definire un programma RAM che computa f, e dando un qualsiasi programma RAM possiamo definire una funzione parziale ricorsiva equivalente.
Omissioni:
Work in progress...
La versione più vecchia di questa pagina è stata modificata il 2006-03-07 22:13:05 da GaS []
Vista della pagina:
1.2 Macchine ad accesso random (RAM – Random Access Machines)
Work in progress...
Torna ad Algoritmi e Strutture dati
