La Macchina di Turing, è un’apparecchiatura in grado di manipolare dati di un nastro dalla lunghezza potenzialmente infinita (stando a delle regole prefissate), resa celebre da “The Imitation Game” (biografia cinematrografica di Alan Turing, con Benedict Cumberbacht e Keira Knightley) ed utilizzata nella “teoria della calcolabilità” e nello “studio della complessità degli algoritmi”.
Essa deve la sua nascita al lavoro del matematico e crittografo inglese Alan Turing, considerato tutt’ora uno dei padri dell’informatica e matematico tra i più influenti del 900: dopo la laurea all’Università di Cambridge (con il massimo dei voti) scrisse nel 1936, un articolo denominato “On computable Numbers, with an application to the Entscheidungsproblem”, sul tema del “problema della decibilità” (precedentemente trattato da David Hilbert e Wilhem Ackermann, nel 1900) proponendo una soluzione attraverso un modello matematico in grado di simulare il calcolo umano, con una macchina munita di una testina di lettura e scrittura, in grado di comporre su un nastro infinito partizionato in caselle.
Le caratteristiche della Macchina di Turing
A seguito di un istante di tempo, la macchina si ritrova in uno stato interno successivo all’elaborazione dei dati; le componenti che formano lo stato interno sono il numero della cella, il suo contenuto e l’istruzione che essa deve seguire. Tra le configurazioni possibili figurano quelle iniziali, finali ed intermedie. Con la Macchina di Turing, è possibile operare da una casella posizionata a destra e da una posizionata a sinistra, scrivere un simbolo dall’insieme della casella e cancellarlo (e/o fermarsi). [Merita lettura l’articolo di Focus]
Essa è costituita da meccanismi elementari semplici; ha potere computazionale (presumibilmente alla massima) ed è in grado di risolvere ogni particolare problema calcolabile. Tra le varianti del dispositivo, figurano la “Macchina di Turing deterministica a un nastro con istruzioni a cinque campi”, la “Macchina di Turing multinastro”, la “Macchina di Turing con memoria bidimensionale” e la “Macchina di Turing non deterministica”. La macchina universale invece, calcola la funzione u e simula il comportamento di ogni altra.
I fattori negativi della Macchina di Turing
Una MdT con un’evoluzione illimitata, può essere utilizzata positivamente attraverso una successione di oggetti, numeri primi e numeri di Mersenne; in tipologie di calcolo differenti, essa procede senza fornire indicazioni e quindi, possiamo solo attendere un risultato (in tempi accettabili) oppure interrompere l’elaborazione. [Tutte le info su Treccani.it]
[Photo by Pixabay.com]
