Chi ha visto il film The Imitation Game? Prima della sua uscita in pochi conoscevano Alan Turing, protagonista indiscusso della pellicola. Chi era Alan Turing?
Genio della matematica, padre dell’informatica, crittografo, inventore, eroe della seconda guerra mondiale. Tutte le definizioni sono più che corrette.
Quella a cui farò riferimento nel presente articolo è "padre dell’informatica" intesa come scienza dell’informazione, visto che il matematico inglese propose l'idea di una macchina che fosse capace di svolgere ogni tipo di calcolo su numeri e simboli eseguendo istruzioni immesse dall'utilizzatore; se non è informatica questa…

Più è semplice il linguaggio più è difficile programmare

Anche questa sembra la frase di un film ma non lo è; è invece una verità assoluta della programmazione. I linguaggi di programmazione ad alto livello anche se sembrano ostici offrono una vasta gamma di istruzioni, librerie, tipi di dati che in parte facilitano la stesura degli algoritmi.
Immaginate però per un attimo che vi fosse vietato di usare l’istruzione condizionale in C, C++, Java o in un qualunque altro  linguaggio di programmazione. Non basta? Ok, facciamo sparire anche i cicli.
Io a questo punto smetterei di fare il programmatore e mi metterei in cerca di un altro lavoro.
Ma forse c’è ancora qualche coraggioso ostinato che tenta di programmare. Bene, eliminiamo anche librerie e possibilità di definire variabili. Sarebbe lo stesso possibile programmare?

La Macchina di Turing

Il visionario matematico inglese aveva già negli anni 30 del 1900 immaginato che si potesse realizzare una macchina programmabile (ebbene si, programmabile) in grado di eseguire una serie di istruzioni (programma) atte alla soluzione di un problema mediante ragionamento logico (algoritmo). Le regole per scrivere le istruzioni (costrutti del linguaggio) sono molto semplici e derivano direttamente dalla descrizione della Macchina di Turing. Fisicamente non è mai stata realizzata (attenzione, la Macchina di Turing non è quella che si vede nel film). È rimasta un fondamentale e importantissimo formalismo teorico utilizzato nella teoria della calcolabilità e nello studio della complessità degli algoritmi. Le trattazioni complete sulla Macchina di Turing sono innumerevoli. Mi permetto di fornire una breve descrizione della macchina a scopo divulgativo

• C’è un nastro di input-output (lettura e scrittura). Il nastro può essere immaginato come un nastro di lunghezza infinita, diviso in celle.
• Ogni cella contiene un simbolo oppure può essere vuota.
• Il simbolo appartiene ad un alfabeto che decide il programmatore.
• C’è una testina che si sposta lungo il nastro di una cella alla volta, a destra o sinistra.

Ad ogni passo la macchina a seconda del simbolo letto sul nastro e dello stato in cui si trova può:

1. Passare ad un altro stato
2. Scrivere un simbolo sulla cella stessa
3. Eliminare il simbolo letto dalla cella stessa
4. Spostarsi di una cella a destra o sinistra o rimanere nella stessa posizione

La brutta notizia

Non abbiamo altro! Programmare in questo modo è veramente difficile. Come spesso dico ai miei studenti: lavorate un paio di settimane con la Macchina di Turing e vedrete come rimpiangerete i tanto odiati array, cicli for, variabili booleane e via dicendo.

La buona notizia

Non abbiamo altro! Quindi anche chi non ha mai programmato in vita sua può imparare ad usare la macchina in pochi minuti e, se dotato di buone capacità logiche, risolvere algoritmi sempre più complessi.

Esercitiamoci

Non esiste la macchina fisica originale ma in compenso ci sono diversi simulatori validi. Nel presente articolo farò riferimento al simulatore dell’Università di Pisa che tra l’altro è la sede dell’importante gara nazionale sulla Macchina di Turing che si svolge ogni anno e alla quale partecipano studenti da tutta Italia. La cosa interessante è che, come già detto, l’utilizzo della Macchina di Turing non richiede prerequisiti e quindi non è assolutamente scontato che i vincitori della gara debbano per forza essere studenti di informatica. Uno studente di un liceo classico con ottime capacità logico-deduttive può sbaragliare tranquillamente anche buoni conoscitori di Java e C++ ma meno dotati. Ma veniamo al funzionamento del simulatore utilizzabile e/o scaricabile direttamente dall'apposita pagina del sito dell’Università di Pisa.

Questo è un esempio di istruzione nel linguaggio della Macchina di Turing:

(0,9,1,0,<)

Sembra di difficile comprensione ma non lo è affatto. [...]

ATTENZIONE: quello che hai appena letto è solo un estratto, l'Articolo Tecnico completo è composto da ben 2277 parole ed è riservato agli ABBONATI. Con l'Abbonamento avrai anche accesso a tutti gli altri Articoli Tecnici che potrai leggere in formato PDF per un anno. ABBONATI ORA, è semplice e sicuro.

Ti potrebbe interessare anche:

Criteri per la progettazione dei LED driver

Corso di Elettronica per ragazzi – Puntata 14

PRAM, il tuo Primo Robot Autonomo Mobile – Parte 4

L’applicazione delle fibre ottiche nei sistemi di controllo degli aerei

Telecamera per impieghi automotive: note di progettazione

Progetto di un Chatbot IA con NLP e Python – Puntata 3