Un qualsiasi procedimento eseguibile in modo meccanico è detto algoritmo se risponde alle seguenti quattro caratteristiche:

 

1) consta di un numero finito di passi

 

2) ad ogni passo viene determinato univocamente il passo successivo

 

3) rappresenta la risoluzione di tutti i problemi dello stesso tipo e non solo di un caso particolare

 

4) è interpretabile ed eseguibile dall’esecutore.

 

Molti matematici si sono cimentati nella ricerca di macchine in grado di risolvere qualsiasi problema, o per lo meno tutti quelli risolvibili attraverso un algoritmo.

 

Un passo decisivo in tal senso fu fatto nel 1936 da Alan Turing che, oltre a dare una definizione rigorosa di algoritmo, identificò le caratteristiche di un modello  matematico di una macchina  astratta in grado di eseguire un algoritmo.

 

Tale macchina prese appunto il nome di macchina di Turing.

 

La macchina di Turing rappresenta ancora oggi uno dei più potenti strumenti logico concettuali mai creati dall’uomo e rappresentò il punto di partenza per tutti gli studi successivi che portarono alla realizzazione dei potenti calcolatori.

 

La macchina di Turing, riportata nella figura successiva, è essenzialmente costituita dai tre seguenti elementi:

 

1) un nastro infinito

 

2) una testina di lettura e scrittura

 

3) un organo di controllo

Il nastro, che può essere considerato l’organo di memorizzazione delle informazioni, è suddiviso in caselle, e può spostarsi a destra o a sinistra di una sola casella per volta.