Matematica III - i modelli e le macchine astratte

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.

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.

testina0 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 REGISTROggetto

Il compito 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 dati

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;