Πληρότητα Τούρινγκ

Στη θεωρία υπολογισιμότητας, ένα σύστημα κανόνων διαχείρισης δεδομένων (όπως οι ομάδες εντολών του υπολογιστή, ή η γλώσσα προγραμματισμού ή ένα κυψελοειδές αυτόματο), λέγεται ότι είναι "Τούρινγκ {Turing} πλήρες" ή "υπολογιστικά καθολικό" αν μπορεί να χρησιμοποιηθεί για να προσομοιώσει οποιαδήποτε μηχανή Τούρινγκ. Αυτό σημαίνει, ότι αυτό το σύστημα είναι σε θέση να αναγνωρίσει ή να αποφασίσει άλλα σύνολα κανόνων χειρισμού δεδομένων. Αυτή η "πληρότητα Turing", χρησιμοποιείται ως ένας τρόπος έκφρασης της ισχύος ενός τέτοιου κανόνα διαχείρισης δεδομένων. Η δύναμη έκφρασης αυτών των "γραμματικών", καταγράφεται στην "Ιεραρχία Chomsky". Πρακτικά, σχεδόν όλες οι γλώσσες προγραμματισμού, είναι σήμερα "Τούρινγκ πλήρεις". Η ονομασία της έννοιας αυτής είναι φόρος τιμής στον Άγγλο μαθηματικό και επιστήμονα πληροφορικής, Άλαν Τούρινγκ.

Μια σχετική ιδέα είναι αυτή της ισοδυναμίας Τούρινγκ, ότι δηλαδή, δύο υπολογιστές Α και Β ονομάζονται "ισοδύναμοι", αν o Α μπορεί να προσομοιώσει τον Β και ο Β μπορεί να προσομοιώσει τον Α. Η Θεωρία Church-Τούρινγκ", λέει ότι οποιαδήποτε συνάρτηση, της οποίας οι τιμές μπορούν να υπολογιστούν από έναν αλγόριθμο, μπορούν να υπολογιστούν και από μια μηχανή Τούρινγκ και επομένως ότι αν οποιοσδήποτε πραγματικός υπολογιστής μπορεί να προσομοιώσει μια μηχανή Turing, είναι "Τούρινγκ ισοδύναμος" με μια μηχανή Τούρινγκ. Μια καθολική μηχανή Τούρινγκ, μπορεί να χρησιμοποιηθεί για την προσομοίωση οποιασδήποτε άλλης μηχανής Turing και κατ' επέκταση των υπολογιστικών πτυχών οποιουδήποτε πιθανού υπολογιστή στον πραγματικό κόσμο.

Για να δείξουμε ότι κάτι είναι "Τούρινγκ πλήρες", αρκεί μόνο να δείξουμε ότι μπορεί να χρησιμοποιηθεί για να προσομοιώσει ένα "Τούρινγκ πλήρες" σύστημα. Για παράδειγμα, μια προστακτική γλώσσα είναι "Τούρινγκ πλήρης" εάν έχει τις λεγόμενες "υπό συνθήκη διακλαδώσεις", (π.χ., "if" και "goto" δηλώσεις, ή μια εντολή "branch if zero") και την ικανότητα να αλλάξει ένα αυθαίρετο ποσό μνήμης (π.χ., η ικανότητα διατήρησης ενός αυθαίρετου αριθμού στοιχείων δεδομένων). Φυσικά, κανένα φυσικό σύστημα δεν μπορεί να έχει άπειρη μνήμη, αλλά αν αγνοηθεί ο περιορισμός της πεπερασμένης μνήμης, οι περισσότερες γλώσσες προγραμματισμού είναι "Τούρινγκ πλήρεις".

Μη μαθηματική χρήση

Στην καθημερινή μας γλώσσα, οι έννοιες "Τούρινγκ πλήρης" ή "Τούρινγκ ισοδύναμο", χρησιμοποιούνται για να δηλώσουν ότι οποιοσδήποτε πραγματικός υπολογιστής γενικής χρήσης, ή γλώσσα υπολογιστή, μπορεί να προσομοιώσει, περίπου, τις υπολογιστικές πτυχές οποιουδήποτε άλλου υπολογιστή γενικής χρήσης, ή γλώσσας υπολογιστή, του πραγματικού κόσμου.

Οι πραγματικοί υπολογιστές που έχουν κατασκευαστεί μέχρι τώρα, μπορούν να αναλυθούν λειτουργικά όπως μια μηχανή Τούρινγκ μιας ταινίας (η "ταινία" που αντιστοιχεί στη μνήμη τους), έτσι τα σχετικά μαθηματικά μπορούν να εφαρμοστούν, αν η λειτουργία τους γίνει αρκετά αφαιρετική. Ωστόσο, οι πραγματικοί υπολογιστές έχουν περιορισμένους φυσικούς πόρους, επομένως είναι πλήρεις μόνον όσον αφορά το γραμμικά οριοθετημένο αυτόματο. Αντίθετα, ένας καθολικός υπολογιστής ορίζεται ως συσκευή με πλήρες σύνολο οδηγιών Τούρινγκ, άπειρη μνήμη και άπειρο διαθέσιμο χρόνο.

Επίσημοι ορισμοί

Στη θεωρία υπολογισιμότητας, χρησιμοποιούνται αρκετοί σχετικοί όροι για την περιγραφή της υπολογιστικής ισχύος ενός υπολογιστικού συστήματος (όπως μια αφηρημένη μηχανή ή μια γλώσσα προγραμματισμού):

Πληρότητα Τούρινγκ

Ένα υπολογιστικό σύστημα που μπορεί να υπολογίσει κάθε λειτουργία που μπορεί να υπολογιστεί με μια μηχανή Τούρινγκ, ονομάζεται Τούρινγκ πλήρες (ή Τούρινγκ-ισχυρό). Εναλλακτικά, ένα τέτοιο σύστημα είναι και ένα σύστημα που μπορεί να προσομοιώσει μια καθολική μηχανή Τούρινγκ.

Ισότητα Τούρινγκ

Ένα σύστημα Turing πλήρες ονομάζεται Τούρινγκ ισοδύναμο, αν κάθε λειτουργία που μπορεί να υπολογίσει είναι επίσης Turing υπολογίσιμη, δηλαδή, αν υπολογίζει ακριβώς την ίδια κατηγορία λειτουργιών όπως και οι μηχανές Τούρινγκ. Εναλλακτικά, ένα Τούρινγκ ισοδύναμο σύστημα, είναι ένα σύστημα που μπορεί να προσομοιώνει και να προσομοιώνεται από μια παγκόσμια μηχανή Τούρινγκ. (Όλα τα γνωστά συστήματα που είναι Turing πλήρη, είναι και Turing ισοδύναμα, το οποίο υποστηρίζει τη θεωρία Church-Turing).

(Υπολογιστική) καθολικότητα

Ένα σύστημα, ονομάζεται καθολικό σε σχέση με μια τάξη συστημάτων, αν μπορεί να υπολογίσει κάθε συνάρτηση που υπολογίζεται από συστήματα της τάξης αυτής (ή μπορεί να προσομοιώσει κάθε ένα από αυτά τα συστήματα). Συνήθως, ο όρος καθολικότητα χρησιμοποιείται σε σχέση με μια ολοκληρωμένη κατηγορία συστημάτων Τούρινγκ. Ο όρος "ασθενώς καθολικός" χρησιμοποιείται μερικές φορές για να διακρίνει ένα σύστημα (π.χ. ένα κυψελοειδές αυτοματοποιητή), του οποίου η καθολικότητα επιτυγχάνεται μόνο τροποποιώντας τον τυποποιημένο ορισμό της μηχανής Turing έτσι ώστε να περιλαμβάνει ρεύματα εισόδου με άπειρα πολλά 1.

Ιστορία

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

Ο αναλυτικός κινητήρας του Τσαρλς Μπάμπατζ, (1830), θα ήταν το πρώτο Turing πλήρες μηχάνημα, αν είχε κατασκευαστεί τη στιγμή που σχεδιάστηκε. Ο Μπάμπατζ εκτιμούσε ότι το μηχάνημα ήταν ικανό για πολλούς υπολογισμούς, συμπεριλαμβανομένης της πρωτόγονης λογικής σκέψης, αλλά δεν κατάλαβε ότι κανένα άλλο μηχάνημα δεν θα μπορούσε να το κάνει καλύτερα. Από τη δεκαετία του 1830, μέχρι και τη δεκαετία του 1940, χτίστηκαν και βελτιώθηκαν μηχανικά συστήματα υπολογισμού, όπως τα πρώτα προσθετικά κομπιουτεράκια (adders) και οι πολλαπλασιαστές, αλλά δεν μπορούσαν να εκτελέσουν μια "υπό προϋπόθεση διακλάδωση", και επομένως δεν ήταν πλήρης.

Στα τέλη του 19ου αιώνα, ο Λέοπολντ Κρόνεκερ διατύπωσε έννοιες υπολογιστικής ικανότητας, ορίζοντας τις πρώτες αναδρομικές λειτουργίες. Αυτές οι λειτουργίες μπορούν να υπολογιστούν με υπολογισμό "rote", αλλά δεν αρκούν για να δημιουργήσουν έναν καθολικό υπολογιστή, επειδή οι εντολές που τις υπολογίζουν δεν επιτρέπουν έναν άπειρο βρόχο. Στις αρχές του 20ου αιώνα, ο Ντάβιντ Χίλμπερτ έγραψε ένα πρόγραμμα, για να αξιωματοποιήσει όλα τα μαθηματικά με ακριβή αξιώματα και ακριβείς λογικούς κανόνες αφαίρεσης, που θα μπορούσαν να εκτελεστούν από μια μηχανή. Σύντομα, έγινε σαφές ότι μια μικρή σειρά κανόνων αφαίρεσης, είναι αρκετή για να παράγει τις συνέπειες οποιουδήποτε συνόλου αξιών. Αυτοί οι κανόνες, αποδείχθηκαν από τον Κουρτ Γκέντελ το 1930 ότι είναι αρκετοί για να παράγουν κάθε θεώρημα.

Η πραγματική έννοια του υπολογισμού απομονώθηκε σύντομα μετά, ξεκινώντας από το θεώρημα ατέλειας του Κουρτ Γκέντελ. Αυτό το θεώρημα έδειξε ότι τα συστήματα αξιώματος ήταν περιορισμένα όταν σκέφτονταν τον υπολογισμό που συνάγει τα θεωρήματά τους. Ο Church και ο Τούρινγκ επέδειξαν ανεξάρτητα ότι το "πρόβλημα της απόφασης" του Χίλμπερτ δεν ήταν επιλύσιμο, προσδιορίζοντας έτσι τον υπολογιστικό πυρήνα του θεωρήματος ατέλειας. Αυτό, μαζί με το έργο του Γκέντελ πάνω στις γενικές αναδρομικές λειτουργίες, κατέδειξαν ότι υπάρχουν σύνολα από απλές οδηγίες, οι οποίες, όταν συνδυαστούν, είναι σε θέση να παράγουν οποιοδήποτε υπολογισμό. Το έργο του Γκέντελ έδειξε ότι η έννοια του υπολογισμού είναι, ουσιαστικά, μοναδική.

Το 1941, ο Κόνραντ Τσούζε ολοκλήρωσε τον "Z3" (ηλεκτρονικό υπολογιστή), το πρώτο μηχάνημα εργασίας που ήταν Τούρινγκ πλήρες. Αυτός, ήταν ο πρώτος ψηφιακός υπολογιστής, με τη σύγχρονη έννοια.