Se siete indecisi e i vostri problemi sono complessi, provate a fermare tutto.

Dai calcolatori meccanici  ai modelli di macchine  per  il calcolo automatico:  il passo  tra i due  approcci è stato obbligatorio, dal momento che  si rendevano necessari degli strumenti che permettessero di valutare la  complessità degli algoritmi e le risorse  fisiche a disposizione  per  il loro calcolo.
 Alan Mathison Turing,  matematico, logico e crittografo britannico, è stato uno dei fondatori della teoria della calcolabilità degli algoritmi attraverso l’ideazione della macchina di Turing nel 1936 pubblicando un articolo intitolato: “On computable numbers, with an application to the Entscheidungs problem”. In maniera generalistica una macchina di Turing è un modello di macchina astratta,  non fisica, dotata di una testina e un nastro, su cui è in grado di effettuare operazioni di lettura e scrittura .  La testina della macchina evolve  nel tempo,  muovendosi sul  nastro su cui  è posta una stringa che rappresenta il dato di ingresso di un problema P. Un’ evoluzione della macchina consiste in una sequenza di sue possibili configurazioni di una stringa di lunghezza finita. Ma se  si utilizza una macchina di Turing con evoluzione illimitata  per il calcolo dei numeri primi, dei numeri di Mersenne (infatti si considerano infinite le risorse di spazio e tempo a disposizione della macchina),  si vuole capire se la macchina si arresterà o meno in seguito alla computazione.  Tale problema prende il nome di problema della fermata. Esiste un macchina di Turing universale che è in grado di simulare qualsiasi configurazione della macchina di Turing, ma non è in grado di decidere in ogni caso il problema dell’arresto. Quindi nessuna macchina di Turing può farlo. Questo risultato negativo, che prende  il nome di congettura di Church-Turing,  si esprime dicendo che il problema dell’arresto è  Turing-indecidibile. Questo risultato negativo costituisce un limite per tutti i meccanismi computazionali; esso costituisce un risultato limitativo di grande importanza generale e per lo studio degli algoritmi.

Macchina di Turing