Lego Macchina di Turing

Tutto ciò che è calcolabile può essere calcolato da una Macchina di Turing quindi nessuna macchina, ne un semplice pc ne un supercalcolatore, può calcolare di più: potrà farlo solo più velocemente ma niente altro.

Ho parlato più volte di Alan Turing, del suo famoso Test; ed in questa occasione riparlo del suo lavoro fondante ossia la Macchina Universale di Turing; e lo faccio per una ragione che è contenuta nel titolo: ci arrivo.

Nel 1936, Alan Turing immaginò la sua Macchina Universale come un semplice nastro con infinite celle nelle quali una testina capace di andare avanti e dietro può leggere, scrivere e cancellare simboli in funzione di una serie di regole definite ossia di istruzioni. Questa fu la grande intuizione di Turing, una macchina in grado di gestire simboli; o come disse lo storico della scienza George Dyson “il nastro contiene sia numeri che significano cose, sia numeri che fanno cose”

Numeri che significano dati e numeri che significano istruzioni.

Ogni calcolo può essere fatto in questo modo, inserendo i giusti dati e scrivendo le necessarie regole / istruzioni:

leggi la cella 1 > spostati a sinistra > cancella > scrivi 1 > spostati a destra > ecc

I moderni computer si basano sull’architettura hardware concepita da John von Neumann e che di fatto realizza una Macchina di Turing:

un processore preleva istruzioni e dati dalla memoria (numeri che significano dati e altri numeri che significano istruzioni), esegue le istruzioni ossia operazioni matematiche, e memorizza i risultati.

Tra le varie simulazioni della Macchina di Turing che potete trovare in rete la mia preferita è quella costruita da Jeroen van den Bos e Davy Landman del Centrum Wiskunde & Informatica (CWI) di Amsterdam. In occasione del centenario (quest’anno) della nascita di Alan Turing, hanno costruito una Lego Turing Machine con le componenti del Lego Mindstorm NXT il robot assemblabile e programmabile della lego.

La funzione della testina è svolta dal sensore di colore che viene alzato/abbassato sul nastro dal movimento di un motore; il nastro costruito con i vari moduli di costruzione è mosso da un secondo motore con ingranaggi; i simboli intesi come 0 ed 1 sono rappresentati da pioli neri che in posizione retta vengono letti dal sensore (nero=1) mentre nell’altra posizione il sensore legge il colore bianco e quindi 0.

Gustatevi il video