Giovedì 29 Giugno 2006

- Sezione 3 - Dal 1600 al 1945 - Approfondimenti

La macchina di Turing

Una macchina di Turing è composta da

  • un nastro infinitamente lungo suddiviso in caselle, ciascuna delle quali può contenere un simbolo (equivale al foglio di carta a quadretti utilizzato da una persona che fa conti);

  • una testina che esamina una casella alla volta e può leggere e cambiare il simbolo della casella (equivale alla persona che fissa l’attenzione su una cifra o ne scrive una);

  • degli stati (che rappresentano gli stati mentali della persona);

  • un insieme di regole che, dato lo stato e il contenuto della casella corrente, dicono cosa bisogna fare (per esempio scrivere un simbolo o spostarsi a una altra casella).

Per un particolare algoritmo occorre stabilire l’alfabeto dei simboli, e costruire l’insieme degli stati e l’insieme delle regole: scritti in (opportune) caselle del nastro i dati di partenza, si avvia la macchina. Se quello realizzato è effettivamente un algoritmo, la macchina (dopo un certo tempo) si ferma con il risultato contenuto sul nastro in opportune caselle. (Con parole attuali gli stati e le regole costituiscono il programma).

Home Tour virtuale Sezione 3 Approfondimenti