LA MACCHINA DI TURING
Nel 1936 il matematico inglese A. M.
Turing propose una definizione del
concetto di algoritmo tramite un modello
matematico di macchina in grado di
eseguire una computazione. Tale modello
diventò la famosa Macchina di Turing
(MdT).
Le componenti della macchina
La macchina di Turing è costituita da:
• Un nastro;
• Una testina di lettura/scrittura;
• Un’unità di memoria interna;
• Un’unità di calcolo;
• Un’unità logica;
IL NASTRO
Il nastro è lo strumento che contiene le
informazioni che dovranno essere elaborate, i
risultati intermedi e finali. Questo dispositivo è
diviso in celle, ciascuna delle quali può
contenere un solo simbolo appartenente a un
certo insieme chiamato alfabeto di lavoro,
oppure essere vuota.
TESTINA DI LETTURA/SCRITTURA
La testina di lettura/scrittura (TLS) è un
meccanismo che, posizionato su una cella del
nastro e governato da un’unità di controllo, può
leggere il simbolo che vi è contenuto e scriverne
uno appartenente all’alfabeto di lavoro, in modo
da sostituire quello che ci fosse stato prima e
spostarsi a destra o a sinistra o restare ferma. La
sequenza di simboli è delimitato da un carattere
speciale sia a destra che a sinistra.
UNITA’ DI CONTROLLO
Per impartire i comandi alla TLS, la MdT è
provvista di un’unità di controllo che inoltra i
seguenti ordini:
• Fermo;
• Spostati a sinistra e analizza la cella;
• Spostati a destra e analizza la cella;
Questi tre elementi costituiscono l’insieme dei
simboli di movimento.
UNITA’ LOGICA
L’unità logica decide i passi che la macchina deve
compiere, e per fare questo necessità di due
ingressi:
• Il contenuto della cella sulla quale è
posizionata la TLS;
• Lo stato della macchina in quell’istante;
Questi due valori definiscono il comportamento
della MdT. (esempio pag. 179 libro A)
TURING E LA SUA INVENZIONE
Benvenuti Marco 3°A Info