Macchina di Turing

La macchina di Turing è un dispositivo computazionale teorico in grado di svolgere qualsiasi tipologia di calcolo. La macchina di Turing viene definita dal matematico inglese Alan Turing, da cui prende il nome, nel 1936. La macchina di Turing comunica con l'esterno attraverso un nastro di lunghezza infinita, sul quale può scrivere ( output ) o leggere ( input ) i dati ed eseguire gli algoritmi. Sul nastro sono poste delle celle in grado di contenere un solo simbolo. La macchina di Turing può simulare qualsiasi processo di calcolo formale, separando l'informazione dello stato interno dall'informazione dello stato esterno. Il concetto della macchina di Turing è alla base dei moderni computer.