Εισαγωγή
Οι αλγόριθμοι έχουν γίνει πανταχού παρόντες. Βελτιστοποιούν τις μετακινήσεις μας, επεξεργάζονται πληρωμές και συντονίζουν τη ροή της κίνησης στο Διαδίκτυο. Φαίνεται ότι για κάθε πρόβλημα που μπορεί να διατυπωθεί με ακριβείς μαθηματικούς όρους, υπάρχει ένας αλγόριθμος που μπορεί να το λύσει, τουλάχιστον κατ' αρχήν.
Αλλά αυτό δεν είναι έτσι — ορισμένα φαινομενικά απλά προβλήματα δεν μπορούν ποτέ να λυθούν αλγοριθμικά. Ο πρωτοπόρος επιστήμονας υπολογιστών Άλαν Τούρινγκ αποδείχθηκε την ύπαρξη τέτοιων «μη υπολογίσιμων» προβλημάτων πριν από σχεδόν έναν αιώνα, στην ίδια εργασία όπου διατύπωσε το μαθηματικό μοντέλο υπολογισμού που ξεκίνησε τη σύγχρονη επιστήμη των υπολογιστών.
Ο Turing απέδειξε αυτό το πρωτοποριακό αποτέλεσμα χρησιμοποιώντας μια αντιδιαισθητική στρατηγική: Καθόρισε ένα πρόβλημα που απλώς απορρίπτει κάθε προσπάθεια επίλυσής του.
«Σε ρωτάω τι κάνεις και μετά σου λέω «Όχι, θα κάνω κάτι διαφορετικό», είπε Ραχούλ Ιλάνγκο, μεταπτυχιακός φοιτητής στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης που σπουδάζει θεωρητική επιστήμη των υπολογιστών.
Η στρατηγική του Turing βασίστηκε σε μια μαθηματική τεχνική που ονομάζεται διαγωνοποίηση και έχει μια ξεχωριστή ιστορία. Εδώ είναι μια απλοποιημένη περιγραφή της λογικής πίσω από την απόδειξή του.
Θεωρία των χορδών
Η διαγωνοποίηση προέρχεται από ένα έξυπνο τέχνασμα για την επίλυση ενός εγκόσμιου προβλήματος που περιλαμβάνει σειρές από bit, καθεμία από τις οποίες μπορεί να είναι είτε 0 είτε 1. Λαμβάνοντας υπόψη μια λίστα τέτοιων συμβολοσειρών, όλες εξίσου μεγάλες, μπορείτε να δημιουργήσετε μια νέα συμβολοσειρά που δεν υπάρχει στο λίστα?
Η πιο απλή στρατηγική είναι να εξετάσουμε κάθε δυνατή συμβολοσειρά με τη σειρά. Ας υποθέσουμε ότι έχετε πέντε χορδές, η κάθε μία έχει μήκος πέντε bits. Ξεκινήστε σαρώνοντας τη λίστα για 00000. Εάν δεν υπάρχει, μπορείτε να σταματήσετε. αν είναι, προχωράς στο 00001 και επαναλαμβάνεις τη διαδικασία. Αυτό είναι αρκετά απλό, αλλά είναι αργό για μεγάλες λίστες μακριών χορδών.
Η διαγωνοποίηση είναι μια εναλλακτική προσέγγιση που δημιουργεί μια συμβολοσειρά που λείπει λίγο-λίγο. Ξεκινήστε με το πρώτο bit της πρώτης συμβολοσειράς στη λίστα και αντιστρέψτε το — αυτό θα είναι το πρώτο bit της νέας σας συμβολοσειράς. Στη συνέχεια, αντιστρέψτε το δεύτερο bit της δεύτερης συμβολοσειράς και χρησιμοποιήστε το ως το δεύτερο bit της νέας συμβολοσειράς και επαναλάβετε μέχρι να φτάσετε στο τέλος της λίστας. Τα bit που αναστρέφετε διασφαλίζουν ότι η νέα συμβολοσειρά διαφέρει από κάθε συμβολοσειρά στην αρχική λίστα σε τουλάχιστον ένα σημείο. (Σχηματίζουν επίσης μια διαγώνια γραμμή μέσα από τη λίστα των χορδών, δίνοντας το όνομά της στην τεχνική.)
Η διαγωνοποίηση χρειάζεται μόνο να εξετάσει ένα bit από κάθε συμβολοσειρά στη λίστα, επομένως είναι συχνά πολύ πιο γρήγορη από άλλες μεθόδους. Αλλά η πραγματική του δύναμη έγκειται στο πόσο καλά παίζει με το άπειρο.
«Οι χορδές μπορούν τώρα να είναι άπειρες. η λίστα μπορεί να είναι άπειρη — εξακολουθεί να λειτουργεί», είπε Ράιαν Ουίλιαμς, θεωρητικός επιστήμονας υπολογιστών στο MIT.
Ο πρώτος άνθρωπος που αξιοποίησε αυτή τη δύναμη ήταν ο Georg Cantor, ο ιδρυτής του μαθηματικού υποπεδίου της θεωρίας συνόλων. Το 1873, ο Cantor χρησιμοποίησε τη διαγωνοποίηση για να αποδείξει ότι ορισμένα άπειρα είναι μεγαλύτερο από άλλα. Έξι δεκαετίες αργότερα, ο Turing προσάρμοσε την έκδοση του Cantor για τη διαγωνοποίηση στη θεωρία του υπολογισμού, δίνοντάς της μια σαφώς αντίθετη γεύση.
Το παιχνίδι περιορισμού
Ο Turing ήθελε να αποδείξει την ύπαρξη μαθηματικών προβλημάτων που κανένας αλγόριθμος δεν μπορεί να λύσει - δηλαδή προβλήματα με καλά καθορισμένες εισόδους και εξόδους, αλλά χωρίς αλάνθαστη διαδικασία για τη μετάβαση από είσοδο σε έξοδο. Έκανε αυτό το ασαφές έργο πιο διαχειρίσιμο εστιάζοντας αποκλειστικά σε προβλήματα απόφασης, όπου η είσοδος μπορεί να είναι οποιαδήποτε συμβολοσειρά 0 και 1 και η έξοδος είναι είτε 0 είτε 1.
Ο προσδιορισμός του αν ένας αριθμός είναι πρώτος (διαιρούμενος μόνο με το 1 και τον εαυτό του) είναι ένα παράδειγμα ενός προβλήματος απόφασης — δεδομένου μιας συμβολοσειράς εισόδου που αντιπροσωπεύει έναν αριθμό, η σωστή έξοδος είναι 1 εάν ο αριθμός είναι πρώτος και 0 εάν δεν είναι. Ένα άλλο παράδειγμα είναι ο έλεγχος προγραμμάτων υπολογιστή για συντακτικά λάθη (το αντίστοιχο των γραμματικών λαθών). Εκεί, οι συμβολοσειρές εισόδου αντιπροσωπεύουν κώδικα για διαφορετικά προγράμματα — όλα τα προγράμματα μπορούν να αναπαρασταθούν με αυτόν τον τρόπο, αφού έτσι αποθηκεύονται και εκτελούνται σε υπολογιστές — και ο στόχος είναι να εξάγεται 1 εάν ο κώδικας περιέχει συντακτικό σφάλμα και 0 εάν t.
Ένας αλγόριθμος λύνει ένα πρόβλημα μόνο εάν παράγει τη σωστή έξοδο για κάθε πιθανή είσοδο — αν αποτύχει έστω και μία φορά, δεν είναι αλγόριθμος γενικής χρήσης για αυτό το πρόβλημα. Συνήθως, θα πρέπει πρώτα να καθορίσετε το πρόβλημα που θέλετε να λύσετε και στη συνέχεια να προσπαθήσετε να βρείτε έναν αλγόριθμο που το λύνει. Ο Τούρινγκ, αναζητώντας άλυτα προβλήματα, ανέτρεψε αυτή τη λογική - φαντάστηκε μια άπειρη λίστα όλων των πιθανών αλγορίθμων και χρησιμοποίησε τη διαγωνοποίηση για να κατασκευάσει ένα επίμονο πρόβλημα που θα ανέτρεπε κάθε αλγόριθμο στη λίστα.
Φανταστείτε ένα στημένο παιχνίδι 20 ερωτήσεων, όπου ο απαντών αντί να ξεκινά με ένα συγκεκριμένο αντικείμενο στο μυαλό του, επινοεί μια δικαιολογία για να πει όχι σε κάθε ερώτηση. Μέχρι το τέλος του παιχνιδιού, έχουν περιγράψει ένα αντικείμενο που ορίζεται εξ ολοκλήρου από τις ιδιότητες που του λείπουν.
Η απόδειξη διαγωνοποίησης του Τούρινγκ είναι μια έκδοση αυτού του παιχνιδιού όπου οι ερωτήσεις διατρέχουν την άπειρη λίστα πιθανών αλγορίθμων, ρωτώντας επανειλημμένα: "Μπορεί αυτός ο αλγόριθμος να λύσει το πρόβλημα που θα θέλαμε να αποδειχτεί μη υπολογίσιμο;"
«Είναι ένα είδος «απείρου ερωτήσεων», είπε ο Ουίλιαμς.
Για να κερδίσει το παιχνίδι, ο Turing χρειαζόταν να δημιουργήσει ένα πρόβλημα όπου η απάντηση είναι όχι για κάθε αλγόριθμο. Αυτό σήμαινε τον εντοπισμό μιας συγκεκριμένης εισόδου που κάνει τον πρώτο αλγόριθμο να βγάζει λάθος απάντηση, μια άλλη είσοδο που κάνει τον δεύτερο να αποτυγχάνει και ούτω καθεξής. Βρήκε αυτές τις ειδικές εισροές χρησιμοποιώντας ένα κόλπο παρόμοιο με αυτό που είχε χρησιμοποιήσει πρόσφατα ο Kurt Gödel αποδειχθούν ότι αυτοαναφορικοί ισχυρισμοί όπως «αυτή η δήλωση είναι αναπόδεικτη» προκάλεσαν προβλήματα στα θεμέλια των μαθηματικών.
Η βασική ιδέα ήταν ότι κάθε αλγόριθμος (ή πρόγραμμα) μπορεί να αναπαρασταθεί ως μια συμβολοσειρά 0 και 1. Αυτό σημαίνει, όπως στο παράδειγμα του προγράμματος ελέγχου σφαλμάτων, ότι ένας αλγόριθμος μπορεί να λάβει τον κώδικα ενός άλλου αλγορίθμου ως είσοδο. Κατ 'αρχήν, ένας αλγόριθμος μπορεί να λάβει ακόμη και τον δικό του κώδικα ως είσοδο.
Με αυτή τη διορατικότητα, μπορούμε να ορίσουμε ένα μη υπολογίσιμο πρόβλημα όπως αυτό στην απόδειξη του Turing: «Δεδομένου μιας συμβολοσειράς εισόδου που αντιπροσωπεύει τον κώδικα ενός αλγορίθμου, βγάζουμε 1 εάν αυτός ο αλγόριθμος βγάζει 0 όταν ο δικός του κώδικας είναι η είσοδος. Διαφορετικά, έξοδος 0." Κάθε αλγόριθμος που προσπαθεί να λύσει αυτό το πρόβλημα θα παράγει λάθος έξοδο σε τουλάχιστον μία είσοδο — δηλαδή, την είσοδο που αντιστοιχεί στον δικό του κώδικα. Αυτό σημαίνει ότι αυτό το διεστραμμένο πρόβλημα δεν μπορεί να λυθεί με κανέναν αλγόριθμο.
Τι δεν μπορεί να κάνει η άρνηση
Οι επιστήμονες υπολογιστών δεν είχαν ακόμη ολοκληρώσει τη διαγωνοποίηση. Το 1965, ο Juris Hartmanis και ο Richard Stearns προσάρμοσαν το επιχείρημα του Turing αποδειχθούν ότι δεν δημιουργούνται όλα τα υπολογίσιμα προβλήματα ίσα — ορισμένα είναι εγγενώς πιο δύσκολα από άλλα. Αυτό το αποτέλεσμα ξεκίνησε το πεδίο της θεωρίας της υπολογιστικής πολυπλοκότητας, που μελετά τη δυσκολία των υπολογιστικών προβλημάτων.
Αλλά η θεωρία πολυπλοκότητας αποκάλυψε επίσης τα όρια της αντίθετης μεθόδου του Turing. Το 1975, ο Theodore Baker, ο John Gill και ο Robert Solovay αποδείχθηκε ότι πολλά ανοιχτά ερωτήματα στη θεωρία πολυπλοκότητας δεν μπορούν ποτέ να επιλυθούν μόνο με τη διαγωνοποίηση. Το κυριότερο μεταξύ αυτών είναι το περίφημο πρόβλημα P έναντι NP, το οποίο ρωτά εάν όλα τα προβλήματα με εύκολα ελεγχόμενες λύσεις είναι επίσης εύκολο να λυθούν με τον σωστό έξυπνο αλγόριθμο.
Τα τυφλά σημεία της διαγωνοποίησης είναι άμεση συνέπεια του υψηλού επιπέδου αφαίρεσης που την κάνει τόσο ισχυρή. Η απόδειξη του Turing δεν περιελάμβανε κανένα μη υπολογίσιμο πρόβλημα που θα μπορούσε να προκύψει στην πράξη - αντίθετα, επινόησε ένα τέτοιο πρόβλημα εν κινήσει. Άλλες αποδείξεις διαγωνιοποίησης είναι εξίσου μακριά από τον πραγματικό κόσμο, επομένως δεν μπορούν να επιλύσουν ερωτήσεις όπου έχουν σημασία οι λεπτομέρειες του πραγματικού κόσμου.
«Χειρίζονται τον υπολογισμό από απόσταση», είπε ο Williams. «Φαντάζομαι έναν τύπο που αντιμετωπίζει ιούς και έχει πρόσβαση σε αυτούς μέσα από κάποιο ντουλαπάκι».
Η αποτυχία της διαγωνοποίησης ήταν μια πρώιμη ένδειξη ότι η επίλυση του προβλήματος P έναντι NP θα ήταν ένα μακρύ ταξίδι. Όμως, παρά τους περιορισμούς της, η διαγωνοποίηση παραμένει ένα από τα βασικά εργαλεία στο οπλοστάσιο των θεωρητικών της πολυπλοκότητας. Το 2011, ο Williams το χρησιμοποίησε μαζί με μια σειρά από άλλες τεχνικές για να αποδειχθούν ότι ένα συγκεκριμένο περιορισμένο μοντέλο υπολογισμού δεν μπορούσε να λύσει ορισμένα εξαιρετικά δύσκολα προβλήματα - ένα αποτέλεσμα που διέφευγε τους ερευνητές για 25 χρόνια. Απείχε πολύ από την επίλυση του P έναντι του NP, αλλά εξακολουθούσε να αντιπροσωπεύει σημαντική πρόοδο.
Αν θέλετε να αποδείξετε ότι κάτι δεν είναι δυνατό, μην υποτιμάτε τη δύναμη του να λέτε απλώς όχι.
- SEO Powered Content & PR Distribution. Ενισχύστε σήμερα.
- PlatoData.Network Vertical Generative Ai. Ενδυναμώστε τον εαυτό σας. Πρόσβαση εδώ.
- PlatoAiStream. Web3 Intelligence. Ενισχύθηκε η γνώση. Πρόσβαση εδώ.
- PlatoESG. Αυτοκίνητο / EVs, Ανθρακας, Cleantech, Ενέργεια, Περιβάλλον, Ηλιακός, Διαχείριση των αποβλήτων. Πρόσβαση εδώ.
- PlatoHealth. Ευφυΐα βιοτεχνολογίας και κλινικών δοκιμών. Πρόσβαση εδώ.
- ChartPrime. Ανεβάστε το Trading Game σας με το ChartPrime. Πρόσβαση εδώ.
- BlockOffsets. Εκσυγχρονισμός της περιβαλλοντικής αντιστάθμισης ιδιοκτησίας. Πρόσβαση εδώ.
- πηγή: https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/
- :έχει
- :είναι
- :δεν
- :που
- ][Π
- $UP
- 1
- 20
- 2011
- 25
- a
- αφαίρεση
- Λογαριασμός
- πριν
- Alan
- Alan Turing
- αλγόριθμος
- αλγοριθμικά
- αλγόριθμοι
- Όλα
- alone
- Επίσης
- μεταξύ των
- an
- και
- Άλλος
- απάντηση
- κάθε
- πλησιάζω
- ΕΙΝΑΙ
- επιχείρημα
- σηκώνομαι
- Οπλοστάσιο
- AS
- ζητώ
- At
- αρτοποιός
- βασίζονται
- BE
- γίνονται
- πίσω
- Κομμάτι
- Κουτί
- Χτίζει
- αλλά
- by
- που ονομάζεται
- cambridge
- CAN
- περίπτωση
- Αιώνας
- ορισμένες
- έλεγχος
- αρχηγός
- κωδικός
- περίπλοκο
- υπολογισμός
- υπολογιστή
- Πληροφορική
- υπολογιστές
- Εξετάστε
- κατασκευάσει
- Περιέχει
- αντίθετος
- συντεταγμένη
- διορθώσει
- Αντίστοιχος
- σκάφος
- δημιουργήθηκε
- μοιρασιά
- δεκαετίες
- απόφαση
- ορίζεται
- ορίζεται
- περιγράφεται
- Παρά
- καθέκαστα
- διαφορετικές
- Δυσκολία
- κατευθύνει
- απόσταση
- Διακεκριμένος
- do
- Όχι
- πράξη
- Μην
- κάθε
- Νωρίς
- εύκολα
- εύκολος
- είτε
- τέλος
- αρκετά
- εξασφαλίζω
- εξ ολοκλήρου
- ίσος
- εξίσου
- Ισοδύναμος
- σφάλμα
- λάθη
- Even
- Κάθε
- εξετάζω
- παράδειγμα
- αποκλειστικά
- εκτελέστηκε
- ύπαρξη
- εξαιρετικά
- ΑΠΟΤΥΓΧΑΝΩ
- αποτυγχάνει
- Αποτυχία
- πασίγνωστη και
- μακριά
- Far Cry
- γρηγορότερα
- πεδίο
- Εύρεση
- Όνομα
- πέντε
- Αναρρίπτω
- ροή
- εστιάζοντας
- Για
- μορφή
- Βρέθηκαν
- Ιδρύματα
- ιδρυτής
- από
- παιχνίδι
- γενικού σκοπού
- παράγουν
- παίρνω
- να πάρει
- δεδομένου
- Δίνοντας
- γκολ
- μετάβαση
- αποφοιτήσουν
- πρωτοποριακή
- Άνθρωπος
- είχε
- λαβή
- Σκληρά
- σκληρότερα
- ιπποσκευή
- Έχω
- he
- κεφάλι
- Ψηλά
- του
- ιστορία
- Πως
- HTTPS
- i
- προσδιορισμό
- IEEE
- if
- φαντάζομαι
- φανταστείτε
- in
- ένδειξη
- Άπειρος
- Άπειρο
- εισαγωγή
- είσοδοι
- διορατικότητα
- αντί
- Ινστιτούτο
- Internet
- εγγενώς
- εμπλέκω
- IT
- ΤΟΥ
- εαυτό
- Γιάννης
- μόλις
- Κλειδί
- Kurt
- αργότερα
- ξεκίνησε
- ελάχιστα
- Επίπεδο
- βρίσκεται
- Μου αρέσει
- περιορισμός
- περιορισμούς
- όρια
- γραμμή
- Λιστα
- Λίστες
- λογική
- Μακριά
- που
- περιοδικό
- μεγάλες
- ΚΑΝΕΙ
- ευχείριστος
- πολοί
- Μασαχουσέτη
- Ινστιτούτο Τεχνολογίας της Μασαχουσέτης
- μαθηματικός
- μαθηματικά
- ύλη
- μέσα
- σήμαινε
- μέθοδος
- μέθοδοι
- ενδέχεται να
- νου
- Λείπει
- λάθη
- MIT
- μοντέλο
- ΜΟΝΤΕΡΝΑ
- περισσότερο
- πλέον
- μετακινήσετε
- πολύ
- όνομα
- και συγκεκριμένα
- σχεδόν
- που απαιτούνται
- ανάγκες
- αρνητικός
- ποτέ
- Νέα
- Όχι.
- τώρα
- αριθμός
- αντικείμενο
- of
- συχνά
- on
- μια φορά
- ONE
- αποκλειστικά
- ανοίξτε
- Βελτιστοποίηση
- or
- πρωτότυπο
- ΑΛΛΑ
- Άλλα
- αλλιώς
- δικός μας
- παραγωγή
- δική
- Χαρτί
- Ειδικότερα
- πληρωμές
- person
- Πρωτοποριακή
- Μέρος
- Πλάτων
- Πληροφορία δεδομένων Plato
- Πλάτωνα δεδομένα
- παίζει
- δυνατός
- δύναμη
- ισχυρός
- πρακτική
- ανάγκη
- Ακμή
- αρχή
- Πρόβλημα
- προβλήματα
- διαδικασία
- διαδικασια μας
- παράγει
- παράγει
- Πρόγραμμα
- Προγράμματα
- Πρόοδος
- απόδειξη
- αποδείξεις
- Αποδείξτε
- αποδείχθηκε
- ιδιότητες
- Quantamamagazine
- ερώτηση
- Ερωτήσεις
- μάλλον
- πραγματικός
- πραγματικό κόσμο
- πρόσφατα
- λείψανα
- επαναλαμβάνω
- ΚΑΤ 'ΕΠΑΝΑΛΗΨΗ
- εκπροσωπώ
- εκπροσωπούνται
- εκπροσωπούν
- ερευνητές
- επιλυθεί
- επίλυση
- περιορισμένος
- αποτέλεσμα
- Αποκαλυφθε'ντα
- Richard
- ελεγχθεί
- δεξιά
- ROBERT
- τρέξιμο
- Είπε
- ίδιο
- λένε
- ρητό
- σάρωσης
- Επιστήμη
- Επιστήμονας
- επιστήμονες
- Αναζήτηση
- Δεύτερος
- φαινομενικώς
- φαίνεται
- σειρά
- Σιάμ
- παρόμοιες
- Ομοίως
- Απλούς
- απλοποιημένη
- απλά
- αφού
- ΕΞΙ
- επιβραδύνουν
- So
- Λύσεις
- SOLVE
- Λύει
- Επίλυση
- μερικοί
- κάτι
- ειδική
- κηλίδες
- Εκκίνηση
- Ξεκινήστε
- Δήλωση
- στελέχη
- Ακόμη
- στάση
- αποθηκεύονται
- ειλικρινής
- Στρατηγική
- Σπάγγος
- Φοιτητής
- μελέτες
- μελετώντας
- τέτοιος
- σύνταξη
- Πάρτε
- Έργο
- τεχνικές
- Τεχνολογία
- όροι
- από
- ότι
- Η
- Τους
- τότε
- θεωρητικός
- θεωρία
- Εκεί.
- Αυτοί
- αυτοί
- Σκέψη
- αυτό
- εκείνοι
- Μέσω
- εγκάρσιος
- προς την
- μαζι
- εργαλεία
- ΚΙΝΗΣΗ στους ΔΡΟΜΟΥΣ
- ταλαιπωρία
- αληθής
- προσπαθώ
- αναδιάρθρωσης
- ΣΤΡΟΦΗ
- Γύρισε
- πανταχού παρών
- μέχρι
- χρήση
- μεταχειρισμένος
- χρησιμοποιώντας
- εκδοχή
- Εναντίον
- ιούς
- θέλω
- ήθελε
- ήταν
- Τρόπος..
- we
- webp
- ΛΟΙΠΌΝ
- καλά καθορισμένη
- Τι
- πότε
- αν
- Ποιό
- Ο ΟΠΟΊΟΣ
- θα
- Williams
- νίκη
- με
- λειτουργεί
- κόσμος
- θα
- Λανθασμένος
- χρόνια
- ακόμη
- Εσείς
- Σας
- zephyrnet