Τι είναι η πληρότητα του Turing;

Η πληρότητα είναι όταν μια γλώσσα προγραμματισμού είναι σε θέση να εκτελέσει τις λειτουργίες μιας μηχανής Turing.Αυτή είναι μια έννοια για έναν πολύ βασικό μηχανικό υπολογιστή, που μερικές φορές περιγράφεται ως το απλούστερο μηχάνημα που μπορεί να θεωρηθεί υπολογιστής.Σχεδόν όλες οι γλώσσες προγραμματισμού που χρησιμοποιούνται σήμερα, και θεωρητικά, οι υπολογιστές που τους τρέχουν, έχουν την πληρότητα του Turing.

Η έννοια της πληρότητας του Turing προέρχεται από τον Alan Turing, έναν βρετανό επιστήμονα υπολογιστών του οποίου η εργασία περιελάμβανε αποκρυπτογράφηση κωδικοποιημένων μηνυμάτων κατά τη διάρκεια του Β 'Παγκοσμίου Πολέμου.Μεταξύ του έργου του για τον υπολογισμό ήταν η ανάπτυξη μιας φιλοσοφίας του τι θα μπορούσε να κάνει ένας υπολογιστής.Αυτό περιελάμβανε την ιδέα ότι οι υπολογιστές λειτουργούν απλά με τους αλγόριθμους τρέχουσας.Δηλαδή, ακολουθούν ένα σταθερό σύνολο κανόνων για την επεξεργασία δεδομένων και με τη σειρά τους να λύσουν προβλήματα.Αυτό σημαίνει ότι ένας υπολογιστής δεν σκέφτεται ούτε λαμβάνει αποφάσεις όπως ένα άτομο μπορεί να δείξει την έννοια, ο Turing περιέγραψε μια υποθετική μηχανή που ονομάζεται A-Machine, με τη στάση για αυτόματη.Άλλοι αργότερα το ονόμασαν το μηχάνημα Turing.Το μηχάνημα θα επεξεργαστεί έναν κύλινδρο ταινίας που θα μπορούσε να μετακινηθεί πίσω ή προς τα εμπρός και περιείχε μια γραμμή συμβόλων.Σε κάθε στιγμή το μηχάνημα θα μπορούσε να επεξεργαστεί ένα σύμβολο και, εάν είναι απαραίτητο, να το αλλάξει.Για τους σκοπούς της έννοιας, ο κύλινδρος της ταινίας θα μπορούσε να είναι απείρως μακρύς, πράγμα που σημαίνει ότι η μνήμη του υπολογιστή δεν ήταν εγγενώς περιορισμένη.Αυτή είναι μια αναλογία για την ιδέα ότι μόλις ένας υπολογιστής έχει ένα σύνολο οδηγιών που πρέπει να ακολουθήσουν, το ποσό των δεδομένων που μπορεί να εφαρμόσει αυτές τις οδηγίες για να υπόκειται μόνο σε φυσικά όρια.

ειρωνικά, οι περισσότεροι υπολογιστές σήμερα δεν έχουν στην πραγματικότητα την πληρότητα.Αυτό οφείλεται στο γεγονός ότι έχουν περιορισμούς στον διαθέσιμο χώρο αποθήκευσης και έτσι τα δεδομένα που μπορούν να επεξεργαστούν.Έχουν επίσης φυσικούς περιορισμούς, κυρίως ότι τελικά θα φθαρούν.Είναι στην πραγματικότητα η γλώσσα προγραμματισμού που έχει πληρότητα Turing.Αυτό ήταν ένα πείραμα που σχεδιάστηκε από τον Turing για να δει αν οι υπολογιστές μπορούν να συνομιλήσουν στη φυσική γλώσσα.Η αρχή της δοκιμής είναι ότι εάν ένας άνθρωπος δεν μπορεί να πει τη διαφορά μεταξύ μιας συνομιλίας μόνο με τον υπολογιστή και ενός άλλου ανθρώπου, ο υπολογιστής περνάει τη δοκιμή.Ενώ ορισμένοι υπολογιστές έχουν περάσει τη δοκιμή όταν το εύρος των υποκειμένων συνομιλίας είναι περιορισμένο, κανένας δεν το έχει κάνει σε απεριόριστη συνομιλία.