UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modelli per l’Informatica Prof. Michele Amoretti Fondamenti di Informatica a.a. 2007/2008 Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Sommario • Che cosa è un modello? • L’uso dei modelli in campo scientifico ed ingegneristico • Modelli per l’informatica • Livelli di descrizione • Automi e Macchine di Turing • Modello di Von Neumann Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Che cosa è un modello? I modelli sono uno strumento importante per studiare molti fenomeni fisici e sociali. Sistemi meteorologici, cicli climatici, diffusione di epidemie, sviluppi demografici e molecole chimiche sono esempi di sistemi e fenomeni studiati tramite modelli. Un modello di tali fenomeni: 1. cattura l’essenza, cioè le proprietà principali, dell’oggetto reale; 2. probabilmente differisce in scala dall’oggetto reale; 3. è privo di alcuni dettagli dell’oggetto reale; 4. manca di alcune funzionalità dell’oggetto reale. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Che cosa è un modello? Che cosa si può guadagnare studiando modelli, se questi non si comportano esattamente come gli oggetti reali che rappresentano? Da un lato, i modelli possono migliorare la nostra comprensione del sistema reale a cui si riferiscono. Cambiando un aspetto nel modello possiamo vedere immediatamente gli effetti della modifica. Tali modifiche potrebbero essere molto costose, difficili o pericolose da apportare nel fenomeno reale. Il vantaggio è che i modelli ci offrono un ambiente sicuro e controllato per verificare delle ipotesi, per controllare quale potrebbe essere l’effetto provocato da una modifica di un fattore nel sistema reale. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Che cosa è un modello? I modelli possono anche fornire ambienti per apprendere e interagire con vari sistemi. Un simulatore di volo, ad esempio, può fornire all’aspirante pilota un’esperienza realistica in un ambiente privo di rischi. Infine, i modelli non solo ci forniscono informazioni su fenomeni esistenti, ma possono anche essere usati come strumenti di progettazione. Un modello di un nuovo progetto potrebbe mettere in rilievo dei difetti senza sprecare tempo, soldi e correre eventuali rischi nella costruzione di un prototipo. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica L’uso dei modelli in campo scientifico ed ingegneristico E’ spesso impossibile o poco pratico, nella maggior parte dei campi dell’ingegneria, verificare se la soluzione di un problema sia adeguata o meno, applicandola direttamente al mondo reale. la fase di progetto di fonda sull’uso di modelli Modelli fisici: osservazioni e misure su una riproduzione (spesso in scala ridotta) del sistema reale che deve essere progettato. Modelli formali: operazioni su oggetti matematici che rappresentano le astrazioni delle entità reali che devono essere modellate. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica L’uso dei modelli in campo scientifico ed ingegneristico I modelli formali consentono all’utente di applicare il rigore del ragionamento matematico per dedurre le proprietà delle entità modellate. Es. un insieme di equazioni matematiche può descrivere la struttura di un ponte e le forze ad esso applicate: dopo aver risolto tali equazioni il progettista può prevedere gli sforzi interni della struttura. I modelli formali richiedono: 1. la formalizzazione del problema 2. la risoluzione del problema mediante gli strumenti offerti dal formalismo scelto 3. l’interpretazione dei risultati ottenuti dal modello, allo scopo di dedurre e valutare le scelte di progetto Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica L’uso dei modelli in campo scientifico ed ingegneristico Al di fuori di quello ingegneristico, negli altri campi della scienza l’impiego dei modelli è generalmente più orientato verso l’interpretazione della realtà piuttosto che verso la progettazione. Un modello è adeguato se i risultati ottenuti, sperimentando o ragionando su di esso, riflettono proprietà osservabili del fenomeno in corso di studio, ovviamente entro limiti di approssimazione accettabili. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modelli per l’informatica I modelli giocano un ruolo fondamentale per l’informatica. In molte applicazioni, i programmi per calcolatori vengono progettati allo scopo di sostituire procedure manuali. Quindi i progettisti del software devono “riprodurre” o “imitare” il comportamento essenziale della procedura manuale: il programma è quindi un modello di tale procedura manuale. La produzione del software non consiste comunque solo nella programmazione. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modelli per l’informatica Il programma può essere considerato come modello formale di una attività automatizzabile. L’ingegneria del software si è diretta verso l’impiego di linguaggi formali in tutte le fasi di produzione del software. La formalità è richiesta per migliorare l’affidabilità e la facilità di manutenzione dei programmi, ma anche per consentire l’impiego di strumenti automatici di supporto alla produzione del software. Elementi chiave dell’ingegneria del software: accurata analisi dei requisiti - il documento di specifica dei requisiti è un modello che enfatizza il comportamento esterno del sistema analisi funzionale - il documento di specifica funzionale è un modello che tiene conto della struttura complessiva del software e astrae dai dettagli interni di ciascun modulo Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modelli per l’informatica L’astrazione e la costruzione di modelli svolgono un ruolo fondamentale anche nella comprensione e nel progetto dei sistemi di elaborazione (intesi come insieme di hardware e software). Ogni sistema di elaborazione deve essere in grado di: 1. accettare informazioni in ingresso; 2. memorizzare informazioni e caricarle dalla memoria; 3. eseguire azioni in base alle istruzioni di un algoritmo; la scelta di quale azione intraprendere può dipendere dallo stato attuale dell’elaboratore stesso, oltre che dall’elemento di ingresso elaborato; 4. produrre informazioni in uscita. Naturalmente un computer reale ha tutte queste capacità ed è un esempio di sistema di elaborazione, come un essere umano e un videoregistratore programmabile. Quest’ultimo, tuttavia, ha un insieme molto limitato di operazioni primitive che può eseguire, e quindi può eseguire algoritmi molto limitati. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modelli per l’informatica Il computer, benché abbia un insieme limitato di istruzioni primitive, è un sistema di calcolo “generale” perché tali primitive possono essere combinate e organizzate per svolgere attività complesse. • • Primitive di sistema: funzionalità che il sistema operativo mette a disposizione delle applicazioni Primitive di basso livello: funzionalità messe a disposizione del sistema operativo (es. driver per il controllo delle periferiche) Le “operazioni primitive” disponibili agli esseri umani non sono ancora tutte note, ma per molti aspetti sembrano superare quelle di computer, e potremmo certamente classificare l’essere umano come un sistema di calcolo generale. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livelli di descrizione Per poter usare un programma di elaborazione testi su di un PC, l’utente può considerare quast’ultimo come una macchina da scrivere sofisticata, dotata di una tastiera, di uno schermo video e di una stampante. Il progettista del programma di elaborazione testi, invece, richiede una visione del sistema molto più dettagliata, anche se non ha ancora la necessità di rappresentarlo a livello di circuiti hardware. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livelli di descrizione Esistono innumerevoli sistemi per cui coesistono più livelli di descrizione. Es. Noi esseri umani siamo composti da un numero enorme di cellule e tutto ciò che facciamo potrebbe essere descritto in termini di di cellule, o addirittura a livello molecolare. In pratica però non c’è modo di collegare una descrizione microscopica con ciò che sentiamo di essere. livelli distanti Es. Il modo di percepire la scacchiera da parte di un maestro di scacchi è completamente diverso da quello di un principiante. Il maestro letteralmente non vede le mosse cattive, proprio come un dilettante non vede le mosse illecite. Con un po’ di pratica, è possibile avvicinarsi al modo di vedere la scacchiera del mestro. livelli vicini Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livelli di descrizione I calcolatori sono sistemi in cui tutti i livelli di descrizione sono vicinissimi tra loro. Il livello più basso che analizzeremo è quello funzionale, nel quale troveremo una memoria, una unità centrale di elaborazione (la CPU) e alcune apparecchiature di ingresso e di uscita (I/O). Vedremo che la memoria è suddivisa in pozioni fisiche distinte dette parole, e che una parola a sua volta è suddivisa in quelli che possono essere considerati gli atomi dell’informatica, i bit. Attenzione! Non c’è ragione di pensare che un insieme di bit rappresenti sempre un numero in base 2. Un insieme di bit può anche rappresentare un’immagine, le lettere di un testo, ecc. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello fisico-tecnologico Progetto esecutivo che consente la realizzazione tecnologica. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello elettronico Gli elementi primitivi sono i componenti elettronici (transistor, resistenze, capacità, generatori di tensione e di corrente, ecc.). NOT Modelli per l’Informatica NAND NOR Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello logico (o porta, o gate) Il sistema è descritto da un insieme di elementi primitivi che realizzano semplici operazioni in logica booleana (NOT, NAND, NOR, ecc) ma anche da elementi più complessi (FLIP-FLOP) che assieme ai primi compongono reti logiche più o meno complesse. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello registro (RTL) Il sistema è descritto in termini di blocchi circuitali di complessità media (registri, unità aritmetico logiche, ecc.) che operano su gruppi di bit (parole). Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello funzionale Il sistema è descritto da un insieme di elementi primitivi definiti da caratteristiche di comportamento o funzionali (processori, memorie, …). disco CPU Memoria I/O bus Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Livello software Questo livello include: • i driver delle periferiche • il kernel del sistema operativo • le librerie di sistema • le applicazioni (di tipo office, videogame, ecc.) I primi calcolatori erano programmati direttamente in linguaggio macchina (istruzioni e dati codificati in sequenze di bit). La definizione di famiglie architetturali ha permesso lo sviluppo di applicazioni portabili scritte in linguaggio assembly. Dagli anni ’70 in poi sono stati introdotti linguaggi di sempre più alto livello (Fortran, C, C++, Java, ecc.), indipendenti dalla specifica famiglia architetturale. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Automi e Macchine di Turing Normalmente pensiamo al “calcolo automatico” come a una disciplina recente legata ai computer, ma l’interesse nella natura teorica del calcolo automatico risale a molto tempo prima dei computer moderni. Verso la fine del diciannovesimo secolo i matematici erano interessati a formalizzare la natura delle dimostrazioni, con due obiettivi: - definire una base formale per le dimostrazioni matematiche avrebbe garantito la correttezza di una dimostrazione; - eseguire la prova automatica di teoremi, con dimostrazioni corrette generate semplicemente seguendo una serie di regole. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Automi e Macchine di Turing Nel 1931 il logico austriaco Kurt Gödel esaminò i sistemi formali per descrivere l’aritmetica dei numeri e dimostrò che In ogni teoria matematica T sufficientemente espressiva da contenere l'aritmetica, esiste una formula φ tale che, se T è coerente, allora né φ né la sua negazione ¬φ sono dimostrabili in T. Questo portò a cercare con interesse un metodo per riconoscere quali proposizioni sono indimostrabili in un sistema formale, ovvero una procedura di calcolo (ciò che abbiamo chiamato algoritmo) per individuare tali proposizioni. Ciò a sua volta condusse a un esame della natura delle procedure di calcolo, con modelli di sistemi di elaborazione per eseguire tali procedure. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Automa a Stati Finiti L’ASF è il modello più semplice e il più usato in campo informatico. Intuitivamente, un ASF rappresenta un sistema che può trovarsi in un numero finito di stati diversi. Come conseguenza di qualche ingresso, che può variare su un insieme finito di possibili valori, l’ASF effettua una transizione da uno stato ad un altro. Definizione formale: Un 1. 2. 3. ASF è una tripla <Q,I,δ>, dove Q è un insieme finito di stati I è un insieme finito di simboli di ingresso δ:Q×IQ è la funzione di transizione Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Automa a Stati Finiti La funzione di transizione è una funzione con dominio finito, in quanto finiti sono l'alfabeto di input e l'insieme degli stati che l'automa può assumere, per cui essa può venire rappresentata con una tabella detta tabella delle transizioni. Una rappresentazione molto più evocativa di un ASF è costituita dal diagramma degli stati, in cui l'automa è rappresentato mediante un grafo orientato, dove i nodi rappresentano gli stati, mentre gli archi rappresentano le transizioni, per cui sono etichettati con il carattere la cui lettura determina la transizione dallo stato corrente al successivo. Il diagramma degli stati permette di identificare anche lo stato iniziale e gli stati finali dell'automa: lo stato iniziale è rappresentato da un nodo con una freccia entrante, mentre gli stati finali sono individuati da un nodo con doppio circolo. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a Stati Finiti Un TSF è un ASF con stato iniziale, uno o più stati finali, e dotato di uscita. Definizione formale: Un 1. 2. 3. 4. 5. 6. 7. TSF è una 7-upla <Q,I,δ,q0,F,O,η>, dove Q è un insieme finito di stati I è un insieme finito di simboli di ingresso δ:Q×IQ è la funzione di transizione q0 in Q è lo stato iniziale F in Q è l’insieme degli stati finali O è l’insieme finito dei simboli di uscita η:Q×IO è la funzione di uscita Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a Stati Finiti Esempio Robot assemblatore che riceve piattini e tazzine su un nastro di ingresso e deve mettere assemblati del tipo “tazzina su piattino” su un nastro di uscita. Regole: 1. Se entrambe le mani sono libere, il robot prende l’oggetto in ingresso (piattino o tazzina) con la mano sinistra. 2. Se il robot ha già un oggetto nella mano sinistra, il nuovo oggetto in arrivo deve essere di tipo diverso e viene preso con la mano destra. 3. Il robot depone la tazza sul piatto e li manda in uscita. 4. Quando termina la sequenza di oggetti in ingresso, il robot deve avere entrambe le mani libere. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a Stati Finiti Esempio Robot assemblatore che riceve piattini e tazzine su un nastro di ingresso e deve mettere assemblati del tipo “tazzina su piattino” su un nastro di uscita. TSF che modella il robot: t = tazzina p = piattino a = assemblato Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Automa a Pila Un automa a pila (AP) è un ASF arricchito di una memoria ausiliaria strutturata come una pila. I simboli possono essere inseriti ed estratti dalla pila secondo una politica “last-in-first-out” (LIFO), ossia l’ultimo simbolo inserito in pila è il primo che viene tolto. Definizione formale: Un 1. 2. 3. 4. 5. 6. TSF è una 6-upla <Q,I,δ,q0,F,O,η>, dove Q è un insieme finito di stati I è un insieme finito di simboli di ingresso Γ è un insieme finito di simboli ausiliari δ:Q×I×ΓQ×Γ è la funzione di transizione q0 in Q è lo stato iniziale Z0 in Γ è il simbolo iniziale della pila Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a Pila Un trasduttore a pila (TP) è un AP dotato di uscita. Definizione formale: Un 1. 2. 3. 4. 5. 6. 7. 8. 9. TP è una 9-upla <Q,I,δ,q0,F,O,η>, dove Q è un insieme finito di stati I è un insieme finito di simboli di ingresso Γ è un insieme finito di simboli ausiliari δ:Q×I×ΓQ×Γ è la funzione di transizione q0 in Q è lo stato iniziale Z0 in Γ è il simbolo iniziale della pila F in Q è l’insieme degli stati finali O è l’insieme finito dei simboli di uscita η :Q×I×ΓO è la funzione di uscita Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a pila Esempio Ancora il robot assemblatore di piattini e tazzine: se ha già in mano un piatto e ne riceve un altro, non è in grado di accettarlo e si ferma. Soluzione: dotiamo il robot di una pila (inizialmente vuota). Regole: 1. Se il robot ha in mano un oggetto e ne riceve un altro dello stesso tipo, depone quello nuovo sulla cima della pila. 2. Se il robot ha in mano un oggetto e ne riceve uno di un altro tipo, crea un assemblato e lo pone sul nastro di uscita. 3. Se il robot ha le mani libere e riceve un oggetto e la pila contiene oggetti di tipo diverso, il robot ne prende uno dalla cima della pila, crea un assemblato e lo pone sul nastro di uscita. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Trasduttore a pila Esempio Ancora il robot assemblatore di piattini e tazzine: se ha già in mano un piatto e ne riceve un altro, non è in grado di accettarlo e si ferma. Soluzione: dotiamo il robot di una pila (inizialmente vuota). NOTA! La pila in ogni istante non contiene contemporaneamente tazzine e piattini, ma solo oggetti dello stesso tipo. NOTA! Se la pila ha capacità infinita, nessun ASF può modellare questo nuovo robot che ha un numero infinito di stati possibili. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing I TP sono più potenti dei TSF, nel senso che possono risolvere tutti i problemi risolubili dai TSF ed anche alcuni problemi che gli ASF non riescono a risolvere. Anche i TP però hanno i loro limiti, essenzialmente dovuti alla rigida politica LIFO con la quale viene gestita la memoria a pila. Un modello ancora più potente è la macchina di Turing (MT), che qui descriviamo nella versione multinastro (o a k nastri). un nastro di ingresso TI un nastro di uscita TO k nastri di memoria T1,..,Tk un dispositivo di controllo dotato di un numero finito di stati Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Ciascun nastro è una sequenza di celle ed è infinito a destra. Ciascuna cella contiene un unico simbolo scelto all’interno di un insieme finito di siboli del nastro, contenente tra gli altri anche il cosiddetto spazio vuoto (blank). Ciascun nastro è dotato di una testina che può leggere, scrivere, muoversi a destra, muoversi a sinistra e rimanere ferma. La testina TI non può scrivere. La testina TO non può né leggere né muoversi verso sinistra. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing La macchina di Turing è progettata per svolgere le seguenti operazioni: 1. cambia lo stato del dispositivo di controllo; 2. stampa nuovi simboli sopra i simboli correnti nelle celle sottostanti alla testina (esclusa quella di TI , che può solo leggere e spostarsi); 3. muove una o tutte le testine, indipendentemente l’una dall’altra, di una cella a destra (R) o a sinistra (L) o rimane ferma (S), esclusa la testina TO che non può muoversi a sinistra. In alternativa, la macchina non effettua alcuna operazione o si ferma definitivamente. I dettagli delle azioni (che cosa scrivere, qual è il nuovo stato e in quale direzione spostare le testine) dipendono dallo stato corrente del dispositivo di controllo e dal contenuto della cella letta (l’ingresso). Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Una configurazione di una MT a k nastri è composta dallo stato dell’unità di controllo, dal contenuto dei k+2 nastri e dalla posizione delle k+2 testine. La configurazione iniziale: l’unità di controllo si trova nello stato iniziale; il nastro di ingresso contiene un numero finito di simboli non vuoti; i nastri di memoria contengono un simbolo speciale Z0 nella loro prima cella e nessun altro simbolo non vuoto; il nastro di uscita è vuoto; le testine sono posizionate sulla prima cella dei rispettivi nastri. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Esempio Un robot che mette insieme una sequenza di piatti grandi (g), piattini (p) e tazzine (t). Regole: 1. Riceve tutti gli oggetti da un nastro e pone ciascun oggetto in cima a tre pile diverse, una per i g, una per i p e una per le t. 2. Dopo aver ricevuto tutti gli oggetti, estrae un g, un p e una t da ciascuna pila e produce un assemblato (a). 3. Alla fine delle sue operazioni verifica che tutte le pile siano vuote. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Esempio Un robot che mette insieme una sequenza di piatti grandi (g), piattini (p) e tazzine (t). Il dispositivo di controllo della MT che modella questo sistema ha 5 stati: - q0 (stato iniziale) - qR (stato di lettura dal nastro in ingresso) - qW (stato di scrittura sul nastro di uscita) - qA (stato finale di accettazione) - qE (stato finale di errore) La MT ha anche tre nastri di memoria T1, T2 e T3, oltre ovviamente ai nastri di ingresso e uscita (TI e TO). Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Esempio Un robot che mette insieme una sequenza di piatti grandi (g), piattini (p) e tazzine (t). Funzionamento della MT: - Inizialmente la MT è in q0, e passa in qR lasciando inalterati i simboli Z0 sui nastri di memoria. Non legge nulla da TI e non muove le testine di TI e TO. - Quando la MT è in qR e legge g, p oppure t dal nastro TI, rimane in qR e scrive i simboli di ingresso nel nastro di memoria opportuno. Le testine di TI e dei nastri di memoria vengono quindi mosse verso destra, mentre la testina di TO resta ferma. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Esempio Un robot che mette insieme una sequenza di piatti grandi (g), piattini (p) e tazzine (t). Funzionamento della MT: - Quando la MT è in qR e legge un simbolo vuoto da TI, significa che tutti gli oggetti in ingresso sono stati prelevati. La testina di TI non si muove più, la MT commuta a qW, sposta a sinistra le testine dei nastri di memoria, e non scrive nulla su TO. - Quando la MT è in qW e legge i simboli g, p e t dai nastri di memoria, rimane in qW. Scrive un simbolo vuoto al posto del simbolo letto e sposta le testine verso sinistra. Inoltre scrive una a su TO e muove la sua testina verso destra. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Esempio Un robot che mette insieme una sequenza di piatti grandi (g), piattini (p) e tazzine (t). Funzionamento della MT: - Quando la MT è in qW e legge Z0 da tutti i registri di memoria, significa che è stato ricevuto un ugual numero di g, p e t e che sono stati tutti assemblati. La MT passa nello stato qA, scrive un simbolo vuoto al posto di Z0 sui nastri di memoria e scrive il carattere Y (successo) su TO e si ferma. - in tutti gli altri casi, la MT entra nello stato di errore qE, scrive il carattere N (fallimento) su TO e si ferma. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Macchina di Turing Si dice macchina di Turing universale (termine che abbreviamo con MTU) una MT capace di simulare le evoluzioni di ogni MT. Si può dire che il primo segmento del nastro della MTU contiene il particolare "programma" che le consente di simulare la particolare MT. La MTU è quindi un modello di computer a programmazione interna, che (a un livello di astrazione più basso) è stato definito da John Von Neumann. La MTU rappresenta un sistema di elaborazione generale, nel senso che può seguire diverse serie di istruzioni (programmi) e quindi risolvere problemi di varia natura. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modello di Von Neumann Quello di Von Neumann è il principale modello di progettazione dei calcolatori elettronici. Ha una unità di elaborazione centrale (CPU) e una struttura di memoria che immagazzina sia i dati che le istruzioni. Il modello di Von Neumann implementa una macchina di Turing universale, ed è il modello di riferimento per la specifica delle architetture sequenziali, cioè dei sistemi di elaborazione in cui le istruzioni vengono eseguite una dopo l’altra. Modelli per l’Informatica Prof. M. Amoretti UNIVERSITA’ DEGLI STUDI DI PARMA Corso di Laurea in Ingegneria Gestionale Fondamenti di Informatica Modello di Von Neumann Lo schema si basa su cinque componenti fondamentali: 1. 2. 3. 4. 5. CPU o unità di lavoro che si divide a sua volta in 1. Unità operativa, nella quale uno dei sottosistemi più rilevanti è l'ALU (Arithmetic Logic Unit) 2. Unità di controllo Unità di memoria, intesa come memoria di lavoro o memoria principale (RAM, Random Access Memory) Unità di input, tramite la quale i dati vengono inseriti nel calcolatore per essere elaborati Unità di output, necessaria affinché i dati elaborati possano essere restituiti all'operatore Bus, un canale che collega tutti i componenti fra C P U loro All'interno dell'ALU è presente un registro detto accumulatore, che fa da buffer tra input e output grazie a una speciale istruzione che carica una parola dalla memoria all'accumulatore e viceversa. Modelli per l’Informatica Prof. M. Amoretti