Cos'è la completezza di Turing?

La completezza è quando un linguaggio di programmazione è in grado di svolgere le funzioni di una macchina Turing.Questo è un concetto per un computer meccanico molto semplice, 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 gestiscono, hanno completezza.

Il concetto di completezza di Turing viene da Alan Turing, uno scienziato informatico britannico il cui lavoro includeva i messaggi codificati durante la seconda guerra mondiale.Tra i suoi lavori sull'informatica c'era lo sviluppo di una filosofia di ciò che un computer poteva effettivamente fare.Ciò includeva il concetto che i computer funzionano semplicemente eseguendo algoritmi.Vale a dire che seguono una serie fissa di regole per elaborare i dati e, a loro volta, risolvono i problemi.Ciò significa che un computer non pensa o prende decisioni come una persona può.

Per illustrare il concetto, Turing ha descritto una macchina ipotetica che ha chiamato A-Machine, con la posizione automatica;Altri in seguito la chiamarono Turing Machine.La macchina elaborerebbe una bobina di nastro che poteva spostarsi avanti o in avanti 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 è soggetto solo a limiti fisici.

Ironia della sorte, la maggior parte dei computer oggi non ha effettivamente completezza.Questo perché hanno limiti allo spazio di archiviazione disponibili e quindi sui dati che possono elaborare.Hanno anche limiti fisici, in particolare che alla fine si consumano.In realtà è il linguaggio di programmazione che ha completezza.Per questo motivo, un computer che esegue un tale programma non è un computer Turing, ma può essere utilizzato per simularne uno.

La completezza non dovrebbe essere confuso 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 può dire la differenza 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 la gamma di argomenti di conversazione è limitata, nessuno lo ha fatto in una conversazione senza restrizioni.