Che materia stai cercando?

Matematica III - i modelli e le macchine astratte Appunti scolastici Premium

Appunti di Matematica III sui calcolatori elettronici per l'esame del professor Scarpetta. Gli argomenti trattati sono i seguenti: la macchina di Turing, teoria della calcolabilità, Church e Turing, l'elaborazione dell'algoritmo, il passaggio da uno stato all'altro.

Esame di Matematica III docente Prof. E. Scarpetta

Anteprima

ESTRATTO DOCUMENTO

LA MACCHINA DI TURING

La macchina di Turing costituisce un modello fondamentale ed è stato utilizzato per approfondire il concetto

stesso di algoritmo. L’idea intuitiva, infatti, potrebbe essere precisata formalmente una volta che venisse definita una

specifica macchina o come modello teorico o con riferimento ad un particolare calcolatore.

La macchina di Turing è un particolare automa, per il quale sono definiti l’insieme degli ingressi e delle uscite,

ed è previsto un apposito meccanismo di lettura (o di ingresso) e di scrittura (o di uscita) effettuati da un

meccanismo ideale su uno speciale nastro continuo. In particolare la macchina di Turing è composta da:

• una memoria, nastro ideale, visto come striscia continua di caselle, dentro le quali può esserci o un

segno dell’alfabeto, che si utilizza per rappresentare i dati o può esser vuota;

• una testina di lettura/scrittura in ogni istante posizionata sulle caselle del nastro;

• capacità di compiere azioni elaborative, spostare la testina o restare fermo, scrivere un simbolo

nella casella su cui si trova posizionata;

• un dispositivo di controllo, che in ogni istante si trova in uno stato, tra quelli definiti.

testina

0 1 0 0

... ...

nastro continuo

Dunque il modello di Turing opera similmente a quello di un automa, completato però dal meccanismo di

lettura e scrittura. Esso in particolare introduce la rappresentazione di un dato mediante stringhe di simboli o per

mezzo di una qualsiasi convenzione. L’elaborazione viene scomposta in operazioni elaborative elementari ed essa

viene completata dalla memorizzazione dei dati. In conclusione una macchina di Turing è completamente individuata

dalle seguenti informazioni:

• contenuto iniziale del nastro;

• posizione iniziale della testina;

• stato iniziale della macchina;

• tabella delle transizioni.

:

TEORIA DELLA CALCOLABILITÀ TESI DI CHURCH E TURING

Esistono macchine di Turing che terminano la loro attività arrestandosi e macchine che operano senza mai

raggiungere la terminazione. Tuttavia in base alla definizione di algoritmo ed alla sua fondamentale proprietà di essere

finito, una macchina che operi senza arrestarsi non realizza un algoritmo. Sulla base di questo è possibile dire che

una macchina di Turing che si fermi e trasformi un nastro t in un nastro t’ rappresenta l’algoritmo per l’elaborazione di

y = f(x), laddove x ed y sono rispettivamente codificati in t e t’.

Tuttavia esistono funzioni che non sono computabili da una macchina di Turing e non esistono formalismi né

macchine concrete in grado di calcolare una funzione, non elaborabile secondo Turing, poiché i diversi modelli possibili

di macchina e le macchine concrete costruite e costruibili sono equivalenti alla macchina di Turing per quanto attiene

alla capacità di calcolare problemi.

STATI E REGISTRI

Oggetto dell’informatica è anche quello di studiare e realizzare organi di memoria, vale a dire strumenti che

hanno l’onere di conservare o, per meglio dire, memorizzare degli stati. Il componente, che rende possibile

quest’operazione, si chiama registro. Il registro è composto da una serie di elementi fisici detti flip flop, essi sono

bistabili in quanto possono assumere unicamente due valori. Tipicamente l’informazione contenuta nei registri

prende il nome di bit. Il calcolatore opera su informazioni, i cui stati sono associati, secondo convenzioni o codifiche,

ai dati da rappresentare. Lo stato del registro tiene traccia dell’informazione fin quando esso non venga modificato.

IL MODELLO DI VON NEUMANN

Il modello di Von Neumann è quello più vicino all’effettiva struttura di un calcolatore ed è stato usato come

modello costruttivo dei primi calcolatori. Nel modello un sistema è costituito dalle seguenti unità:

unità di

controllo

controllo controllo

dati

unità di unità di

memoria

ingresso uscita

dati controllo

ALU

• unità di ingresso (o di input) consente la lettura dei dati in memoria in fase di esecuzione del

programma e del programma stesso in fase di caricamento;

• unità di memoria dove vengono registrate tutte le informazioni e i dati originari, intermedi e finali,

unitamente alle istruzioni del programma;

• unità di controllo (o processore) presiede a tutte le operazioni del calcolatore, interpretando le

istruzioni prelevate dalla memoria e inviate alle specifiche unità per l’esecuzione delle singole

operazioni;


PAGINE

3

PESO

72.87 KB

AUTORE

flaviael

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher flaviael di informazioni apprese con la frequenza delle lezioni di Matematica III e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Scarpetta Edoardo.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica

Geometria e Algebra - prova d'esame con soluzioni
Esercitazione
Analisi I – Corso completo
Dispensa
Teoria completa, Metodi Matematici per l'Ingegneria
Appunto
Geometria e Algebra - Determinanti
Dispensa