Storia Mdt

La Macchina di Turing fu ideata nel 1939 da Alan Turing con l'aiuto di altri scienziati inglesi che contribuì al successo degli alleati nella Seconda Guerra Mondiale: questa rese possibile la decifrazione dei messaggi cifrati tedeschi usati per comunicare ai sommergibili gli obbiettivi da colpire, il cosiddetto sistema Enigma. La Macchina era ed é un vero e proprio computer che può manipolare qualsiasi informazione con estrema precisione. In sostanza poteva leggere,scrivere,memorizzare ed elaborare qualunque informazione. La grande valenza della Macchina di Turing fu quella di dimostrare che nessun sistema in grado di trattare informazioni, comunque fosse fatto e qualunque cosa sapesse fare,sarebbe potuto essere più preciso.
Una macchina di Turing non è una macchina fisica ma un modello di macchina ideale consistente in:un nastro infinito(che rappresenta la memoria della macchina)in entrambe le direzioni, diviso in caselle;una testina che può leggere il simbolo contenuto in una casella e scrivere il simbolo in una casella muovendosi lungo il nastro, una casella per volta.
Grazie alla Macchina,Turing è considerato da molti il padre dell'informatica. Secondo quest'ultimo infatti sarebbe stato possibile inventare una macchina che potesse essere utilizzata per una qualsiasi sequenza computabile. La novità di questa teoria è La dimostrazione che una macchina poteva essere codificata come un numero e viceversa, introducendo il concetto che oggi chiameremmo "software".Però i computer di oggi non si basano su questo modello perchè sarebbero molto lenti e inefficenti; ma su un modello ideato da John Von Neumann che nel 1953 realizzò il primo calcolatore progammabile.
Prima della fine della guerra Alan Turing si rese conto che se avesse avuto i finanziamenti necessari avrebbe portato a termine il progetto della sua macchina universale, ma i burocrati non furono abbastanza capaci di intuire il vantaggio che poteva derivare dalla costruzione di una simile invenzione. Inoltre nel 1952 Turing fu condannato per omossesualità, un fatto considerato grave a quei tempi. La pena stabilita fu la castrazione chimica che gli evitò la galera, ma all,età di soli 42 anni si è suicidato mangiando una mela ricca di cianuro; per questo motivo la macchina di Turing è rimasta solo come modello teorico.
Le caratteristiche:
La macchina di Turing possiede un’unita‘ di elaborazione centrale (CPU, dall’inglese Central Processing Unit) e una memoria su cui poter leggere e scrivere. In particolare, la CPU e` composta da un registro di stato, contenente lo stato attuale della macchina, e da un programma contenente le istruzioni che essa deve eseguire. La memoria di una macchina di Turing e` composta da un nastro infinito, suddiviso in celle e al quale la CPU puo` accedere attraverso una testina di lettura/scrittura .Inizialmente, il nastro contiene la stringa di input preceduta e seguita da una serie infinita di simboli vuoti, la testina e` posizionata sul primo simbolo della stringa di input e la CPU si trova in uno stato speciale, detto stato iniziale. Sulla base dello stato in cui si trova la CPU e del simbolo letto dalla testina, la macchina esegue un’istruzione del programma che puo` modificare il simbolo attualmente scandito dalla testina, spostare la testina a destra oppure a sinistra e cambiare lo stato della CPU. La macchina prosegue nell’esecuzione del programma fino a quando la CPU non viene a trovarsi in uno di un insieme di stati particolari, detti stati finali, oppure non esistono istruzioni del programma che sia possibile eseguire. Nel caso in cui il programma termini perche è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito diviso in caselle. Ad ogni istante di tempo t1, la macchina si trova in uno stato interno s1 ben determinato. Essa può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben alfabeto finito; essa è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo e ad ogni istante si può trovare in uno stato interno ben determinato che fa parte di un insieme finito di stati. Inizialmente sul nastro viene posta una stringa rappresentante i dati che caratterizzano il problema sottoposto alla macchina. La macchina è dotata anche di un repertorio finito di istruzioni che determinano il suo sviluppo ("evoluzione")in conseguenza dei dati iniziali. L’evoluzione si sviluppa per passi successivi che corrispondono a una sequenza di istanti successivi.Ogni passo viene determinato dallo stato attuale s nel quale la macchina si trova e dal carattere c che la testina di I/O trova sulla casella del nastro su cui è posizionata e si manifesta nella modifica del contenuto della casella, nell'eventuale spostamento della testina in una posizione verso destra o verso sinistra e nell'eventuale cambiamento dello stato. Quali azioni vengono effettuate ad ogni passo vengono determinate dall'istruzione, che supponiamo unica, che ha come prime due componenti s e c; le altre tre componenti dell'istruzione forniscono nell'ordine:il nuovo stato, il nuovo carattere e una richiesta di spostamento verso sinistra, nullo o verso destra.

Ecco alcuni esempi semplici per capirne di più:
1. Costruisci una macchina di Turing che sia capace di effettuare una somma.

(0,0..9,0,0..9,>)
(0,-,1,-,<)
(1,0..9,2,-,<)
(2,0..9,3,-,<)
(3,0..9,0,-,<)

2. Costruisci una macchina di Turing che data una sequenza di A e B, sia capace di cambiare le A in B, e viceversa.

(0,A,0,B,>)
(0,B,0,A,>).

Salvo diversa indicazione, il contenuto di questa pagina è sotto licenza Creative Commons Attribution-ShareAlike 3.0 License