La completezza di Turing è quando un linguaggio di programmazione è in grado di svolgere le funzioni di una macchina di Turing. Questo è un concetto per un computer meccanico di base, a volte descritto come la macchina più semplice che può essere considerata un computer. Praticamente tutti i linguaggi di programmazione in uso oggi, e in teoria i computer che li eseguono, hanno la completezza di Turing.
Il concetto di completezza di Turing deriva da Alan Turing, un informatico britannico il cui lavoro includeva la decifrazione di messaggi in codice durante la seconda guerra mondiale. Tra i suoi lavori sull’informatica c’era lo sviluppo di una filosofia su ciò che un computer potrebbe effettivamente fare. Ciò includeva il concetto che i computer funzionano semplicemente eseguendo algoritmi. Vale a dire che seguono un insieme fisso di regole per elaborare i dati e, a loro volta, risolvere i problemi. Ciò significa che un computer non “pensa” o prende decisioni come fa una persona.
Per illustrare il concetto, Turing descrisse un’ipotetica macchina che chiamò “a-machine”, con la “a” che sta per automatico; altri in seguito la chiamarono la macchina di Turing. La macchina elaborava una bobina di nastro che poteva spostarsi avanti o indietro e conteneva una linea di simboli. In qualsiasi momento la macchina potrebbe elaborare un simbolo e, se necessario, modificarlo. Ai fini del concetto, la bobina del nastro potrebbe essere infinitamente lunga, il che significa che la memoria del computer non era intrinsecamente limitata. Questa è un’analogia per l’idea che una volta che un computer ha una serie di istruzioni da seguire, la quantità di dati a cui può applicare tali istruzioni è soggetta solo a limiti fisici.
Ironia della sorte, la maggior parte dei computer oggi non ha la completezza di Turing. Questo perché hanno limitazioni sullo spazio di archiviazione disponibile e quindi sui dati che possono elaborare. Hanno anche limitazioni fisiche, in particolare che alla fine si esauriranno. In realtà è il linguaggio di programmazione che ha la completezza di Turing. Per questo motivo, un computer che esegue un programma del genere non è un computer Turing, ma può essere utilizzato per simularne uno.
La completezza di Turing non deve essere confusa con il test di Turing. Questo è stato un esperimento progettato da Turing per vedere se i computer possono conversare in linguaggio naturale. Il principio del test è che se un essere umano non è in grado di distinguere tra una conversazione di solo testo con il computer e un altro umano, il computer supera il test. Mentre alcuni computer hanno superato il test quando la gamma di argomenti di conversazione è limitata, nessuno lo ha fatto in una conversazione senza restrizioni.