Il concetto di sistema automatico di calcolo è rappresentato in modo semplice da un modello di macchina astratta proposto nel 1936 dal matematico inglese Alan M. Turing (1912-1954). Il modello fa riferimento alla comune attività mentale dell'uomo quando è impegnata nella risoluzione di algoritmi di calcolo: di solito si usano un foglio e una penna con la quale segnare sul foglio i dati e i simboli delle operazioni; il lavoro è controllato dalla mente umana, per la quale la carta costituisce il supporto di memoria (il foglio dei calcoli oppure il foglio del libro che contiene le regole di calcolo).
La Macchina di Turing (MdT) può essere definita intuitivamente come un dispositivo di calcolo in grado di operare, mediante una successione finita di passi discreti e secondo determinate regole (programma), su un numero finito di simboli, facendo astrazione dai limiti di spazio, di tempo (durata dell'elaborazione) e da possibili errori di calcolo.
È importante sottolineare come l'attenzione di Turing fosse rivolta al processo di calcolo, indipendentemente da come esso avveniva fisicamente. In modo rigoroso, infatti, una MdT è un dispositivo astratto, cioè indipendente da ogni sua possibile realizzazione fisica.
Anche se si tratta di una pura astrazione matematica, la Macchina di Turing rappresenta ancora oggi un fondamentale strumento logico-concettuale e può essere considerata il punto di partenza per tutti gli studi che portarono alla realizzazione dei calcolatori programmabili.
Dal punto di vista concettuale la Macchina di Turing può essere considerata come un dispositivo composto da tre elementi:
• Nastro infinito;
• Testina di lettura/scrittura (TLS);
• Meccanismo di controllo.
Il nastro di lunghezza infinita è la memoria principale della Macchina di Turing: esso possiede un numero infinito di caselle e ogni casella può contenere solo un simbolo appartenente a un alfabeto finito di simboli.
La testina di lettura/scrittura permette di scrivere o leggere sul nastro, accedendo ad una sola casella per volta.
Il meccanismo di controllo può essere identificato come un automa, perché è in grado di assumere uno tra un numero finito di stati e di svolgere una delle seguenti operazioni elementari:
• comandare la scrittura di un simbolo nella casella sotto la TLS;
• comandare lo spostamento della TLS sulla casella di destra o su quella di sinistra, oppure arrestarne il movimento;
• comandare la sostituzione dello stato attuale con quello successivo.
In sostanza, durante il suo funzionamento la macchina evolve da una configurazione all'altra: in corrispondenza del simbolo letto sul nastro e dello stato in cui si trova, viene determinato il simbolo che viene scritto sul nastro, lo stato successivo della macchina e il movimento della testina. All'inizio del processo di elaborazione sul nastro si trova la sequenza dei simboli di input e, al verificarsi della terminazione, si trova l'output del procedimento eseguito.
____________________________
Nessun commento:
Posta un commento
Lascia un tuo commento!