Μια απόδειξη ότι υπάρχει τουλάχιστον ένα ασήμαντο πρόγραμμα υπολογιστή που δεν μπορεί να υπάρχει

Οι πιο όμορφες μαθηματικές αποδείξεις, τομ. 2, Maxime Coutte.

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

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

Καθορισμός Η, Το Αδύνατο Πρόγραμμα Υπολογιστών

Ορίζουμε ένα πρόγραμμα υπολογιστή P (i) ως μια λίστα οδηγιών P που όταν εκτελούνται με μια είσοδο i, δίνουν μια έξοδο o.

Για παράδειγμα,

είναι ένα πρόγραμμα που αθροίζει τους δύο αριθμούς που του δίνετε ως εισόδους και,

είναι ένα πρόγραμμα που χρησιμοποιεί ένα άλλο πρόγραμμα - P_add - ως είσοδος, και περνά αυτό το πρόγραμμα τις δύο άλλες εισόδους. Κάνει αυτό που κάνει το P_add (a, b) και το διπλασιάζει.

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

Τώρα ας υποθέσουμε ότι υπάρχει ένα πρόγραμμα H (P, i) που λαμβάνει ως εισαγωγή τη λίστα με τις οδηγίες P του προγράμματος P (i) και i την είσοδο του P (i) και εξάγει 1 εάν P (i) σταματήστε σε κάποιο σημείο και 0 εάν P (i) κολλήσει και τρέξτε για πάντα. Να το θέσω απλά,

Γιατί δεν μπορεί να υπάρχει ο κατάλογος των οδηγιών λογικής

Με βάση την απόδειξη του Άλαν Τούρινγκ στην εφημερίδα «Σε υπολογιστικούς αριθμούς, με αίτηση στο πρόβλημα Entscheidungs» -1937, θα αποδείξουμε ότι το Η δεν μπορεί να υπάρχει.

Με βάση την υπόθεση ότι υπάρχει H κατασκευάζουμε ένα πρόγραμμα X (P) που τρέχει για πάντα αν και μόνο αν H (P, P) = 1 και σταματήσει εάν και μόνο αν H (P, P) = 0. Με άλλα λόγια,

Μπορούμε τώρα να σκεφτούμε να δώσουμε στο X (i) τη δική του λίστα οδηγιών X ως είσοδο: X (X).

Επομένως, το X (X) τρέχει για πάντα αν και μόνο εάν H (X, X) = 1 και X (X) σταματά εάν και μόνο εάν H (X, X) = 0. Με άλλα λόγια,

Έχουμε μια αντίφαση! Έχουμε δείξει από το Reductio ad absurdum ότι το Η δεν μπορεί να υπάρχει αφού η ύπαρξή του οδηγεί σε παράλογα συμπεράσματα.

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

Αναφορές, Alan Turing. "Σε υπολογιστικούς αριθμούς, με εφαρμογή στο πρόβλημα Entscheidungs". 1937.

Είμαι ο Max Coutte, συνιδρυτής του Relativty.com, ένα ακουστικό VR που σχεδίασα από το μηδέν, εκ των οποίων άνοιξα τον κώδικα και το υλικό. Ακολουθήστε με στο Twitter @maxcoutte.