Επιστήμη υπολογιστών

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

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

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

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

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

Ορισμός και συγγενείς επιστήμες

Γλυπτό του Άλαν Τιούρινγκ, του «πατέρα της επιστήμης υπολογιστών και της τεχνητής νοημοσύνης».

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

• Κυβερνητική
• Γλωσσολογία
• Μαθηματική λογική
• Στατιστική
• Εφαρμοσμένα μαθηματικά
• Ηλεκτρονική
• Επιστήμη ηλεκτρολόγου μηχανικού
• Γνωσιακή επιστήμη
• Υπολογιστική επιστήμη
  • Υπολογιστικά μαθηματικά
  • Υπολογιστική φυσική
  • Υπολογιστική χημεία
  • Υπολογιστική βιολογία
  • Υπολογιστική γλωσσολογία
  • Υπολογιστική νευροεπιστήμη

Η επιστήμη υπολογιστών, όρος καταγόμενος από την αγγλική γλώσσα («computer science»), με την ευρεία έννοια περίπου ταυτίζεται με την πληροφορική ως επιστημονικό πεδίο (αγγλ.: «informatics»)^[15], ωστόσο χρησιμοποιείται εναλλακτικά και με μια πιο στενή έννοια η οποία εννοεί αποκλειστικά τη θεωρητική πληροφορική και τα συναφή μαθηματικά της θεμέλια. Σε αυτή την περίπτωση μόνο, συνήθως θεωρείται πως η επιστήμη υπολογιστών συμπεριλαμβάνει τη μηχανική λογισμικού, τα υπολογιστικά συστήματα και τη μηχανική υπολογιστών, ενώ η επιστήμη υπολογιστών όχι. Ο Έντσγκερ Ντάικστρα (Edsger Dijkstra), χρησιμοποιώντας τη στενή και περιορισμένη έννοια της επιστήμης υπολογιστών, έχει πει:

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

Ο φυσικός Ρίτσαρντ Φάινμαν (Richard Feynman) έχει πει:

Η επιστήμη υπολογιστών δεν είναι τόσο παλιά όσο η φυσική, υστερεί χρονικά μερικούς αιώνες. Ωστόσο, αυτό δεν σημαίνει ότι υπάρχουν λιγότερα στο πιάτο του επιστήμονα των υπολογιστών απ' ότι σε αυτό του φυσικού: μπορεί να είναι νεότερη αλλά είχε μια πολύ πιο έντονη γέννηση!

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

1. Θεωρητική πληροφορική
2. Λογισμικό
3. Μηχανική υπολογιστών
4. Υπολογιστικά συστήματα
5. Εφαρμογές υπολογιστών

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

Ιστορία των υπολογιστών

Η Άντα Λάβλεϊς έγραψε το πρώτο πρόγραμμα υπολογιστή κατά τον 19ο αιώνα για την Αναλυτική Μηχανή του Μπάμπατζ, πολύ πριν από την εμφάνιση ηλεκτρονικών υπολογιστών. Η γλώσσα προγραμματισμού Ada έχει ονομαστεί έτσι προς τιμήν της.

Η προϊστορία των υπολογιστών εντοπίζεται τόσο στη μαθηματική μελέτη των αλγορίθμων, όσο και σε ποικίλες απόπειρες κατασκευής υπολογιστικών μηχανών με στόχο την αυτοματοποίηση αριθμητικών υπολογισμών. Αποσπασματικές προσπάθειες ενταγμένες στα δύο αυτά εγχειρήματα μπορούν να ανιχνευθούν από την Αρχαιότητα μέχρι και τον 19ο αιώνα, πολύ πριν από την ανάπτυξη των σύγχρονων ψηφιακών υπολογιστών. Σημαντικοί σταθμοί στην εν λόγω ιστορική διαδρομή υπήρξαν η κατασκευή του μηχανισμού των Αντικυθήρων, του πρώτου μηχανικού υπολογιστή (περιορισμένων βεβαίως δυνατοτήτων) ο οποίος κατασκευάστηκε ποτέ και διασώζεται μέχρι σήμερα, η διατύπωση αλγορίθμων σε φυσική γλώσσα από τον Ευκλείδη και τον Ερατοσθένη, η πρώιμη μελέτη της έννοιας του αλγορίθμου από τον Πέρση μαθηματικό του Μεσαίωνα Αλ Χουαρίζμι στο πλαίσιο της πρώτης πλήρους πραγματείας περί άλγεβρας, η κατασκευή της πρώτης μηχανικής αριθμομηχανής από τον Μπλεζ Πασκάλ το 1645, καθώς και ο μηχανικός υπολογιστής του Τσαρλς Μπάμπατζ στα μέσα του 19ου αιώνα, πρόγονος των καθολικών υπολογιστών γενικού σκοπού, ο οποίος όμως απέτυχε να επηρεάσει σημαντικά την τεχνολογία της εποχής του. Στη συνέχεια, προτού γίνει ξεχωριστή επιστήμη, η επιστήμη υπολογιστών εμφανίστηκε σαν πεδίο των διακριτών μαθηματικών κατά τη δεκαετία του 1930, μετά την αυστηρή μαθηματική τυποποίηση των εννοιών του αλγορίθμου και του υπολογισμού από τους μαθηματικούς Άλαν Τιούρινγκ και Αλόνζο Τσερτς.

Ο ENIAC (1946) υπήρξε ο πρώτος επαναπρογραμματιζόμενος ηλεκτρονικός υπολογιστής γενικού σκοπού, ικανοποιώντας τα κριτήρια του Τιούρινγκ περί καθολικής επιλυσιμότητας (ήταν δηλαδή θεωρητικά σε θέση να εκτελέσει κάθε δυνατό αλγόριθμο), δίνοντας μια αρχική ώθηση στην επιστημονική ανεξαρτητοποίηση της επιστήμης υπολογιστών. Οι υπολογιστές που είχαν προηγηθεί του ENIAC ήταν είτε μηχανικές κατασκευές ειδικού σκοπού (π.χ. ο μηχανισμός των Αντικυθήρων), είτε ηλεκτρομηχανολογικές κατασκευές (π.χ. Ζ3), είτε ηλεκτρονικές συσκευές που δεν είχαν όμως καθολικές δυνατότητες υπολογισιμότητας (π.χ. Colossus). Από τα τέλη της δεκαετίας του 1950, οπότε καθιερώθηκε η αρχιτεκτονική φον Νόιμαν των σύγχρονων ψηφιακών υπολογιστών, η αυτονομημένη πλέον επιστήμη υπολογιστών άρχισε να αναπτύσσεται σε μεγάλο βαθμό ανεξάρτητα από τις ίδιες τις μηχανές, με την πλήρη ακαδημαϊκή αναγνώρισή της ως ξεχωριστής επιστήμης, χαρακτηριζόμενης από τη δική της παράδοση και ιδιότητες, να συμβαίνει σταδιακά κατά τη δεκαετία του 1960. Η πολύ μεγάλη επιρροή της, ακολούθως, στην ανάδυση των ρηξικέλευθων τεχνολογιών πληροφοριών και επικοινωνίας (ΤΠΕ), έχει οδηγήσει διεθνώς μετά το 1970 σε κοινωνικές εξελίξεις που πολλοί εκλαμβάνουν ως «επανάσταση της πληροφορίας», «παγκόσμιο χωριό» και «κοινωνία της γνώσης». Ταυτόχρονα, η επιστήμη υπολογιστών αποτέλεσε το επιστημονικό υπόβαθρο επί του οποίου στηρίχθηκε η σύγχρονη βιομηχανία ανάπτυξης και συντήρησης λογισμικού, κυρίως μετά την καθιέρωση των προσωπικών υπολογιστών, φτάνοντας τελικά να αποτελεί έναν ευμεγέθη τομέα της οικονομίας.

Σήμερα η επιστήμη υπολογιστών ασχολείται επιστημονικά με ένα ευρύ φάσμα θεμάτων, όπως η ανάπτυξη αλγορίθμων για την αποτελεσματική επίλυση προβλημάτων, η κατασκευή και βελτίωση συστημάτων λογισμικού και υλικού υψηλής απόδοσης, η ταχεία και ασφαλής διακίνηση πληροφοριών μέσω τηλεπικοινωνιακών δικτύων, η δημιουργία συστημάτων διαχείρισης δεδομένων, η διερεύνηση του τρόπου με τον οποίο ο άνθρωπος διατυπώνει συλλογισμούς, η προσομοίωση της λειτουργίας του ανθρώπινου εγκεφάλου κλπ. Έτσι, η επιστήμη υπολογιστών συνδέεται άμεσα με όλες τις θετικές επιστήμες, αλλά και με τη φιλοσοφία, την ψυχολογία, τη γλωσσολογία, τη νομική, την ιατρική, τα οικονομικά και τη διοίκηση επιχειρήσεων. Προς τιμήν του Άλαν Τιούρινγκ, κάθε έτος από το 1966 κι έπειτα ο διεθνής «Σύλλογος Μηχανημάτων Υπολογισμού» (Association for Computing Machinery, ACM) απονέμει το Βραβείο Τιούρινγκ σε έναν επιστήμονα του χώρου με αναγνωρισμένη σημαντική συνεισφορά. Το Βραβείο Τιούρινγκ έχει αποκληθεί «Βραβείο Νόμπελ της επιστήμης υπολογιστών».

Κλάδοι

Η επιστήμη υπολογιστών συνίσταται σε πέντε βασικούς κλάδους. Τα επιμέρους πεδία τους παρατίθενται παρακάτω, από κοινού με τα θεμελιώδη πεδία των μαθηματικών στα οποία η επιστήμη υπολογιστών εν πολλοίς στηρίζεται (ενότητα «Μαθηματικά θεμέλια»).

Μαθηματικά θεμέλια Αριθμητική ανάλυση Άλγεβρα Μπουλ Διακριτά μαθηματικά Θεωρία γράφων Μαθηματική λογική Θεωρία πεδίων Πιθανότητες Στατιστική Επεξεργασία σήματος Θεωρία πληροφοριών

Θεωρητική πληροφορική Θεωρία τυπικών γλωσσών Θεωρία υπολογισμού Ανάλυση αλγορίθμων Θεωρία πολυπλοκότητας Τυπική επαλήθευση Δομές δεδομένων Θεωρία γλωσσών προγραμματισμού Κατανεμημένος υπολογισμός Υπολογιστική γεωμετρία Κρυπτολογία Θεωρία ουρών αναμονής Κβαντικός υπολογισμός

Μηχανική υπολογιστών Ολοκληρωμένα κυκλώματα VLSI Λογική σχεδίαση Αρχιτεκτονική υπολογιστών Μικροπρογραμματισμός Μικροεπεξεργαστές Ψηφιακές επικοινωνίες

Υπολογιστικά συστήματα Δίκτυα υπολογιστών Προγραμματισμός δικτύων Κατανεμημένα συστήματα Παράλληλα συστήματα Παράλληλος προγραμματισμός Λειτουργικά συστήματα Ενσωματωμένα συστήματα Συστήματα πραγματικού χρόνου Κινητά συστήματα Ασφάλεια υπολογιστικών συστημάτων

Λογισμικό Μηχανική λογισμικού Προγραμματισμός υπολογιστών Αντικειμενοστρεφής σχεδίαση Σχεδιαστικά πρότυπα Ανάλυση απαιτήσεων Ποιότητα λογισμικού Μεταγλωττιστές Βελτιστοποίηση προγραμμάτων Βάσεις δεδομένων Ανάκτηση πληροφορίας

Εφαρμογές υπολογιστών Γραφικά υπολογιστών CAD και CAM Αλληλεπίδραση ανθρώπου-υπολογιστή Τεχνητή νοημοσύνη Συστήματα γνώσης Επίλυση προβλημάτων Μηχανική μάθηση Εξόρυξη δεδομένων Αναγνώριση προτύπων Μηχανική όραση Ρομποτική Επεξεργασία φυσικής γλώσσας Βιοπληροφορική Επεξεργασία ήχου Επεξεργασία εικόνας και βίντεο Συμπίεση δεδομένων

Φιλοσοφία

Η φιλοσοφία της επιστήμης υπολογιστών, δηλαδή η ορθολογική διερεύνηση των θεμελιωδών υποθέσεων και στόχων της επιστήμης υπολογιστών, σχηματίστηκε σταδιακά ως τομέας ακαδημαϊκής μελέτης κατά το δεύτερο μισό του 20^ου αιώνα, παράλληλα με την ίδια την επιστήμη υπολογιστών. Ωστόσο, μόνο μετά την αλλαγή της χιλιετίας το 2000 άρχισε να αποτελεί διακριτό γνωστικό αντικείμενο, στα πρότυπα άλλων κλάδων της φιλοσοφίας της επιστήμης. Εξαίρεση αποτελεί το επιμέρους πεδίο της ονόματι φιλοσοφία της τεχνητής νοημοσύνης, το οποίο είχε αναδυθεί ταυτόχρονα με την ίδια την τεχνητή νοημοσύνη ήδη από τη δεκαετία του '50, σε επικάλυψη με την προϋπάρχουσα φιλοσοφία της νόησης και παράλληλα με τον διακλαδικό τομέα της γνωσιακής επιστήμης (συμβατικά αποδεκτό έτος εμφάνισης: 1956). Παρακάτω, επομένως, εξετάζεται συνοπτικά η φιλοσοφία της επιστήμης υπολογιστών χωρίς να περιλαμβάνεται στην εν λόγω περιγραφή η φιλοσοφία της τεχνητής νοημοσύνης, λόγω της διαφορετικής ιστορικής διαδρομής, αν και στην πραγματικότητα πρόκειται για το πιο πλούσιο και θεωρητικά μελετημένο επιμέρους πεδίο της.

Η ταυτότητα των προγραμμάτων

Η οντολογική όψη της διάκρισης μεταξύ υλικού και λογισμικού, καθώς και ο εγγενώς διττός χαρακτήρας των προγραμμάτων, συνιστούν ένα βασικό αντικείμενο διερεύνησης στον τομέα. Υλικό και λογισμικό είναι λογικά ισοδύναμα: οτιδήποτε μπορεί να γραφεί ως λογισμικό (σύνολο εντολών προς το υλικό) μπορεί να υλοποιηθεί εναλλακτικά απευθείας σε υλικό, και αντιστρόφως. Ακόμα, ένα πρόγραμμα μπορεί να ιδωθεί είτε ως επεξεργάσιμο κείμενο (πηγαίος κώδικας) είτε ως αφηρημένη, μηχανική διαδικασία υπολογισμού (υλοποίηση αλγορίθμου εκτελούμενη στον υλικό επεξεργαστή). Έτσι, ένα σημαντικό μέρος του τομέα αφιερώνεται στη θεωρητική εξέταση των οντολογικών ερωτημάτων που προκύπτουν από αυτές τις ισοδυναμίες και διττότητες. Μία δυνατότητα επίλυσης του δυϊσμού των προγραμμάτων είναι η αναγόρευση της «διαδικαστικής» όψης ενός προγράμματος σε υλοποίηση της «κειμενικής» του όψης, όμως τότε το ερώτημα απλώς μετατοπίζεται στο ποια είναι η οντολογική φύση μίας σχέσης υλοποίησης και ποια είναι η διαφορά μεταξύ της υλοποίησης πηγαίου κώδικα σε εκτελέσιμο κώδικα (από έναν μεταγλωττιστή) και της υλοποίησης λογισμικού σε υλικό (από έναν μηχανικό υπολογιστών). Μία ενδεχόμενη απάντηση είναι η θέαση του λογισμικού ως αφηρημένης οντότητας, η οποία εκφράζει μία συγκεκριμένη αλληλουχία διατάξεων του υλικού (διαδικαστική όψη / μέσον εκτέλεσης) και ταυτόχρονα περιγράφεται συνοπτικά από μία ισοδύναμη αλληλουχία γλωσσικών συμβόλων (κειμενική όψη / μέσον περιγραφής). Η υλοποίηση, τότε, δεν είναι παρά η απεικόνιση ενός μέσου περιγραφής στο κατάλληλο μέσον εκτέλεσης. Ο φιλόσοφος Ντέιβιντ Τσάλμερς έχει αναπτύξει μία τέτοια διατύπωση της έννοιας της υλοποίησης ως ισομορφισμού. Όμως, σε αυτή την περίπτωση, εγείρεται το ερώτημα του πότε δύο προγράμματα θεωρούνται ταυτόσημα: όταν η κειμενική τους όψη ταυτίζεται ή όταν συμπίπτουν λειτουργικά στη διαδικαστική τους όψη; Πρόκειται για ένα σύνθετο ζήτημα διότι δύο διαφορετικοί πηγαίοι κώδικες μπορούν να μεταγλωττίζονται στην ίδια γλώσσα μηχανής, ή εναλλακτικά να παράγουν στη διαδικαστική τους όψη αλγοριθμικά τελείως ισοδύναμες συμπεριφορές.

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

Μία συγγενής διένεξη αφορά τη διάκριση μεταξύ τυπικών προδιαγραφών και προγραμμάτων. Συμβατικά, θεωρείται πως οι προδιαγραφές ορίζουν μόνο ποιες είναι οι δυνατές είσοδοι και οι αντίστοιχες κατάλληλες έξοδοι ενός προγράμματος, ενώ το τελευταίο περιέχει ένα πλήρες σύνολο βήμα-προς-βήμα εντολών προς τον επεξεργαστή. Ο ορισμός αυτός έχει πράγματι ισχύ για τη γλώσσα μηχανής (τη διαδικαστική όψη των προγραμμάτων) και για τις προστακτικές γλώσσες προγραμματισμού, καταρρέει όμως τελείως όταν ως «πρόγραμμα» θεωρούμε τον πηγαίο κώδικα πιο σύγχρονων δηλωτικών γλωσσών προγραμματισμού. Πράγματι, υπάρχει μία διαχρονική τάση στην ιστορία του προγραμματισμού ώστε η σύνταξη κώδικα να μοιάζει όλο και περισσότερο με σύνταξη τυπικών προδιαγραφών. Μία θεωρητική λύση στο θέμα της διάκρισης μεταξύ των δύο, δίνει η θέση πως οι γλώσσες προγραμματισμού συνοδεύονται κατ' αρχήν από μία υλοποίηση (δηλαδή μπορεί να γραφεί ένας μεταγλωττιστής για αυτές), ενώ οι γλώσσες προδιαγραφών όχι, διότι είναι εφικτό με αυτές να εκφραστούν έννοιες μη επιλύσιμες κατά Τιούρινγκ (δηλαδή μη αλγοριθμίσιμες). Το ζήτημα ωστόσο παραμένει ανοικτό στη φιλοσοφία της επιστήμης υπολογιστών, αφού μοιάζει τουλάχιστον ιδιόρρυθμο να ορίζονται οι γλώσσες προδιαγραφών με γνώμονα το ότι μπορούν να περιγράψουν μη επιλύσιμα υπολογιστικά προβλήματα.

Η σημασιολογία των γλωσσών προγραμματισμού

Ένα στιγμιότυπο πηγαίου κώδικα σε γλώσσα προγραμματισμού Java.

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

Ένα κύριο ζήτημα αφορά το αν και ποια σημασιολογία τοποθετείται εγγύς της πραγματικής υλοποίησης (της τελικής, διαδικαστικής όψης του προγράμματος) και ποια είναι περισσότερο ένα αφηρημένο μαθηματικό κατασκεύασμα. Από μία σκοπιά, όλες οι τυπικές σημασιολογίες δεν είναι παρά αφηρημένα μαθηματικά κατασκευάσματα, αλλά ακόμα και η δηλωτική σημασιολογία, φαινομενικά πολύ απομακρυσμένη από το υλικό μηχανικό υπόστρωμα, είναι σε θέση να εκφράσει αρκετές λεπτομέρειες της πραγματικής υλοποίησης - ως αποτέλεσμα δεν υπάρχει ευρεία συναίνεση σε αυτό το θέμα. Μία εναλλακτική προσέγγιση στο ίδιο ζήτημα αξιοποιεί την έννοια της σύνθεσης: μία τυπική σημασιολογία καλείται συνθετική αν η σημασιολογική τιμή μίας σύνθετης έκφρασης σ' αυτήν αποτελεί συνάρτηση των σημασιολογικών τιμών των συστατικών της μερών. Ωστόσο, αν και η δηλωτική σημασιολογία είναι σχεδιασμένη ως συνθετική (γεγονός που εξηγεί τη μεγάλη της εκφραστική δύναμη), μία λειτουργική σημασιολογία επίσης μπορεί να φέρει τα χαρακτηριστικά της σύνθεσης. Επομένως, ένας ευδιάκριτος θεμελιώδης εννοιολογικός διαχωρισμός μεταξύ λειτουργικών και δηλωτικών σημασιολογιών, έχει αποδειχθεί μέχρι στιγμής ανέφικτος.

Η καθιερωμένη αντίληψη θεωρεί πως η διαδικασία της υλοποίησης ενός προγράμματος, η μεταγλώττιση του πηγαίου κώδικα σε γλώσσα μηχανής, δεν είναι παρά μία απεικόνιση από το πεδίο της σύνταξης στο σημασιολογικό πεδίο, με βάση ένα σύνολο κανόνων. Η εν λόγω θέση όμως υπόρρητα εκλαμβάνει την υλική μηχανή (το λειτουργικό σύνολο επεξεργαστή, κύριας μνήμης κλπ.) ως τελικό φορέα της σημασιολογίας, και άρα του νοήματος του προγράμματος, καθώς αυτή εκτελεί το λογισμικό του μεταγλωττιστή: η μηχανή φέρει εις πέρας την απεικόνιση της κειμενικής σε διαδικαστική όψη κι έτσι νοηματοδοτεί τον κώδικα. Η προσέγγιση αυτή έχει δειχθεί ως ανεπαρκής: π.χ. σε περίπτωση ηλεκτρικής δυσλειτουργίας του επεξεργαστή ενώ εκτελείται η μεταγλώττιση, ο παραχθείς κώδικας έχει μεγάλη πιθανότητα να είναι εσφαλμένος. Σύμφωνα με ποια κριτήρια όμως μπορεί να κριθεί εσφαλμένος αν η υλοποίηση έχει γίνει από την ίδια τη μηχανή που «έσφαλλε»; Άρα, απαιτείται μία πηγή νοημοτοδότησης του πηγαίου κώδικα εξωτερική της υλικής υπολογιστικής μηχανής η οποία φέρει εις πέρας τη μεταγλώττιση.

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

Αποδείξεις και προγράμματα

Θεωρώντας ένα πρόγραμμα υπολογιστή ως έναν μεγάλο υπολογισμό, οι τυπικές προδιαγραφές καθορίζουν τις ζητούμενες κατάλληλες εξόδους του για όλες τις αντίστοιχες δυνατές εισόδους του. Η κατηγορηματική λογική παρέχει μηχανισμούς θέσπισης τυπικών προδιαγραφών για ένα πρόγραμμα, όπως π.χ. η λογική Hoare του Τόνυ Χόαρ, με τους οποίους είναι εφικτό υπό προϋποθέσεις να ελεγχθεί η ορθότητά του: αν πράγματι για κάθε δυνατή είσοδο παράγεται η κατάλληλη έξοδος. Τέτοιες αποδείξεις υλοποιούνται με αφετηρία τις προδιαγραφές του προγράμματος και με βάση τα μαθηματικά εργαλεία της κατηγορηματικής λογικής, αλλά είναι αμφισβητήσιμο από φιλοσοφική σκοπιά το κατά πόσο μοιάζουν με τις συνηθισμένες αποδείξεις των μαθηματικών. Έχει υποστηριχθεί ότι τους λείπει η κομψότητα, η λιτότητα (συνήθως είναι μεγαλύτερες σε έκταση από τον πηγαίο κώδικα του προγράμματος) και η διανοητική γοητεία, ενώ δεν είναι εύκολα επαληθεύσιμες από ανθρώπους. Το επιχείρημα αυτό συνδέεται με παρόμοιες επιστημολογικές διενέξεις στη φιλοσοφία των μαθηματικών σχετικά με τη φύση και την πηγή της αξίας των μαθηματικών αποδείξεων, διενέξεις οι οποίες ενισχύθηκαν κατά τις τελευταίες δεκαετίες εξαιτίας της χρήσης λογισμικού υπολογιστών για απόδειξη θεωρημάτων.

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

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

Οντολογία και γλώσσες προγραμματισμού

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

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

Οι περισσότερες γλώσσες προγραμματισμού εμπεριέχουν την έννοια του τύπου δεδομένων, ο οποίος ανάγεται στη θεωρία τύπων του Μπέρτραντ Ράσελ. Η θεωρία τύπων είναι μία κατηγορία τυπικών συστημάτων τα οποία μπορούν να λειτουργήσουν ως θεμέλια όλων των μαθηματικών, αντί για τη θεωρία συνόλων, ωστόσο οι σύγχρονες γλώσσες προγραμματισμού έχουν πολύ πιο πλούσια συστήματα τύπων συγκριτικά με τη θεωρία του Ράσελ. Τα συστήματα αυτά επιτρέπουν στους μεταγλωττιστές τους να επεκτείνουν τις τυπικές γραμματικές τους με λειτουργίες ελέγχου τύπων, ώστε να διασφαλίζεται περισσότερο η ορθότητα του πηγαίου κώδικα διά της συντακτικής ανάλυσης. Ένα προκύπτον ερώτημα είναι το κατά πόσον το σύστημα τύπων μίας γλώσσας καθορίζει πλήρως την οντολογική της διάσταση, δηλαδή το ποιες κατηγορίες διακριτών οντοτήτων είναι εφικτό να περιγραφούν σε αυτήν (π.χ. αριθμοί, πίνακες κλπ.). Μία ενδεχόμενη λύση είναι η καταφυγή σε θεωρίες περί της φυσικής γλώσσας, σύμφωνα με τις οποίες η οντολογία της τελευταίας ορίζεται από τη σημασιολογία της. Όμως μία σημασιολογική ανάλυση της οντολογίας, αν και θα λάβανε υπόψη της αναγκαστικά το σύστημα τύπων, μπορεί εύκολα να το υπερβεί και να περιγράψει πρόσθετες δομές όχι άμεσα αντιστοιχιζόμενες σε τύπους δεδομένων. Έτσι, εναλλακτικές σημασιολογίες για την ίδια γλώσσα δίνουν ως αποτέλεσμα διαφορετικές οντολογίες, παρόλο που το σύστημα τύπων είναι κοινό, αναλόγως με το επίπεδο αφαίρεσης στο οποίο τοποθετείται η κάθε σημασιολογία.

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

Επιλυσιμότητα

Καλλιτεχνική αναπαράσταση μίας Μηχανής Τιούρινγκ.

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

Σύμφωνα με τη θέση Τσερς-Τιούρινγκ - διατυπωμένη σταδιακά, σε ολοένα και πιο επεξεργασμένες εκδοχές, από το 1936 ως το 1952 - η Μηχανή Τιούρινγκ που τερματίζει για όλες τις εισόδους της συνιστά την αυστηρή τυποποίηση της διαισθητικής έννοιας του αλγορίθμου. Κανένας υπολογισμός δεν μπορεί να κωδικοποιηθεί αλγοριθμικά (ώστε π.χ. να εκτελεστεί από έναν μηχανικό ή ηλεκτρονικό υπολογιστή) αν δεν μπορεί θεωρητικά να σχεδιαστεί Μηχανή Τιούρινγκ (οσοδήποτε πολύπλοκη) η οποία να τον φέρει εις πέρας. Αυτό το γεγονός προϋποθέτει ότι υπάρχουν μη επιλύσιμα (μη αλγοριθμίσιμα) προβλήματα, δίνοντας έτσι οριστικά (αρνητική) απάντηση σε ένα από τα βασικά ερωτήματα του προγράμματος του Χίλμπερτ. Όμως η θέση Τσερτς-Τιούρινγκ είναι μία εικασία με διαισθητικό χαρακτήρα και ένας ορισμός, όχι θεώρημα το οποίο αποδεικνύεται τυπικά. Ωστόσο είναι ευρύτατα αποδεκτή από την επιστημονική κοινότητα.

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

Η επικρατούσα υπόθεση στην επιστήμη υπολογιστών είναι πως πράγματι ισχύει αυτή η ισοδυναμία, επομένως κάθε φυσικός υπολογισμός εκτελούμενος από μία μηχανή περιορίζεται πάντα από τις θεωρητικές υπολογιστικές δυνατότητες των Μηχανών Τιούρινγκ. Πράγματι, κάθε πρόγραμμα γραμμένο σε μία από τις υπάρχουσες γλώσσες προγραμματισμού είναι επιλύσιμο κατά Τιούρινγκ, αλλά και, αντιστρόφως, κάθε υπάρχουσα γλώσσα προγραμματισμού γενικού σκοπού είναι πλήρης κατά Τιούρινγκ, εμπεριέχει δηλαδή όλες τις απαραίτητες δομές για να προσομοιώσει τη λειτουργία μίας Καθολικής Μηχανής Τιούρινγκ. Ωστόσο, με την εμφάνιση του κβαντικού υπολογισμού και με τη θεωρητική μελέτη υπολογισμών άπειρης ακρίβειας, ή μηχανών με δυνατότητα εκτέλεσης άπειρων πράξεων σε πεπερασμένο χρόνο (προϋποθέσεις πρακτικά αδύνατες προς το παρόν), έχει καταδειχθεί η δυνατότητα λειτουργίας υλικών μηχανών με υπολογιστική ισχύ μεγαλύτερη των Μηχανών Τιούρινγκ. Παρ' όλ' αυτά, ορισμένοι υποστηρίζουν ότι τέτοιες προϋποθέσεις είναι όχι μόνο πρακτικά αδύνατες, αλλά και ότι στερούνται εννοιολογικού νοήματος.

Σημαντικοί επιστήμονες

Πρόδρομοι

Πρόσωπο	Επίτευγμα
Ραμόν Λουλ	(Ramon Llull): Για τις πολλαπλές μηχανές συμβολικής αναπαράστασης, την εργασία του Ars Combinatoria, και τις πρωτοποριακές του ιδέες της συμβολικής αναπαράστασης και χειρισμού των συμβόλων αυτών για την παραγωγή γνώσης. Επηρέασε σημαντικά τον Λάιμπνιτς.
Γκότφριντ Βίλχελμ Λάιμπνιτς	(Gottfried Wilhelm Leibniz): Η μεγάλη συνεισφορά του στη συμβολική λογική, κυρίως με την εργασία του Calculus Ratiocinator, επηρέασε σημαντικά τον Γκότλομπ Φρέγκε, του οποίου η ανάπτυξη του κατηγορηματικού λογισμού πρώτης τάξης ήταν κρίσιμη για τη θεωρητική θεμελίωση της επιστήμης υπολογιστών.
Τσαρλς Μπάμπατζ	(Charles Babbage): Σχεδίασε και κατασκεύασε το πρωτότυπο ενός μηχανικού υπολογιστή, ενώ στη συνέχεια σχεδίασε την, ακόμα πιο ισχυρή, Αναλυτική Μηχανή.
Άντα Λάβλεϊς	(Ada Lovelace): Κόρη του Λόρδου Βύρωνα και βοηθός του Τσαρλς Μπάμπατζ. Μελέτησε επιστημονικά την έννοια του υπολογισμού και με την εργασία της Προσχέδιο μιας αναλυτικής μηχανής ανέλυσε το έργο του Μπάμπατζ. Η γλώσσα προγραμματισμού Ada ονομάστηκε έτσι προς τιμήν της.
Γκότλομπ Φρέγκε	(Friedrich Ludwig Gottlob Frege): Η ανάπτυξη του κατηγορηματικού λογισμού πρώτης τάξης από τον Φρέγκε αποτέλεσε σημαντικό προαπαιτούμενο για την ανάπτυξη της θεωρίας υπολογισμού.
Κούρτ Γκέντελ	(Kurt Gödel): Ιστορική υπήρξε η απόδειξή του (1931) ότι η αριθμητική βασισμένη σε αξιώματα του Πεάνο δεν μπορεί να είναι και λογικά συνεπής και πλήρης στον κατηγορηματικό λογισμό πρώτης τάξης. Ο Βιττγκενστάιν στην ύστερή του περίοδο ανέπτυξε ισχυρή κριτική στο έργο του.
Αλόνζο Τσερτς	(Alonso Church): Συνεισέφερε στη θεμελίωση της θεωρίας υπολογισμού, ιδιαίτερα με την ανάπτυξη του λογισμού-λ και τη διερεύνηση μέσω αυτού του προβλήματος της μη-αποφασισιμότητας.
Στίβεν Κολ Κλέινι	(Stephen Cole Kleene): Πρωτοποριακή δουλειά με τον Αλόνζο Τσερτς στον λογισμό-λ, με τον οποία τέθηκαν τα θεμέλια της θεωρίας υπολογισμού.
Άλαν Τιούρινγκ	(Alan Turing): Θεμελιώδεις υπήρξαν οι συνεισφορές του στη θεωρία υπολογισμού, κι επομένως στην αυτονόμηση της επιστήμης υπολογιστών από τα μαθηματικά, στην αυστηρή διατύπωση των εννοιών του υπολογισμού και του αλγορίθμου μέσω της Μηχανής Τιούρινγκ, καθώς και στον σχεδιασμό του Pilot ACE. Ο Τιούρινγκ θεωρείται ο «πατέρας της επιστήμης υπολογιστών και της τεχνητής νοημοσύνης».
Μόρις Γουάιλκς	(Maurice Wilkes): Κατασκεύασε τον πρώτο υπολογιστή με αποθηκευμένο πρόγραμμα, ενώ του αποδίδονται και πολλές ιδέες δομών υψηλού επιπέδου γλωσσών προγραμματισμού.
Κόνραντ Τσούζε	(Konrad Zuse): Κατασκεύασε τον ψηφιακό υπολογιστή Z3, τον πρώτο που λειτούργησε με το δυαδικό σύστημα αρίθμησης, για τον οποίο επινόησε επίσης και τη γλώσσα προγραμματισμού υψηλού επιπέδου, Plankalkül.
Τζον Βίνσεντ Ατανάσοφ	(John Vincent Atanasoff): Κατασκεύασε τον πρώτο ηλεκτρονικό ψηφιακό υπολογιστή, τον ABC. Αντίθετα με τον ENIAC, ο οποίος θεωρείται ο πρώτος πλήρης ηλεκτρονικός υπολογιστής που σχεδιάστηκε να είναι Τιούρινγκ-πλήρης, ο ABC δεν ήταν προγραμματίσιμος.
Τζον Μάκλεϊ και Τζέι Πρέσπερ Έκερτ	(John Mauchly και J. Presper Eckert): Σχεδίασαν και κατασκεύασαν τον ENIAC, τον πρώτο ηλεκτρονικό Τιούρινγκ-πλήρη υπολογιστή και τον UNIVAC I, τον πρώτο διαθέσιμο εμπορικά υπολογιστή στις Η.Π.Α.. Η εργασία τους στον ENIAC στο Πανεπιστήμιο της Πενσυλβάνια επηρέασε σημαντικά τον Τζον φον Νόιμαν στο Ίδρυμα Προηγμένων Ερευνών, καθώς η εργασία τους στην αρχιτεκτονική υπολογιστών ήταν πρωτοποριακή.
Τζον φον Νόιμαν	(John von Neumann): Επινόησε την αρχιτεκτονική φον Νόιμαν, πάνω στην οποία βασίζονται οι σύγχρονοι υπολογιστές. Ακόμα, εφηύρε τα κυτταρικά αυτόματα.
Κλοντ Σάνον	(Claude E. Shannon): Υπήρξε ο θεμελιωτής της θεωρίας πληροφορίας και το έργο του βοήθησε στην έναρξη της σύγχρονης εποχή των τηλεπικοινωνιών. Επίσης επηρέασε την πρώιμη κυβερνητική.

Επιστήμονες υπολογιστών

Πρόσωπο	Επίτευγμα
Άλαν Πέρλις	(Alan Jay Perlis): Επινόησε προηγμένες μεθόδους προγραμματισμού υπολογιστών και κατασκευής μεταγλωττιστών. Υπήρξε ο πρώτος επιστήμονας που τιμήθηκε με Βραβείο Τιούρινγκ (το 1966).
Γκρέις Μάρει Χόπερ	(Grace Murray Hopper): Η Χόπερ έκανε πρωτοποριακή δουλειά στην υποστήριξη της αναγκαιότητας των γλωσσών προγραμματισμού υψηλού επιπέδου, που αποκάλεσε αυτόματο προγραμματισμό. Έγραψε επίσης τον μεταγλωττιστή Α-0 που επηρέασε την COBOL (Commercial Business Oriented Language).
Ρίτσαρντ Χάμινγκ	(Richard Hamming): Συνεισέφερε στην αριθμητική ανάλυση και στην ανάπτυξη κωδίκων ανίχνευσης και διόρθωσης σφαλμάτων (απόσταση Hamming).
Τζέιμς Γουίλκινσον	(James Wilkinson): Συνεισέφερε σημαντικά, με αποτελεσματικούς αλγορίθμους, στην αριθμητική ανάλυση και στην εφαρμοσμένη γραμμική άλγεβρα.
Τζον Μπάκους	(John Backus): Επινόησε τη FORTRAN (Formula Translation), την πρώτη υψηλού επιπέδου γλώσσα προγραμματισμού, καθώς και τη μορφή Μπάκους-Νάουρ, ένα μετασυντακτικό για γραμματικές χωρίς συμφραζόμενα, με το οποίο περιέγραψε τη σύνταξή της.
Ντόναλντ Κνουθ	(Donald Knuth): Για την πολύτομη σειρά βιβλίων Η τέχνη του προγραμματισμού υπολογιστών, τη θεωρητική συνεισφορά του στην ανάλυση αλγορίθμων και για το λογισμικό ψηφιακής τυπογραφίας TeX.
Τζον Μακάρθι	(John McCarthy): Επινόησε τη LISP (List Programming), μια συναρτησιακή γλώσσα προγραμματισμού, και συνεισέφερε τα μέγιστα στη διαμόρφωση και εξέλιξη της πρώιμης τεχνητής νοημοσύνης.
Μάρβιν Μίνσκυ	(Marvin Minsky): Υπήρξε πρωτοπόρος και επηρεαστικός ερευνητής και θεωρητικός της τεχνητής νοημοσύνης.
Ρόμπερτ Φλόιντ	(Robert Floyd): Συνεισέφερε στην εξέλιξη της τυπικής επαλήθευσης, της σχεδίασης μεταγλωττιστών και στη θεωρία γράφων.
Άλεν Νιούελ και Χέρμπερτ Σάιμον	(Allen Newell και Herbert Simon): Η από κοινού συμβολή τους στη διαμόρφωση και εξέλιξη της τεχνητής νοημοσύνης και της γνωσιακής επιστήμης, υπήρξε ανυπολόγιστη.
Έντσγκερ Ντάικστρα	(Edsger Dijkstra): Σημαντική είναι η προσφορά του στην ανάλυση αλγορίθμων, στην απαξίωση της προγραμματιστικής εντολής goto, στην επινόηση των σημαφόρων κλπ. Ονομάσθηκε «πατέρας του παράλληλου προγραμματισμού» και υπήρξε πρωτοπόρος στη μελέτη των λειτουργικών συστημάτων.
Μάικλ Ράμπιν και Ντέινα Σκοτ	(Michael Rabin και Dana Scott): Η από κοινού συνεισφορά τους στη θεωρία υπολογισμού, εφόσον υπήρξαν οι εισηγητές της έννοιας του μη πεπερασμένου αυτομάτου, είναι πολύ σημαντική.
Νίκλαους Βιρτ	(Niklaus Wirth): Επινόησε τη γλώσσα προγραμματισμού Pascal, την οποία ονόμασε έτσι προς τιμήν του Γάλλου πρωτοπόρου Μπλεζ Πασκάλ (Blaise Pascal).
Τζέιμς Κούλεϊ και Τζον Τάκει	(James W. Cooley και John W. Tukey): Επινόησαν έναν τρόπο για τον υπολογισμό του Ταχέως Μετασχηματισμού Φουριέ.
Τσαρλς Μπάκμαν	(Charles Backman): Από τη θέση του ερευνητή σε ιδιωτικές βιομηχανίες και όχι ως ακαδημαϊκός, συνεισέφερε σημαντικό θεωρητικό και πρακτικό έργο στην εξέλιξη των βάσεων δεδομένων.
Όλε-Γιόχαν Ντάαλ και Κρίστεν Νίγκαρντ	(Ole-Johan Dahl και Kristen Nygaard): Επινόησαν την πρώτη αντικειμενοστρεφή γλώσσα προγραμματισμού Simula (Simulation Language).
Κεν Τόμσον και Ντένις Ρίτσι	(Ken Thomson και Dennis Ritchie): Σχεδίασαν τη γλώσσα προγραμματισμού C και το λειτουργικό σύστημα Unix, με ανυπολόγιστες συνέπειες στους σύγχρονους υπολογιστές.
Τόνυ Χόαρ	(Tony Hoare): Ανέπτυξε την τυπική γλώσσα Επικοινωνούσες Ακολουθιακές Διεργασίες (CSP) και τον αλγόριθμο γρήγορης ταξινόμησης (Quicksort).
Άιβαν Σάδερλαντ	(Ivan Sutherland): Είχε σημαντική επιρροή και καινοτόμες συνεισφορές στον τομέα των γραφικών υπολογιστών.
Φρέντερικ Μπρουκς	(Frederick Brooks): Είχε σημαντική συνεισφορά, από τη δεκαετία του 1960, στην αρχιτεκτονική υπολογιστών, στα λειτουργικά συστήματα και στη μηχανική λογισμικού.
Κένεθ Άιβερσον	(Kenneth Iverson): Επινόησε τη γλώσσα προγραμματισμού APL (A Programming Language) και συνεισέφερε στον κλάδο της αλληλεπίδρασης ανθρώπου-υπολογιστή.
Έντγκαρ Κοντ	(Edgar Codd): Επινόησε το επικρατές σχεσιακό μοντέλο στις βάσεις δεδομένων.
Ντάγκλας Ένγκελμπαρτ	(Douglas Engelbart): Συνεισέφερε στον χώρο της αλληλεπίδρασης ανθρώπου-υπολογιστή, με πρωτοποριακές τεχνολογίες όπως το ποντίκι, τα γραφικά περιβάλλοντα χρήστη και το υπερκείμενο, το οποίο αξιοποιήθηκε κατόπιν στο Διαδίκτυο.
Τζάσεκ Καρπίνσκι	(Jacek Karpinski): Ανάπτυξε τον πρώτο διαφορικό αναλυτή που χρησιμοποιούσε τρανζίστορ, και επίσης ανέπτυξε έναν από τους πρώτους αλγόριθμους αναγνώρισης εικόνων και χαρακτήρων. Τέλος, είναι ο εφευρέτης του πρώτου μίνι-υπολογιστή, του K-202.
Στίβεν Κουκ	(Steven Cook): Συνεισέφερε σημαντικά στη σύγχρονη θεωρία υπολογισμού.
Ρίτσαρντ Καρπ	(Richard Karp): Είχε σημαντική συμβολή στη θεωρία της ανάλυσης αλγορίθμων και στη μελέτη προβλημάτων συνδυαστικής βελτιστοποίησης.
Τζον Χόπκροφτ και Ρίτσαρντ Τάρτζαν	(John Hopcroft και Richard Tarjan): Τα επιτεύγματά τους κινούνται στον χώρο της σχεδίασης και ανάλυσης αλγορίθμων και της μελέτης των δομών δεδομένων.
Χρίστος Παπαδημητρίου	Συνεισέφερε σημαντικά στη θεωρία υπολογισμού και, ευρύτερα, στη θεωρητική πληροφορική.
Ουίλιαμ Κάαν	(William Kahan): Επινόησε καινοτόμες μεθόδους στην αριθμητική ανάλυση και στην αριθμητική κινητής υποδιαστολής.
Τζον Κοκ	(John Cocke): Συνεισέφερε στη σχεδίαση και θεωρία των μεταγλωττιστών, καθώς και στην ανάπτυξη των αρχιτεκτονικών RISC στη μηχανική υπολογιστών.
Κρίστοφερ Λάνγκτον	(Christopher Langton): Με βάση τις δικές του κυρίως συνεισφορές ιδρύθηκε το επιστημονικό πεδίο της τεχνητής ζωής. Μελέτησε ακόμα διεξοδικά τα κυτταρικά αυτόματα.
Ρόντνεϊ Μπρουκς	(Rodney Brooks): Υπεύθυνος για την ανάδυση της συμπεριφορικής προσέγγισης στη ρομποτική και στην τεχνητή νοημοσύνη, μετατοπίζοντας το ενδιαφέρον από τον αφηρημένο υπολογισμό στην αλληλεπίδραση των ρομπότ με το περιβάλλον.
Τζουντέα Περλ	(Judea Pearl): Συνεισέφερε στη διάδοση και εξέλιξη υποσυμβολικών, πιθανοκρατικών προσεγγίσεων και αλγορίθμων στην τεχνητή νοημοσύνη, με αποτέλεσμα σημαντικές θεωρητικές και πρακτικές εξελίξεις στον τομέα μετά το 1990.
Μπιάρνε Στρούστρουπ	(Bjarne Stroustrup): Εφηύρε τη γλώσσα προγραμματισμού C++, εξοπλίζοντας τη C με ισχυρά χαρακτηριστικά αντικειμενοστρέφειας.
Ρίτσαρντ Στόλλμαν	(Richard Stallman): Είναι ο ιδρυτής του κινήματος ελεύθερου λογισμικού και επινόησε την άδεια χρήσης copyleft.
Άντριου Τάνενμπαουμ	(Andrew Tanenbaum): Επέβλεψε την κατασκευή του λειτουργικού συστήματος Minix (μία δωρεάν παραλλαγή του Unix για διδακτικούς σκοπούς, σχεδιασμένη για το IBM PC) και συνεισέφερε σημαντικά στην έρευνα επί των υπολογιστικών συστημάτων.
Λίνους Τόρβαλντς	(Linus Benedict Torvalds): Είναι ο αρχικός δημιουργός του πυρήνα του Linux, του δημοφιλέστερου λειτουργικού συστήματος ανοιχτού κώδικα, και έχει παραμείνει επικεφαλής της ανάπτυξής του.
Τιμ Μπέρνερς-Λι	(Tim Berners-Lee): Επινόησε τον Παγκόσμιο Ιστό ως υπηρεσία του Διαδικτύου.
Σεμπάστιαν Θραν	(Sebastian Thrun): Συνεισέφερε σημαντικά στην εξέλιξη και βελτίωση αλγορίθμων ρομποτικής, όπως π.χ. μεθόδων πιθανοκρατικής επίλυσης του θεμελιώδους προβλήματος SLAM, και στον σχεδιασμό αυτόνομων, ευφυών οχημάτων με ικανοποιητική απόδοση.
Κωνσταντίνος Δασκαλάκης	(Constantinos Daskalakis): Έλυσε τον γρίφο του Νας, που απασχολούσε την επιστήμη υπολογιστών για 60 χρόνια.

Εξωτερικοί σύνδεσμοι

• Πολυμέσα σχετικά με το θέμα Computer science στο Wikimedia Commons
• Λεξιλογικός ορισμός του επιστήμη υπολογιστών στο Βικιλεξικό