Θεωρία υπολογισμού
Η θεωρία υπολογισμού[2] είναι ο κλάδος της θεωρητικής πληροφορικής που πραγματεύεται το εάν και το πόσο αποδοτικά είναι δυνατόν να λυθεί κάποιο πρόβλημα με χρήση κάποιου αλγορίθμου σε ένα υπολογιστικό μοντέλο, μια αφηρημένη μαθηματική έννοια ορισμένη με αυστηρούς κανόνες. Ο τομέας διαιρείται σε δύο κύριους κλάδους: τη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, αλλά και οι δύο εφαρμόζονται σε μοντέλα υπολογισμού. Η θεωρία πολυπλοκότητας παρουσιάζει ομοιότητες με την ανάλυση αλγορίθμων, έναν άλλο θεμελιώδη κλάδο της επιστήμης υπολογιστών, ο οποίος όμως ενδιαφέρεται για την εύρεση των ιδιοτήτων ενός συγκεκριμένου αλγορίθμου που επιλύει κάποιο υπολογιστικό πρόβλημα, και όχι για τις εγγενείς υπολογιστικές ιδιότητες του ίδιου του προβλήματος.
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη της έννοιας του υπολογισμού, οι επιστήμονες αξιοποιούν διάφορες διατυπώσεις υπολογιστικών μοντέλων, αλλά συνηθέστερη είναι η μηχανή Τούρινγκ. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναν προσωπικό υπολογιστή με άπειρη μνήμη, αν και η μνήμη αυτή είναι προσβάσιμη μόνο κατά μικρά διακριτά τμήματα. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή μαθηματική διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, ενώ κατά πολλούς αντιπροσωπεύει το ισχυρότερο εφικτό μοντέλο υπολογισμού. Αυτό σημαίνει ότι ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά αν και μόνο αν υπάρχει μηχανή Τούρινγκ που το επιλύει. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή με επαρκή μνήμη.
Η θεωρία υπολογισμού για να φτάσει στα συμπεράσματά της αξιοποιεί το γνωστικό πεδίο των τυπικών γλωσσών, καθώς κάθε πρόβλημα δυνάμενο να επιλυθεί αλγοριθμικά μπορεί να εκφραστεί ως πρόβλημα ανάγνωσης ή παραγωγής μίας τυπικής γλώσσας. Αυτή η επικάλυψη της επιστήμης υπολογιστών με τη μαθηματική λογική και τη γλωσσολογία είχε ως αποτέλεσμα την ανάπτυξη συντακτικών και λεκτικών αναλυτών για την εύκολη κατασκευή μεταγλωττιστών.
Τυπικές γραμματικές
ΕπεξεργασίαΣτην επιστήμη υπολογιστών μια τυπική γραμματική (formal grammar) είναι μια αφηρημένη δομή που περιγράφει μια τυπική γλώσσα επακριβώς, δηλαδή είναι ένα σύνολο κανόνων που απεικονίζουν μαθηματικώς το σύνολο, (συνήθως απειροσύνολο), των πεπερασμένου μήκους στοιχειοσειρών / συμβολοσειρών που σχηματίζονται με διακριτά στοιχεία / σύμβολα (π.χ. γράμματα), τα οποία ανήκουν σε ένα σύνολο, συνήθως πεπερασμένο, που το λέμε αλφάβητο. Οι τυπικές γραμματικές ονομάστηκαν έτσι κατ’ αναλογία των γραμματικών των γλωσσών που μιλούν οι άνθρωποι, αλλά τα αλφάβητά τους δεν περιέχουν κατ’ ανάγκη γράμματα. Οι τυπικές γραμματικές διαχωρίζονται σε δυο κύριες κατηγορίες: γενετικές (generative) και αναλυτικές (analytic).[3]
Μια γενετική γραμματική, η οποία θα μπορούσε να ονομάζεται γεννητική ή παραγωγική γραμματική, είναι ένα σύνολο κανόνων με το οποίο όλες οι συμβολοσειρές που μπορούν να υπάρξουν σε μια γλώσσα μπορούν να παραχθούν με διαδοχικά επιθέματα ξεκινώντας από ένα προκαθορισμένο αρχικό σύμβολο δημιουργίας στοιχειοσειράς. Μια γενετική γραμματική ουσιαστικά είναι η τυπική μορφή του αλγορίθμου παραγωγής στοιχειοσειρών που ανήκουν στη γλώσσα.
- Συνοπτικά για την γενετική γραμματική :
- λειτουργεί ως δημιουργός στοιχειοσειρών της γλώσσας, δηλαδή γράφει τη γλώσσα,
- η πορεία είναι από τη γραμματική προς τις λέξεις της γλώσσας,
- εφαρμόζεται παραγωγική (top-down) προσέγγιση, από το γενικό προς το μερικό.
Μια αναλυτική γραμματική, αντιθέτως, είναι ένα σύνολο κανόνων που υποθέτουν ότι μία αυθαίρετη στοιχειοσειρά δίνεται προς επεξεργασία και με διαδοχικά βήματα ανάλυσης προκύπτει ως αποτέλεσμα η τιμή μιας λογικής μεταβλητής:
- ΑΛΗΘΗΣ, αν η στοιχειοσειρά ανήκει στη γλώσσα που περιγράφει η αναλυτική γραμματική
- ΨΕΥΔΗΣ, αν η στοιχειοσειρά δεν ανήκει στη γλώσσα που περιγράφει η αναλυτική γραμματική.
- Συνοπτικά για την αναλυτική γραμματική :
- σαρώνει τη στοιχειοσειρά, τεχνολογεί τα μέρη που την αποτελούν και τα αναγνωρίζει (συντακτικός αναλυτής (parser) ο οποίος διαβάζει τη γλώσσα),
- η πορεία είναι από τις λέξεις της γλώσσας προς τη γραμματική της,
- εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.
Βασικές αρχές
ΕπεξεργασίαΑστέρι Κλέινι ή κλειστότητα Κλέινι (Kleene Star) ενός αλφαβήτου Σ ονομάζουμε το σύνολο Σ* όλων των δυνατών συμβολοσειρών που προκύπτουν από αυτό το αλφάβητο. Πρόκειται για ένα μετρήσιμο απειροσύνολο (Συμπέρασμα 1). Γλώσσα ονομάζουμε ένα υποσύνολο του Σ* για δεδομένο αλφάβητο Σ. Το σύνολο όλων των γλωσσών που προκύπτουν από ένα αλφάβητο Σ είναι το δυναμοσύνολο (το σύνολο όλων των δυνατών υποσυνόλων) του Σ* και είναι μη μετρήσιμο απειροσύνολο (Συμπέρασμα 2). Μπορούμε να καταλήξουμε σε διάφορους πεπερασμένους τρόπους αναπαράστασης γλωσσών (ασχέτως του αν οι ίδιες οι γλώσσες είναι πεπερασμένες ή άπειρες), όμως όλοι οδηγούν σε μία συμβολοσειρά ως τρόπο αναπαράστασης μίας γλώσσας. Όμως, δεδομένου ενός αλφαβήτου αναπαράστασης Σ, υπάρχουν μετρήσιμα άπειρες συμβολοσειρές αναπαράστασης (Συμπέρασμα 1) και μη μετρήσιμα άπειρες γλώσσες (Συμπέρασμα 2). Επομένως, αφού υπάρχουν περισσότερες γλώσσες απ' ό,τι αναπαραστάσεις, αναπόφευκτα θα υπάρχουν πάντα γλώσσες που δεν μπορούμε να αναπαραστήσουμε με πεπερασμένο τρόπο.
Υπάρχουν δύο ισοδύναμοι τρόποι περιγραφής μίας γλώσσας: είτε μέσω ενός παραγωγού γλώσσας, ενός εκφραστικού μηχανισμού που περιγράφει τις έγκυρες συμβολοσειρές της συγκεκριμένης γλώσσας, είτε μέσω ενός αναγνώστη γλώσσας, ενός μαθηματικού μοντέλου-μηχανής που αποδέχεται συμβολοσειρές της συγκεκριμένης γλώσσας (τερματίζοντας θετικά αν η είσοδός του είναι συμβολοσειρά που ανήκει στη γλώσσα). Υπάρχουν διάφορες κλάσεις παραγωγών και των αντίστοιχων αναγνωστών, με την κάθε κλάση να καλύπτει ένα υπερσύνολο των γλωσσών που καλύπτει η προηγούμενη. Κατηγοριοποιούνται με την ιεραρχία Τσόμσκι, από τις πιο περιορισμένες ως τις πιο ευρείες:
Παραγωγοί Αναγνώστες 1 Κανονικές εκφράσεις Πεπερασμένα αυτόματα 2 Γραμματικές χωρίς συμφραζόμενα Αυτόματα στοίβας 3 Γραμματικές με συμφραζόμενα Γραμμικώς περιορισμένες μηχανές Τούρινγκ 4 Γενικές γραμματικές Μηχανές Τούρινγκ
Ένα αυτόματο αποτελείται από ένα σύνολο καταστάσεων στις οποίες εισέρχεται ανάλογα με το σε ποια κατάσταση βρίσκεται ήδη και ποιο σύμβολο διάβασε τελευταία από τη συμβολοσειρά εισόδου. Κάποιες από αυτές τις καταστάσεις είναι τελικές, δηλαδή αν η είσοδος εξαντληθεί όσο το αυτόματο είναι σε κάποια από αυτές η συμβολοσειρά είναι αποδεκτή. Υπάρχει ένας πίνακας μεταβάσεων που καθορίζει το σε ποια κατάσταση θα εισέλθει για κάθε περίπτωση.
Μία γλώσσα η οποία γίνεται αποδεκτή από κάποια Μηχανή Τούρινγκ[4], δηλαδή η τελευταία είναι βέβαιο ότι τερματίζει μόνο όταν δέχεται ως είσοδο συμβολοσειρά που ανήκει στη γλώσσα (διαφορετικά μπορεί να μπει σε ατέρμονα βρόχο), ονομάζεται MT-αποδεκτή. Μία γλώσσα η οποία αποφασίζεται από κάποια Μηχανή Τούρινγκ, δηλαδή η τελευταία τερματίζει για κάθε είσοδο και δίνει θετικό αποτέλεσμα αν η συμβολοσειρά ανήκει στη γλώσσα και αρνητικό αν δεν ανήκει, ονομάζεται ΜΤ-αποφασίσιμη. Επίσης η Μηχανή Τούρινγκ[1] μπορεί να γράφει σύμβολα στην ταινία εισόδου της (σε αντίθεση με τα αυτόματα) οπότε μπορεί να υπολογίζει και συναρτήσεις, δεχόμενη μία συμβολοσειρά εισόδου και παράγοντας την αντίστοιχη συμβολοσειρά εξόδου.
Τόσο στα αυτόματα όσο και στις Μηχανές Τούρινγκ υπάρχει μία παραλλαγή τους που διαθέτει ένα πανίσχυρο αλλά αντιρεαλιστικό μαθηματικό χαρακτηριστικό: τον μη ντετερμινισμό, τη δυνατότητα δηλαδή σε κάθε βήμα της λειτουργίας τους να «μαντεύουν» τη σωστή διαδρομή που πρέπει να ακολουθήσουν στη συνέχεια από ένα πλήθος δυνατών διαδρομών. Τα μη ντετερμινιστικά αυτόματα συνήθως έχουν εκθετικά λιγότερες καταστάσεις από τα ρεαλιστικά αντίστοιχα ντετερμινιστικά, ενώ οι μη ντετερμινιστικές Μηχανές Τούρινγκ ολοκληρώνουν τη λειτουργία τους σε εκθετικά λιγότερο χρόνο από τις αντίστοιχες ρεαλιστικές ντετερμινιστικές. Ώστόσο κάθε μη ντετερμινιστικό πεπερασμένο αυτόματο μπορεί να μετασχηματιστεί σε ένα ισοδύναμο ντετερμινιστικό που αναγνωρίζει την ίδια γλώσσα (έστω και με πολύ περισσότερες καταστάσεις), καθώς και κάθε μη ντετερμινιστική Μηχανή Τούρινγκ μπορεί να μετασχηματιστεί σε μία ισοδύναμη ντετερμινιστική (έστω και με πολύ μεγαλύτερη χρονική πολυπλοκότητα). Αυτή η ισοδυναμία δεν ισχύει στα αυτόματα στοίβας, αφού υπάρχουν γλώσσες χωρίς συμφραζόμενα που γίνονται αποδεκτές μόνο από μη ντετερμινιστικά αυτόματα στοίβας για τα οποία δεν υπάρχουν αντίστοιχα ντετερμινιστικά. Ειδικά για τις Μηχανές Τούρινγκ έχουν προταθεί και διάφορες άλλες παραλλαγές (πιο ρεαλιστικές, όπως π.χ. με ταινία διπλής κατεύθυνσης ή πολλαπλές κεφαλές ανάγνωσης συμβόλων) οι οποίες όμως έχει αποδειχθεί ότι επίσης είναι ισοδύναμες με την πρότυπη ντετερμινιστική Μηχανή Turing και μάλιστα με την ίδια χρονική πολυπλοκότητα.
Υπολογισιμότητα
ΕπεξεργασίαΚαθολική Μηχανή Τούρινγκ ονομάζεται μία Μηχανή Τούρινγκ που δέχεται ως είσοδο κατάλληλα κωδικοποιημένες συμβολοσειρές που συμβολίζουν άλλες Μηχανές Τούρινγκ (Μ) και μία είσοδο γι' αυτές (w) και προσομοιώνει τη λειτουργία της Μ με είσοδο w. Με αυτόν τον τρόπο κωδικοποίησης ένα οποιοδήποτε υπολογιστικό πρόβλημα μπορεί να εκφραστεί ως ένα σύνολο συμβολοσειρών, δηλαδή μία γλώσσα, και να επιλυθεί από μία κατάλληλη Μηχανή Τούρινγκ που αποφασίζει αυτή τη γλώσσα· δηλαδή τερματίζει με βεβαιότητα για όλες τις εισόδους της. Σύμφωνα λοιπόν με τη Θέση Τσερτς-Τούρινγκ η ντετερμινιστική Μηχανή Τούρινγκ που αποφασίζει μία γλώσσα είναι το έσχατο και πιο ευρύ υπολογιστικό μοντέλο, μία αυστηρή μαθηματική περιγραφή της άτυπης έννοιας του αλγορίθμου!
Αν για ένα υπολογιστικό πρόβλημα δεν μπορεί να βρεθεί μία Μηχανή Τούρινγκ που να αποφασίζει την αντίστοιχη γλώσσα, τότε το πρόβλημα αυτό είναι μη επιλύσιμο, δεν μπορεί δηλαδή να υπάρξει αλγόριθμος που το επιλύει. Ένα διάσημο μη επιλύσιμο πρόβλημα είναι το πρόβλημα του τερματισμού (η εύρεση μίας Μηχανής Τούρινγκ που αποφασίζει αν μία άλλη Μηχανή Τούρινγκ θα τερματίσει με συγκεκριμένη είσοδο ή θα πέσει σε ατέρμονα βρόχο), το οποίο χρησιμεύει ώστε να ανάγονται άλλα προβλήματα σε αυτό και να αποδεικνύεται έτσι ότι είναι μη επιλύσιμα. Η Μηχανή Τούρινγκ είναι το πιο ισχυρό μοντέλου υπολογισμού γιατί διαθέτει άπειρη μνήμη (την ταινία εισόδου / εξόδου), ενώ τα πεπερασμένα αυτόματα και τα αυτόματα στοίβας έχουν σοβαρούς περιορισμούς μνήμης (στα πρώτα η μνήμη τους είναι κωδικοποιημένη στις καταστάσεις τους ενώ τα δεύτερα έχουν επιπλέον και μια πεπερασμένη στοίβα).
Οι υπολογιστές φον Νόιμαν αλλά και άλλα μοντέλα υπολογισμού (π.χ. ορισμένα τεχνητά νευρωνικά δίκτυα) ισοδυναμούν μαθηματικώς με Καθολικές Μηχανές Τούρινγκ και γι' αυτό μπορεί σε αυτά να εκτελεστεί, με κατάλληλη κωδικοποίηση, οποιοσδήποτε αλγόριθμος.
Πολυπλοκότητα
ΕπεξεργασίαΠαρόλο που κάποια προβλήματα είναι επιλύσιμα, δεν έχει βρεθεί μέχρι στιγμής αλγόριθμος που να τα επιλύει σε λογικά χρονικά όρια· δηλαδή με πολυωνυμική και όχι εκθετική χρονική πολυπλοκότητα. Σε αυτό το σημείο συνεισφέρει η θεωρία πολυπλοκότητας: P ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε πολυωνυμικό χρόνο. NP ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή μη ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε πολυωνυμικό χρόνο αλλά όχι ντετερμινιστική (οι ισοδύναμες ντετερμινιστικές Μηχανές Τούρινγκ έχουν αυξημένη εκθετική πολυπλοκότητα). E ονομάζεται το σύνολο των γλωσσών που αναπαριστούν υπολογιστικά προβλήματα για τα οποία είναι γνωστή είτε μη ντετερμινιστική είτε ντετερμινιστική Μηχανή Τούρινγκ που τα επιλύει σε εκθετικό χρόνο. Αυτή τη στιγμή γνωρίζουμε ότι το P είναι υποσύνολο του NP και ότι το NP είναι υποσύνολο του Ε. Ωστόσο δεν γνωρίζουμε κατά πόσον αυτές οι σχέσεις είναι γνήσιου υποσυνόλου, αν και υποψιαζόμαστε ότι αυτό ισχύει. Αν αποδειχτεί ότι το P δεν είναι γνήσιο υποσύνολο του NP τότε σημαίνει ότι υπάρχουν ντετερμινιστικές Μηχανές Τούρινγκ που επιλύουν όλα τα προβλήματα του NP σε πολυωνυμικό χρόνο και απλώς δεν έχουν επινοηθεί μέχρι στιγμής. Σήμερα ωστόσο αυτό δεν θεωρείται πιθανό και οι περισσότεροι επιστήμονες εικάζουν ότι η εκθετική πολυπλοκότητα είναι εγγενής σε αυτά τα προβλήματα.[2]
Τα προβλήματα του NP που δεν φαίνεται να ανήκουν στο P έχουν την ιδιότητα να ανάγονται όλα σε ένα μικρό σύνολο βασικών και καλά μελετημένων προβλημάτων. Αυτή η ιδιότητα ονομάζεται πληρότητα και τα εν λόγω προβλήματα ονομάζονται NP-πλήρη. Έχει αποδειχθεί ότι αν ανακαλυφθεί κάποτε Μηχανή Τούρινγκ που να επιλύει κάποιο από αυτά ντετερμινιστικά σε πολυωνυμικό χρόνο (οπότε αυτό θα ανήκει στο P), τότε όλα τα NP-πλήρη προβλήματα θα ανήκουν στο P. Όπως προαναφέρθηκε ωστόσο αυτό δεν θεωρείται πιθανό.
Παραπομπές
Επεξεργασία- ↑ 1,0 1,1 De Mol, Liesbeth (2021). Zalta, Edward N., επιμ. Turing Machines (Winter 2021 έκδοση). Metaphysics Research Lab, Stanford University.
- ↑ 2,0 2,1 «ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ - ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ ΤΜΗΜΑ ΕΠΙΣΤΗΜΗΣ ΥΠΟΛΟΓΙΣΤΩΝ» (PDF).
- ↑ «Θεωρία Υπολογισμού και Πολυπλοκότητα - Κανονικές εκφράσεις -Τμήμα Πληροφορικής, Πανεπιστήμιο Κύπρου» (PDF).
- ↑ Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications. ISBN 978-0486432281.