Το πιο σημαντικό μηχάνημα που δεν κατασκευάστηκε ποτέ

Ο υπολογισμός είναι μια οικεία έννοια που οι περισσότεροι από εμάς κατανοούμε διαισθητικά. Πάρτε τη λειτουργία f(x) = x + 3. Όταν x είναι τρία, f(3) = 3 + 3. Έξι. Ανετα. Φαίνεται προφανές ότι αυτή η συνάρτηση είναι υπολογίσιμη. Αλλά ορισμένες συναρτήσεις δεν είναι τόσο απλές και δεν είναι τόσο εύκολο να προσδιοριστεί εάν μπορούν να υπολογιστούν, πράγμα που σημαίνει ότι μπορεί να μην μας δώσουν ποτέ μια τελική απάντηση.

Το 1928, οι Γερμανοί μαθηματικοί David Hilbert και Wilhelm Ackermann πρότειναν μια ερώτηση που ονομάζεται Πρόβλημα Entscheidungs («πρόβλημα απόφασης»). Με τον καιρό, η ερώτησή τους θα οδηγούσε σε έναν επίσημο ορισμό της υπολογισιμότητας, που επέτρεπε στους μαθηματικούς να απαντήσουν σε μια σειρά από νέα προβλήματα και έθεσε τα θεμέλια για τη θεωρητική επιστήμη των υπολογιστών.

Ο ορισμός προήλθε από έναν 23χρονο φοιτητή ονόματι Άλαν Τούρινγκ, ο οποίος το 1936 έγραψε ένα σπερματικό χαρτί που όχι μόνο επισημοποίησε την έννοια του υπολογισμού, αλλά αποδείχθηκε επίσης ένα θεμελιώδες ερώτημα στα μαθηματικά και δημιούργησε τη διανοητική βάση για την εφεύρεση του ηλεκτρονικού υπολογιστή. Η μεγάλη διορατικότητα του Τούρινγκ ήταν να δώσει μια συγκεκριμένη απάντηση στο υπολογιστικό ερώτημα με τη μορφή μιας αφηρημένης μηχανής, που αργότερα ονομάστηκε μηχανή Τούρινγκ από τον διδακτορικό του σύμβουλο, Αλόνζο Τσερτς. Είναι αφηρημένο γιατί δεν υπάρχει (και δεν μπορεί) να υπάρχει φυσικά ως απτή συσκευή. Αντίθετα, είναι ένα εννοιολογικό μοντέλο υπολογισμού: Εάν το μηχάνημα μπορεί να υπολογίσει μια συνάρτηση, τότε η συνάρτηση είναι υπολογίσιμη.

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

Ο καλύτερος τρόπος για να κατανοήσετε μια μηχανή Turing είναι να εξετάσετε ένα απλό παράδειγμα. Ας φανταστούμε ένα που έχει σχεδιαστεί για να μας λέει εάν μια δεδομένη είσοδος είναι ο αριθμός μηδέν. Θα χρησιμοποιήσουμε τον αριθμό εισαγωγής 0001 συνοδευόμενο από κενά σύμβολα (#), οπότε το "#0001#" είναι το σχετικό μέρος της ταινίας μας.

Το μηχάνημα ξεκινά στην αρχική κατάσταση, την οποία θα ονομάσουμε q0. Διαβάζει το πιο αριστερό κελί στην κασέτα μας και βρίσκει ένα κενό διάστημα. Οι κανόνες λένε, "Όταν στην κατάσταση q0, εάν το σύμβολο είναι #, αφήστε το ως έχει χωρίς τροποποίηση, μετακινήστε ένα κελί προς τα δεξιά και αλλάξτε την κατάσταση του μηχανήματος σε q1." Μετά από αυτό το βήμα, το μηχάνημα βρίσκεται στην κατάσταση q1 και η κεφαλή του διαβάζει το δεύτερο σύμβολο, 0.

Τώρα αναζητούμε έναν κανόνα που ισχύει για αυτές τις συνθήκες. Βρίσκουμε ένα που λέει, "Παραμονή στην κατάσταση q1 και μετακινήστε το κεφάλι ένα κελί προς τα δεξιά." Αυτό μας αφήνει στην ίδια θέση (στην κατάσταση q1, διαβάζοντας "0"), οπότε συνεχίζουμε να κινούμαστε προς τα δεξιά μέχρι το κεφάλι να διαβάσει τελικά έναν διαφορετικό αριθμό, το 1.

Όταν συμβουλευόμαστε ξανά τον πίνακα, βρίσκουμε έναν νέο κανόνα: «Αν συναντήσουμε ένα 1, μετάβαση στο q2, που είναι μια κατάσταση «απόρριψης». Το μηχάνημα σταματά, απαντώντας "Όχι" στην αρχική ερώτηση, "Είναι το '0001' μηδέν;"

Αν αντ' αυτού η είσοδος είναι "#0000#", το μηχάνημα θα συναντήσει ένα # μετά από όλα αυτά τα μηδενικά. Όταν συμβουλευόμαστε τον πίνακα, βρίσκουμε έναν κανόνα που λέει ότι αυτό σημαίνει ότι το μηχάνημα εισέρχεται σε κατάσταση q3, κατάσταση «αποδοχής». Τώρα το μηχάνημα απαντά "Ναι" στην ερώτηση "Είναι το '0000' μηδέν;"

Με την αφηρημένη μηχανή του, ο Turing καθιέρωσε ένα μοντέλο υπολογισμού για να απαντήσει στο Entscheidungsproblem, το οποίο ρωτά επίσημα: Δεδομένου ενός συνόλου μαθηματικών αξιωμάτων, υπάρχει μια μηχανική διαδικασία - ένα σύνολο εντολών, που σήμερα θα ονομάζαμε αλγόριθμο - που μπορεί πάντα να προσδιορίσετε αν μια δεδομένη πρόταση είναι αληθής;

Ας πούμε ότι θέλουμε να βρούμε έναν αλγόριθμο που μπορεί να μας πει εάν μια συγκεκριμένη θέση σκακιού είναι δυνατή. Εδώ, τα αξιώματα είναι οι κανόνες του σκακιού που διέπουν τις νόμιμες κινήσεις. Μπορούμε να ακολουθήσουμε μια πεπερασμένη βήμα προς βήμα ακολουθία διαδικασιών για να φτάσουμε σε αυτή τη θέση; Αν και ορισμένες θέσεις μπορεί να διαρκέσουν περισσότερο από τη διάρκεια ζωής μας για να αναλυθούν - ένας αλγόριθμος μπορεί να δημιουργήσει όλες τις πιθανές θέσεις και να συγκρίνει καθεμία από αυτές με την είσοδο - τέτοιοι αλγόριθμοι υπάρχουν στο παιχνίδι του σκακιού. Ως αποτέλεσμα, λέμε ότι το σκάκι μπορεί να αποφασιστεί.

Ωστόσο, το 1936, ο Church και ο Turing — χρησιμοποιώντας διαφορετικές μεθόδους — απέδειξαν ανεξάρτητα ότι δεν υπάρχει γενικός τρόπος επίλυσης κάθε περίπτωσης του προβλήματος Entscheidungs. Για παράδειγμα, ορισμένα παιχνίδια, όπως το Game of Life του John Conway, δεν μπορούν να αποφασιστούν: Κανένας αλγόριθμος δεν μπορεί να καθορίσει εάν ένα συγκεκριμένο μοτίβο θα εμφανιστεί από ένα αρχικό μοτίβο.

Ο Turing έδειξε ότι μια συνάρτηση είναι υπολογίσιμη εάν υπάρχει ένας αλγόριθμος που μπορεί να εκτελέσει την επιθυμητή εργασία. Ταυτόχρονα, έδειξε ότι ένας αλγόριθμος είναι μια διαδικασία που μπορεί να οριστεί από μια μηχανή Turing. Ως εκ τούτου, μια υπολογίσιμη συνάρτηση είναι μια συνάρτηση που έχει μια μηχανή Turing για να την υπολογίσει. Αυτό μπορεί να φαίνεται σαν ένας κυκλικός τρόπος για να ορίσουμε την υπολογισιμότητα, αλλά είναι ο καλύτερος που έχουμε. «Δεν είναι σαν να έχεις επιλογή να το ορίσεις με άλλο τρόπο», είπε Μάικλ Σίπσερ, θεωρητικός επιστήμονας υπολογιστών στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης. «Νομίζω ότι είναι κοινώς αποδεκτό ότι η θέση Church-Turing λέει ότι η άτυπη έννοια του αλγορίθμου αντιστοιχεί σε αυτό που μπορεί να κάνει οποιοδήποτε «λογικό» υπολογιστικό μοντέλο». Άλλοι μαθηματικοί έχουν καταλήξει σε διαφορετικά μοντέλα υπολογισμού που φαίνονται αρκετά διαφορετικά στην επιφάνεια, αλλά στην πραγματικότητα είναι ισοδύναμα: Μπορούν να κάνουν οποιονδήποτε υπολογισμό μπορούν να κάνουν οι μηχανές Turing και το αντίστροφο.

Μόνο λίγα χρόνια αφότου ο Kurt Gödel είχε αποδείξει ότι τα μαθηματικά ήταν ατελής, ο Church και ο Turing έδειξαν με αυτήν την εργασία ότι ορισμένα προβλήματα στα μαθηματικά δεν μπορούν να επιλυθούν — κανένας αλγόριθμος, όσο περίπλοκος κι αν είναι, δεν μπορεί να μας πει εάν η απάντηση είναι ναι ή όχι. Και τα δύο ήταν καταστροφικά πλήγματα για τον Χίλμπερτ, ο οποίος ήλπιζε ότι τα μαθηματικά θα είχαν τακτοποιημένες, εξιδανικευμένες απαντήσεις. Αλλά είναι ίσως το ίδιο καλά: Εάν υπήρχε μια γενική λύση στο πρόβλημα Entscheidungs, αυτό θα σήμαινε ότι όλα τα προβλήματα στα μαθηματικά θα μπορούσαν να περιοριστούν σε απλούς μηχανικούς υπολογισμούς.

Πέρα από την απάντηση σε αυτά τα θεμελιώδη ερωτήματα, η μηχανή του Τούρινγκ οδήγησε επίσης απευθείας στην ανάπτυξη σύγχρονων υπολογιστών, μέσω μιας παραλλαγής γνωστής ως η καθολική μηχανή Turing. Αυτό είναι ένα ειδικό είδος μηχανής Turing που μπορεί να προσομοιώσει οποιαδήποτε άλλη μηχανή Turing σε οποιαδήποτε είσοδο. Μπορεί να διαβάσει μια περιγραφή άλλων μηχανών Turing (τους κανόνες και τις ταινίες εισόδου τους) και να προσομοιώσει τις συμπεριφορές τους στη δική του ταινία εισόδου, παράγοντας την ίδια έξοδο που θα παρήγαγε η προσομοιωμένη μηχανή, όπως οι σημερινοί υπολογιστές μπορούν να διαβάσουν οποιοδήποτε πρόγραμμα και να το εκτελέσουν. Το 1945, ο John von Neumann πρότεινε μια αρχιτεκτονική υπολογιστή - που ονομάζεται αρχιτεκτονική von Neumann - που έκανε δυνατή την καθολική ιδέα της μηχανής Turing σε μια πραγματική μηχανή.

Όταν Sanjeev Arora, ένας θεωρητικός επιστήμονας υπολογιστών στο Πανεπιστήμιο του Πρίνστον, διδάσκει αυτή την έννοια, τονίζει μια ευρύτερη φιλοσοφική εικόνα. «Υπάρχουν δύο έννοιες του «καθολικού», είπε. «Μια έννοια του καθολικού είναι ότι μπορεί να λειτουργήσει οποιαδήποτε άλλη μηχανή Turing. Αλλά η άλλη, μεγαλύτερη έννοια του «καθολικού» είναι ότι μπορεί να εκτελέσει οποιονδήποτε υπολογισμό θα βρείτε στο σύμπαν». Στον κόσμο της κλασικής φυσικής, οποιαδήποτε φυσική διαδικασία μπορεί να μοντελοποιηθεί ή να προσομοιωθεί χρησιμοποιώντας αλγόριθμους, οι οποίοι, με τη σειρά τους, μπορούν να προσομοιωθούν από μια μηχανή Turing.

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

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