Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μΧωρίς σύνοψη επεξεργασίας |
|||
Γραμμή 1:
Η '''θεωρία υπολογισμού''' είναι ο κλάδος της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]] που πραγματεύεται το εάν και το πόσο αποδοτικά είναι δυνατόν να λυθεί κάποιο πρόβλημα με χρήση κάποιου [[αλγόριθμος|αλγορίθμου]] σε ένα [[υπολογιστικό μοντέλο]], μια αφηρημένη [[μαθηματικά|μαθηματική]] έννοια ορισμένη με αυστηρούς κανόνες. Ο τομέας διαιρείται σε δύο κύριους κλάδους: τη '''θεωρία υπολογισιμότητας''' και τη [[θεωρία πολυπλοκότητας]], αλλά και οι δύο εφαρμόζονται σε μοντέλα υπολογισμού. Η θεωρία πολυπλοκότητας παρουσιάζει ομοιότητες με την [[ανάλυση αλγορίθμων]], έναν άλλο θεμελιώδη κλάδο της επιστήμης υπολογιστών, ο οποίος όμως ενδιαφέρεται για την εύρεση των ιδιοτήτων ενός συγκεκριμένου αλγορίθμου που επιλύει κάποιο υπολογιστικό πρόβλημα, και όχι για τις εγγενείς υπολογιστικές ιδιότητες του ίδιου του προβλήματος.
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη της έννοιας του υπολογισμού, οι επιστήμονες αξιοποιούν διάφορες διατυπώσεις υπολογιστικών μοντέλων, αλλά συνηθέστερη είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναν [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη [[Μνήμη υπολογιστή|μνήμη]], αν και η μνήμη αυτή είναι προσβάσιμη μόνο κατά μικρά διακριτά τμήματα. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή μαθηματική διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, ενώ κατά πολλούς αντιπροσωπεύει το ισχυρότερο εφικτό μοντέλο υπολογισμού. Αυτό σημαίνει ότι ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά αν και μόνο αν υπάρχει μηχανή Τούρινγκ που το επιλύει. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή με επαρκή μνήμη.
Η θεωρία υπολογισμού για να φτάσει στα συμπεράσματά της αξιοποιεί το γνωστικό πεδίο των [[τυπική γλώσσα|τυπικών γλωσσών]], καθώς κάθε πρόβλημα δυνάμενο να επιλυθεί αλγοριθμικά μπορεί να εκφραστεί ως πρόβλημα ανάγνωσης ή παραγωγής μίας τυπικής γλώσσας. Αυτή η επικάλυψη της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]] με τη [[μαθηματική λογική]] και τη [[γλωσσολογία]] είχε ως αποτέλεσμα την ανάπτυξη [[συντακτική ανάλυση (υπολογιστές)|συντακτικών]] και [[λεκτική ανάλυση (υπολογιστές)|λεκτικών]] αναλυτών για την εύκολη κατασκευή [[μεταγλωττιστής|μεταγλωττιστών]].
| |||