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

Αλλά αυτοί οι υπολογιστές, που φαίνεται να έχουν απεριόριστες δυνατότητες - έχουν περιορισμούς; Υπάρχουν προβλήματα που οι υπολογιστές δεν μπορούν να λύσουν;

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

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

Υπολογιστής

Τι είναι ένας υπολογιστής? Τι είναι το πρόβλημα;

Στο σχολείο, διδάσκουμε συχνά ένα νοητικό μοντέλο προβλημάτων και λειτουργιών που λέει κάτι τέτοιο:

Η συνάρτηση είναι μια διαδικασία που εφαρμόζετε σε μια είσοδο x για να βρείτε μια έξοδο f (x).

Αποδεικνύεται ότι το μαθηματικός ορισμός είναι διαφορετικό:

Η συνάρτηση είναι ένα σύνολο ζευγών που ταξινομούνται έτσι ώστε το πρώτο στοιχείο κάθε ζεύγους να προέρχεται από ένα σύνολο X (ονομάζεται τομέας), το δεύτερο στοιχείο κάθε ζεύγους προέρχεται από ένα σύνολο Y (που ονομάζεται συν-τομέας ή εύρος) και κάθε στοιχείο του τομέα αντιστοιχίζεται με ακριβώς ένα στοιχείο του εύρους.

Αυτό ήταν αρκετό. Αλλά τι ακριβώς σημαίνει αυτό;

Αυτός ο ορισμός μας λέει ότι ένας υπολογιστής είναι μια μηχανή για υπολογιστικές λειτουργίες.

Γιατί;

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

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

Γιατί δεν μπορούν όλες οι συναρτήσεις να περιγραφούν ως αλγόριθμος.

Κανόνες παιχνιδιού

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

Ας καλέσουμε το αλφάβητο της μηχανής εισαγωγής, το οποίο είναι ένα σύνολο ακολουθίας χαρακτήρων από κάποιο πεπερασμένο σύνολο. Για παράδειγμα, το αλφάβητο του μηχανήματος μπορεί να είναι δυαδικό (0s και 1s) ή μπορεί να είναι το σύνολο χαρακτήρων ASCII. Οποιαδήποτε πεπερασμένη ακολουθία χαρακτήρων είναι μια συμβολοσειρά - για παράδειγμα '0110.'

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

Λαμβάνοντας υπόψη αυτές τις παραμέτρους, είναι σημαντικό να χαρακτηριστεί ένας ακόμη τύπος: μια συλλογή συμβολοσειρών χαρακτήρων. Ίσως μας ενδιαφέρει το σύνολο των χορδών που δέχεται ένα μηχάνημα, ή ίσως χτίζουμε μια μηχανή που δέχεται χορδές σε ένα συγκεκριμένο σετ και όχι σε άλλα, ή ίσως ρωτάμε αν είναι δυνατόν να σχεδιάσουμε μια μηχανή που να δέχεται όλα συγκεκριμένα σετ και όχι σε άλλους.

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

Ένας σημαντικός χειριστής είναι ο χειριστής αστέρι Kleene που χρησιμοποιείται επίσης με κανονικές εκφράσεις. Αυτό μπορεί να θεωρηθεί ως ένωση όλων των δυνατών γλωσσικών δυνάμεων. Για παράδειγμα, εάν η γλώσσα μας ΠΡΟΣ ΤΟ είναι το σύνολο των συμβολοσειρών χαρακτήρων {‘01’, ‘1’}, τότε μέλος του ΠΡΟΣ ΤΟ* είναι η συμβολοσειρά χαρακτήρων '0101111'.

Λογιστική

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

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

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

Λοιπόν, δεν είναι τόσο κακό. Ένα απίστευτα άπειρο σετ είναι ένα που μπορεί να απαριθμηθεί. Είναι πιθανό να πούμε: αυτό είναι το πρώτο στοιχείο, αυτό είναι το δεύτερο στοιχείο, και ούτω καθεξής, τελικά εκχωρώντας έναν αριθμό σε κάθε στοιχείο στο σύνολο. Πάρτε για παράδειγμα το σύνολο των ζυγών αριθμών. Μπορούμε να πούμε ότι το 2 είναι το πρώτο, το 4 το δεύτερο, το 6 το τρίτο και ούτω καθεξής. Τέτοια σύνολα είναι μετρήσιμα άπειρα ή μετρήσιμα.

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

Πολλά λογιστικά προγράμματα

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

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

Για να επαναλάβω:

κόμβος js τι είναι

Το σύνολο όλων των συμβολοσειρών χαρακτήρων σε οποιοδήποτε αλφάβητο (π.χ. Σύνολο όλων των προγραμμάτων υπολογιστή) είναι μετρήσιμο.

Αμέτρητες πολλές γλώσσες

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

Το σύνολο όλων των γλωσσών σε οποιοδήποτε αλφάβητο είναι μετρήσιμο.

Για άλλη μια φορά, δεν καλύπτουμε η απόδειξη εδώ.

Συνέπειες

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

Γιατί;

Ας υποθέσουμε ΠΡΟΣ ΤΟ είναι το σύνολο χαρακτήρων ASCII. ο Χαρακτήρες ASCII είναι απαραίτητα μόνο για τη σύνταξη ενός προγράμματος υπολογιστή. Μπορούμε να δούμε ότι το σύνολο των συμβολοσειρών που αντιπροσωπεύουν, για παράδειγμα, προγράμματα JavaScript είναι ένα υποσύνολο του ΠΡΟΣ ΤΟ* (εδώ, ο * είναι ο χειριστής αστέρων της Kleene). Η επιλογή του JavaScript είναι αυθαίρετη. Δεδομένου ότι αυτό το σύνολο προγραμμάτων είναι ένα υποσύνολο ενός μετρήσιμου συνόλου, έχουμε ότι το σύνολο προγραμμάτων JavaScript είναι μετρήσιμο.

Επίσης, ας το σκεφτούμε αυτό για οποιαδήποτε γλώσσα μεγάλο μπορούμε να ορίσουμε κάποια λειτουργία φά που αξιολογεί σε 1 εάν υπάρχει συμβολοσειρά Χ Είναι μέσα μεγάλο και 0 διαφορετικά. Όλες αυτές οι λειτουργίες είναι διαφορετικές. Επειδή υπάρχει αντιστοιχία 1: 1 με το σύνολο όλων των γλωσσών και επειδή το σύνολο όλων των γλωσσών είναι μετρήσιμο, έχουμε ότι το σύνολο όλων αυτών των λειτουργιών είναι μετρήσιμο.

Εδώ είναι το σημείο σε βάθος:

Δεδομένου ότι το σύνολο όλων των έγκυρων προγραμμάτων είναι μετρήσιμο, αλλά το σύνολο των λειτουργιών δεν είναι, τότε πρέπει να υπάρχουν κάποιες συναρτήσεις για τις οποίες απλά δεν μπορούμε να γράψουμε προγράμματα.

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

Τώρα το ερώτημα είναι: 'Πώς είναι αυτά τα προβλήματα;' Πριν συνεχίσουμε να περιγράφουμε αυτά τα προβλήματα, πρέπει πρώτα να μοντελοποιήσουμε τον υπολογισμό με γενικευμένο τρόπο.

Μηχανές σκλήρυνσης

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

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

• Το τρέχον σύμβολο κάτω από το κεφάλι και

• Η εσωτερική κατάσταση του μηχανήματος, η οποία ενημερώνεται επίσης όταν πληκτρολογείται το σύμβολο

Αυτό είναι όλο.

Καθολικότητα

Το 1926, ο Alan Turing όχι μόνο ανέπτυξε τη μηχανή Turing αλλά είχε επίσης πολλές σημαντικές ιδέες σχετικά με τη φύση του υπολογισμού όταν έγραψε το διάσημο άρθρο του, 'On Computable Numbers'. Συνειδητοποίησε ότι ένα πρόγραμμα υπολογιστή θα μπορούσε να θεωρηθεί ως είσοδος σε έναν υπολογιστή. Με αυτήν την άποψη, είχε την όμορφη ιδέα ότι μια μηχανή Turing θα μπορούσε να προσομοιώσει ή να εκτελέσει αυτήν την είσοδο.

Ενώ θεωρούμε δεδομένες αυτές τις ιδέες σήμερα, στην εποχή του Turing η ιδέα μιας τέτοιας καθολικής μηχανής ήταν η σημαντική ανακάλυψη που επέτρεψε στον Turing να αναπτύξει άλυτα προβλήματα.

Διατριβή Εκκλησίας-Turing

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

Όλα τα υπολογιστικά στοιχεία μπορούν να υπολογιστούν από μια μηχανή Turing.

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

Αναγνώριση και αποφασιστικότητα

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

Μια γλώσσα είναι αναγνωρίσιμη αν υπάρχει μια μηχανή Turing που την αναγνωρίζει.

τι είναι η θεωρία gestalt

Υ

Μια γλώσσα είναι αποφασιστική εάν υπάρχει μια μηχανή Turing που την αποφασίζει.

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

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

Ανασφάλεια

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

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

Μπορούμε να το δοκιμάσουμε χρησιμοποιώντας τη μηχανή Turing. Οι μηχανές σκλήρυνσης μπορούν να περιγραφούν ως χορδές χαρακτήρων, οπότε υπάρχει ένας μετρήσιμος αριθμός. Ας υποθέσουμε ότι ο Μ_ένας, Μ₂και ούτω καθεξής αποτελούν το σύνολο όλων των μηχανών Turing. Θα καθορίσουμε την ακόλουθη συνάρτηση:

f (i, j) = 1 si Μ_Εγώαποδεχεσαιι>, Το αντίθετο

Εδώ, είναι η σύνταξη για 'κωδικοποίηση συμβολοσειράς Μ' και αυτή η συνάρτηση αντιπροσωπεύει το πρόβλημα της παραγωγής 1 εάν το Μ_Εγώσταματά όταν δέχεστε το Μ_ιως είσοδος και έξοδος 0, αντίθετα. Σημειώστε ότι ο Μ_Εγώπρέπει να σταματήσει (δηλ. να είστε παραβάτης συμφωνίας). Αυτό είναι απαραίτητο αφού θέλουμε να περιγράψουμε μια αναποφάσιστη συνάρτηση (δηλαδή, πρόβλημα χωρίς λύση).

Τώρα, ας ορίσουμε επίσης μια γλώσσα μεγάλο που αποτελείται από κωδικοποιήσεις συμβολοσειρών μηχανών Turing που ΔΕΝ δέχονται τις δικές τους περιγραφές:

L =

Για παράδειγμα, κάποια μηχανή Μ_έναςμπορεί έξοδος 0 για είσοδοένας& gt, ενώ άλλο μηχάνημα M₂μπορεί να δώσει έξοδο 1 για είσοδο2>. Για να αποδείξουμε ότι αυτή η γλώσσα είναι αναπόφευκτη, ρωτάμε τι κάνει ο Μ_μεγάλο, το μηχάνημα που αποφασίζει τη γλώσσα L, όταν δίνεται η δική του περιγραφήμεγάλο> ως είσοδος. Υπάρχουν δύο ευκαιρίες:

Μ_μεγάλοαποδεχεσαιμεγάλο>

ή

Μ_μεγάλοαρνείταιμεγάλο>

Σι Μ_μεγάλοαποδέχεται τη δική του κωδικοποίηση, έτσι σημαίνειμεγάλο> δεν είναι στη γλώσσα L. Ωστόσο, εάν συνέβαινε αυτό, τότε M_μεγάλοΔεν έπρεπε να αποδεχτώ την κωδικοποίησή σας. Από την άλλη πλευρά, εάν ο Μ_μεγάλοδεν δέχεται τη δική του κωδικοποίησημεγάλο> είναι στη γλώσσα L, τότε M_μεγάλοθα έπρεπε να έχει αποδεχτεί την κωδικοποίηση συμβολοσειράς σας.

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

Διακοπή του προβλήματος

Παρόλο που το πρόβλημα που μόλις περιγράψαμε μπορεί να μην φαίνεται σχετικό, μπορεί να μειωθεί σε πρόσθετα άλυτα προβλήματα πρακτικής σημασίας, ιδίως πρόβλημα κράτησης :

Η γλώσσα των κωδικοποιήσεων μηχανών Turing που σταματούν στην κενή συμβολοσειρά.

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

Περίληψη

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

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

Αφήνοντας πίσω τις υπολογιστικές λειτουργίες και τις γλώσσες, συζητάμε τώρα την υπολογιστική πολυπλοκότητα, εξετάζοντας τον αποτελεσματικό υπολογισμό και το περίφημο P vs. ΝΡ.

Περίπλοκο

Αργή εναντίον Γρήγορα

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

Για παράδειγμα, ας υποθέσουμε ότι είστε υπεύθυνοι για την ανάπτυξη αλγορίθμων για μια online υπηρεσία γνωριμιών και κάποιος θέτει την ερώτηση, 'Μπορούν όλοι να πάρουν ραντεβού;' Η απάντηση συνοδεύεται από ταίριασμα συμβατών ατόμων έτσι ώστε όλοι να ταιριάζουν. Αποδεικνύεται ότι υπάρχουν αποτελεσματικοί αλγόριθμοι για την επίλυση αυτού του προβλήματος. Αυτό το πρόβλημα βρίσκεται στο σετ Π .

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

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

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

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

Μέχρι την τελευταία, NP-πλήρης είναι το σύνολο των προβλημάτων που είναι τα πιο δύσκολα προβλήματα Για παράδειγμα . Είναι γνωστοί ως το πιο δύσκολο, επειδή υπάρχει πρόβλημα στο Για παράδειγμα μπορεί να μετατραπεί αποτελεσματικά σε NPC . Ως αποτέλεσμα, εάν κάποιος εντοπίσει μια αποτελεσματική λύση σε ένα πρόβλημα στο NPC , κάθε είδους Για παράδειγμα θα απορροφηθεί από Π . Το πρόβλημα της αδελφότητας βρίσκεται επίσης NPC

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

Ευκρίνεια ιχνηλασιμότητας

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

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

ερώτημα πολυμέσων για όλες τις συσκευές

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

Στην πραγματικότητα, μπορούμε να είμαστε ακόμη πιο διακριτικοί. Αντί να ζητάμε τη συντομότερη διαδρομή (P), μπορούμε να ζητήσουμε τη μεγαλύτερη διαδρομή χωρίς κόμβους. Αποδεικνύεται ότι το πρόβλημα με τη μεγαλύτερη διαδρομή είναι επίσης πλήρης NP.

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

Περίληψη

Σε αυτό το τεστ πολυπλοκότητας, ορίζουμε τις προβληματικές κλάσεις P και NP. Το P αντιπροσωπεύει ανεπίσημα προβλήματα που μπορούν να επιλυθούν αποτελεσματικά από έναν υπολογιστή, ενώ το NP αντιπροσωπεύει αυτά που είναι αποτελεσματικά επαληθεύσιμα.

Κανείς δεν μπόρεσε να δείξει ότι το P δεν είναι ίσο με το NP. Εάν αυτές οι δύο κατηγορίες προβλημάτων είναι ισοδύναμες, είναι αυτό που είναι γνωστό ως P εναντίον NP και είναι το πιο σημαντικό ανοιχτό πρόβλημα στη θεωρητική πληροφορική σήμερα, αν όχι όλα τα μαθηματικά. Στην πραγματικότητα, το 2000, το Clay Math Institute ονόμασε το πρόβλημα P εναντίον Το NP ως μία από τις επτά πιο σημαντικές ανοιχτές ερωτήσεις στα μαθηματικά και έχει προσφέρει ανταμοιβή εκατομμυρίου δολαρίων για ένα τεστ που καθορίζει τη λύση σε αυτό το πρόβλημα.

συμπέρασμα

Σε αυτό το άρθρο ερευνούμε τα βασίλεια της υπολογιστικότητας και της πολυπλοκότητας, απαντώντας σε μεγάλες ερωτήσεις όπως 'Τι είναι ένας υπολογιστής;' Ενώ οι λεπτομέρειες μπορεί να είναι συντριπτικές, υπάρχουν πολλά βαθιά μαθήματα που αξίζει να θυμάστε:

• Υπάρχουν μερικά πράγματα που απλά δεν μπορούν να υπολογιστούν, όπως το πρόβλημα διακοπής.

• Υπάρχουν ορισμένα πράγματα που δεν μπορούν να υπολογιστούν αποτελεσματικά, όπως προβλήματα στο NPC.

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