Computing, modelling, and scientific practice: foundational analyses and limitations

Abstract

This dissertation examines aspects of the interplay between computing and scientific practice. The appropriate foundational framework for such an endeavour is rather real computability than the classical computability theory. This is so because physical sciences, engineering, and applied mathematics mostly employ functions defined in continuous domains. But, contraryto the case of computation over natural numbers, there is no universally accepted framework for real computation; rather, there are two incompatible approaches --computable analysis and BSS model--, both claiming to formalise algorithmic computation and to oer foundations for scientific computing. The dissertation consists of three parts. In the first part, we examine what notion of ‘algorithmic computation’ underlies each approach and how it is respectively formalised. It is argued that the very existence of the two rival frameworks indicates that ‘algorithm’ is not one unique concept in mathematics, but it is used in more than one way. We test this hypothesis for consistency with mathematical practice as well as with key foundational works that aim to define the term. As a result, new connections between certain subfields of mathematics and computer science are drawn, and a distinction between ‘algorithms’ and ‘eective procedures’ is proposed. In the second part, we focus on the second goal of the two rival approaches to real computation; namely, to provide foundations for scientific computing. We examine both frameworks in detail, what idealisations they employ, and how they relate to floating-point arithmetic systems used in real computers. We explore limitations and advantages of both frameworks, and answer questions about which one is preferable for computational modelling and which one for addressing general computability issues. In the third part, analog computing and its relation to analogue (physical) modelling in science are investigated. Based on some paradigmatic cases of the former, a certain view about the nature of computation is defended, and the indispensable role of representation in it is emphasized and accounted for. We also propose a novel account of the distinction between analog and digital computation and, based on it, we compare analog computational modelling to physical modelling. It is concluded that the two practices, despite their apparent similarities, are orthogonal.

Η παρούσα διατριβή εξετάζει πτυχές της αλληλεπίδρασης μεταξύ υπολογιστικής και επιστημονικής πρακτικής. Το κατάλληλο θεμελιακό πλαίσιο για μια τέτοια προσπάθεια είναι περισσότερο η πραγματική υπολογισιμότητα παρά η κλασική θεωρία υπολογισιμότητας. Αυτό ισχύει επειδή τα υπολογιστικά προβλήματα στις φυσικές επιστήμες, τις επιστήμες του μηχανικού και τα εφαρμοσμένα μαθηματικά είναι, ως επί το πλείστον, προβλήματα που ενέχουν πραγματικές συναρτήσεις και συνεχή μαθηματικά. Ωστόσο, σε αντίθεση με την περίπτωση υπολογισμών αριθμητικών συναρτήσεων, για την περίπτωση των πραγματικών συναρτήσεων δεν υπάρχει ακόμα μια καθολικά αποδεκτή θεωρία πραγματικής υπολογισιμότητας. Αντ' αυτού, συναντούμε στη βιβλιογραφία δύο πολύ διαφορετικές (και γενικά ασύμβατες) μαθηματικές προσεγγίσεις: την προσέγγιση της υπολογίσιμης ανάλυσης (computable analysis) και την προσέγγιση του μοντέλου BSS ("Blum-Shub-Smale"). Ωστόσο, και οι δύο προσεγγίσεις ως προς την πραγματική υπολογισιμότητα ισχυρίζονται ότι η καθεμία τυποποιεί καταλλήλως την έννοια του «αλγοριθμικό υπολογισμού» και προσφέρει τα αυστηρά μαθηματικά θεμέλια για την πρακτική του επιστημονικού υπολογισμού (αριθμητική ανάλυση). Η διατριβή αποτελείται από τρία μέρη. Στο πρώτο μέρος, εξετάζεται ποια έννοια «αλγοριθμικού υπολογισμού» διέπει κάθε μία από τις δύο προσεγγίσεις της βιβλιογραφίας και, αντιστοίχως, πώς η έννοια αυτή τυποποιείται στην καθεμία. Υποστηρίζεται ότι η ίδια η ύπαρξη δύο ανταγωνιστικών πλαισίων υποδεικνύει ότι η έννοια του «αλγορίθμου» δεν είναι μονοσήμαντη στα μαθηματικά, αλλά στην πραγματικότητα χρησιμοποιείται με περισσότερους από έναν τρόπους, σε διαφορετικούς κλάδους. Εξετάζεται κατά πόσο αυτή η υπόθεση είναι συνεπής με την υπάρχουσα μαθηματική πρακτική καθώς και με βασικές ερευνητικές εργασίες στα θεμέλια των αλγορίθμων οι οποίες έχουν αποσκοπήσει κατά καιρούς να ορίσουν τη συγκεκριμένη έννοια. Ως αποτέλεσμα, η διατριβή δημιουργεί νέες συνδέσεις μεταξύ επιμέρους πεδίων των μαθηματικών και της πληροφορικής, που ως τώρα παραμένουν ασύνδετες· περαιτέρω, προτείνεται μια καινούργια διάκριση μεταξύ των εννοιών του «αλγορίθμου» και της «αποτελεσματικής διαδικασίας» (effective procedure). Το δεύτερο μέρος της εργασίας, εστιάζει στον δεύτερο στόχο των δύο ανταγωνιστικών προσεγγίσεων για την πραγματική υπολογισιμότητα: δηλαδή την παροχή αυστηρών θεμελίων για την μαθηματική περιοχή του επιστημονικού υπολογισμού (αριθμητική ανάλυση). Εξετάζονται λεπτομερώς τα δύο πλαίσια (υπολογιστική ανάλυση και BSS), με ιδιαίτερη έμφαση στο είδος των εξιδανικεύσεων που χρησιμοποιούν και στο πώς σχετίζονται με τα αριθμητικά συστήματα κινητής υποδιαστολής (foating-point arithmetic) που χρησιμοποιούνται για την υλοποίηση υπολογισμών σε πραγματικούς υπολογιστές. Εκτίθενται τα πλεονεκτήματα και οι περιορισμοί των δύο μαθηματικών προσεγγίσεων και απαντώνται ερωτήματα σχετικά με το ποια από τις δύο είναι καταλληλότερη να παρέχει μαθηματικά θεμέλια για διαδικασίες υπολογιστικής μοντελοποίησης και ποια για την αντιμετώπιση ευρύτερων προβλημάτων υπολογισιμότητας. Στο τρίτο μέρος της διατριβής, διερευνάται επιστημολογικά ο αναλογικός υπολογισμός και η σχέση του με την αναλογική/φυσική μοντελοποίηση (δηλαδή τη χρήση φυσικών μοντέλων κλίμακας--scale models) στην επιστημονική πρακτική. Με βάση ορισμένες παραδειγματικές περιπτώσεις αναλογικών υπολογιστών, προτείνεται μια συγκεκριμένη προσέγγιση ως προς τον ορισμό και τη φύση του «υπολογισμού» εν γένει, κατά την οποία αποδίδεται ιδιαίτερος επιστημικός ρόλος στην έννοια της «αναπαράστασης». Επιπρόσθετα, προτείνεται μια νέα ερμηνεία της διάκρισης μεταξύ «αναλογικού» και «ψηφιακού» υπολογισμού και, βάσει αυτής, συγκρίνονται επιστημολογικά η πρακτική της αναλογικής υπολογιστικής μοντελοποίησης και η πρακτική της φυσικής μοντελοποίησης (χρήση μοντέλων κλίμακας). Συμπεραίνεται ότι, παρά τις φαινομενικές τους ομοιότητές τους, οι δύο αυτές πρακτικές είναι επιστημολογικά ασύμμετρες.