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

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

Η προϊστορία των υπολογιστών εντοπίζεται τόσο στη μαθηματική μελέτη των αλγορίθμων, όσο και σε ποικίλες απόπειρες κατασκευής υπολογιστικών μηχανών με στόχο την αυτοματοποίηση αριθμητικών υπολογισμών. Αποσπασματικές προσπάθειες ενταγμένες στα δύο αυτά εγχειρήματα μπορούν να ανιχνευθούν από την Αρχαιότητα μέχρι και τον 19ο αιώνα, πολύ πριν από την ανάπτυξη των σύγχρονων ψηφιακών υπολογιστών. Σημαντικοί σταθμοί στην εν λόγω ιστορική διαδρομή υπήρξαν η κατασκευή του μηχανισμού των Αντικυθήρων, του πρώτου μηχανικού υπολογιστή (περιορισμένων βεβαίως δυνατοτήτων) ο οποίος κατασκευάστηκε ποτέ και διασώζεται μέχρι σήμερα, η διατύπωση αλγορίθμων σε φυσική γλώσσα από τον Ευκλείδη και τον Ερατοσθένη, η πρώιμη μελέτη της έννοιας του αλγορίθμου από τον Πέρση μαθηματικό του Μεσαίωνα Αλ Χουαρίζμι στο πλαίσιο της πρώτης πλήρους πραγματείας περί άλγεβρας, η κατασκευή της πρώτης μηχανικής αριθμομηχανής από τον Μπλεζ Πασκάλ το 1645, καθώς και ο μηχανικός υπολογιστής του Τσαρλς Μπάμπατζ στα μέσα του 19ου αιώνα, πρόγονος των καθολικών υπολογιστών γενικού σκοπού, ο οποίος όμως απέτυχε να επηρεάσει σημαντικά την τεχνολογία της εποχής του. Στη συνέχεια, προτού γίνει ξεχωριστή επιστήμη, η επιστήμη υπολογιστών εμφανίστηκε σαν πεδίο των διακριτών μαθηματικών κατά τη δεκαετία του 1930, μετά την αυστηρή μαθηματική τυποποίηση των εννοιών του αλγορίθμου και του υπολογισμού από τους μαθηματικούς Άλαν Τιούρινγκ και Αλόνζο Τσερτς.
Ο ENIAC (1946) υπήρξε ο πρώτος επαναπρογραμματιζόμενος ηλεκτρονικός υπολογιστής γενικού σκοπού, ικανοποιώντας τα κριτήρια του Τιούρινγκ περί καθολικής επιλυσιμότητας (ήταν δηλαδή θεωρητικά σε θέση να εκτελέσει κάθε δυνατό αλγόριθμο), δίνοντας μια αρχική ώθηση στην επιστημονική ανεξαρτητοποίηση της επιστήμης υπολογιστών. Οι υπολογιστές που είχαν προηγηθεί του ENIAC ήταν είτε μηχανικές κατασκευές ειδικού σκοπού (π.χ. ο μηχανισμός των Αντικυθήρων), είτε ηλεκτρομηχανολογικές κατασκευές (π.χ. Ζ3), είτε ηλεκτρονικές συσκευές που δεν είχαν όμως καθολικές δυνατότητες υπολογισιμότητας (π.χ. Colossus). Από τα τέλη της δεκαετίας του 1950, οπότε καθιερώθηκε η αρχιτεκτονική φον Νόιμαν των σύγχρονων ψηφιακών υπολογιστών, η αυτονομημένη πλέον επιστήμη υπολογιστών άρχισε να αναπτύσσεται σε μεγάλο βαθμό ανεξάρτητα από τις ίδιες τις μηχανές, με την πλήρη ακαδημαϊκή αναγνώρισή της ως ξεχωριστής επιστήμης, χαρακτηριζόμενης από τη δική της παράδοση και ιδιότητες, να συμβαίνει σταδιακά κατά τη δεκαετία του 1960. Η πολύ μεγάλη επιρροή της, ακολούθως, στην ανάδυση των ρηξικέλευθων τεχνολογιών πληροφοριών και επικοινωνίας (ΤΠΕ), έχει οδηγήσει διεθνώς μετά το 1970 σε κοινωνικές εξελίξεις που πολλοί εκλαμβάνουν ως «επανάσταση της πληροφορίας», «παγκόσμιο χωριό» και «κοινωνία της γνώσης». Ταυτόχρονα, η επιστήμη υπολογιστών αποτέλεσε το επιστημονικό υπόβαθρο επί του οποίου στηρίχθηκε η σύγχρονη βιομηχανία ανάπτυξης και συντήρησης λογισμικού, κυρίως μετά την καθιέρωση των προσωπικών υπολογιστών, φτάνοντας τελικά να αποτελεί έναν ευμεγέθη τομέα της οικονομίας.
Σήμερα η επιστήμη υπολογιστών ασχολείται επιστημονικά με ένα ευρύ φάσμα θεμάτων, όπως η ανάπτυξη αλγορίθμων για την αποτελεσματική επίλυση προβλημάτων, η κατασκευή και βελτίωση συστημάτων λογισμικού και υλικού υψηλής απόδοσης, η ταχεία και ασφαλής διακίνηση πληροφοριών μέσω τηλεπικοινωνιακών δικτύων, η δημιουργία συστημάτων διαχείρισης δεδομένων, η διερεύνηση του τρόπου με τον οποίο ο άνθρωπος διατυπώνει συλλογισμούς, η προσομοίωση της λειτουργίας του ανθρώπινου εγκεφάλου κλπ. Έτσι, η επιστήμη υπολογιστών συνδέεται άμεσα με όλες τις θετικές επιστήμες, αλλά και με τη φιλοσοφία, την ψυχολογία, τη γλωσσολογία, τη νομική, την ιατρική, τα οικονομικά και τη διοίκηση επιχειρήσεων. Προς τιμήν του Άλαν Τιούρινγκ, κάθε έτος από το 1966 κι έπειτα ο διεθνής «Σύλλογος Μηχανημάτων Υπολογισμού» (Association for Computing Machinery, ACM) απονέμει το Βραβείο Τιούρινγκ σε έναν επιστήμονα του χώρου με αναγνωρισμένη σημαντική συνεισφορά. Το Βραβείο Τιούρινγκ έχει αποκληθεί «Βραβείο Νόμπελ της επιστήμης υπολογιστών».

Φιλοσοφία

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

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

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

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

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

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

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

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

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

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

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