macchina di Turing

Macchina di Turing

Modello di agente di calcolo adatto a simulare la logica di qualsiasi algoritmo computazionale. La macchina formale fu proposta nel 1936 dal logico e matematico britannico Alan Turing, come sistema astratto che, opportunamente programmato, era capace di eseguire ogni tipo di operazione (l’idea di Turing era di rendere automatica una macchina da scrivere). Oggi ne esistono molte varianti, la più semplice delle quali è la macchina di Turing a nastro, formata da un’unità di controllo contenente un programma con un numero finito di istruzioni, da un nastro di lunghezza illimitata suddiviso in celle e da un’unità di lettura e scrittura sul nastro in grado di spostarsi avanti e indietro di un numero qualsiasi di celle e di leggere e scrivere in una qualsiasi delle celle un simbolo di un alfabeto prefissato. Questa macchina, pur nella sua semplicità, può calcolare in un numero finito di passi elementari qualsiasi funzione computabile. Il nastro si estende idealmente in modo infinito nei due versi e risulta diviso in celle, ciascuna contenente un simbolo appartenente a un insieme finito di simboli detto alfabeto.

Ogni ;macchina di Turing deve possedere un alfabeto che contenga il simbolo speciale b (blank, spazio), i simboli 0 e 1, e un numero finito di altri simboli, come X e Y, usati come segnaposto. In ogni istante solo un numero finito di celle contiene simboli diversi da b. Il nastro funziona pertanto da input, da output e da memoria. La macchina è costituita da un numero finito k di stati o configurazioni ed è pensata per eseguire solo un tipo di operazione primitiva. A ogni operazione corrispondono tre azioni o comandi: scrittura di un nuovo simbolo nella cella, posizionamento in un nuovo stato, spostamento di una cella verso destra o verso sinistra. Le istruzioni possibili per la macchina sono: stato corrente, simbolo corrente, prossimo simbolo, prossimo stato, direzione di spostamento. Una macchina di Turing può eseguire un’intera sequenza di istruzioni, poiché risulta sincronizzata da una sorta di orologio interno. La macchina è pertanto un modello di agente di calcolo generale che modellizza ciò che effettivamente può compiere un calcolatore.

La macchina di Turing ha permesso di dimostrare che alcuni problemi non ammettono nessuna soluzione generale calcolabile. La tesi o congettura di Church-Turing afferma infatti che, se esiste un algoritmo per eseguire un compito che manipola simboli, allora esiste una macchina di Turing in grado di eseguire quel compito. Pertanto, è possibile utilizzare il modello della macchina di Turing per definire i limiti della computabilità: se per un problema non esiste una macchina di Turing in grado di risolverlo allora il problema si dice incomputabile o irrisolvibile.

→ Complessità algoritmica; Informatica teorica; Intelligenza artificiale; Sistemi chimico-fisici: autorganizzazione