Che cos'è la completezza di Turing?
La completezza di Turing è quando un linguaggio di programmazione è in grado di svolgere le funzioni di una macchina 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 completezza di Turing.
Il concetto di completezza di Turing viene da Alan Turing, uno scienziato 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 poteva effettivamente fare. Ciò includeva il concetto che i computer funzionano semplicemente eseguendo algoritmi. Ciò significa 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" né prende decisioni come una persona può.
Per illustrare il concetto, Turing descrisse un'ipotetica macchina che chiamò "a-machine", con la "a" che significa 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 effettivamente 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 consumeranno. In realtà è il linguaggio di programmazione che ha completezza di Turing. Per questo motivo, un computer che esegue tale programma 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 essere umano, il computer supera il test. Mentre alcuni computer hanno superato il test quando l'intervallo di argomenti di conversazione è limitato, nessuno lo ha fatto in una conversazione senza restrizioni.