Is software a kind of mathematics? – From an ongoing discussion on the Humanist list [#DH #Digital Humanities]

I’ve appended two emails I recently sent to the Humanist list. They’re recent contributions to a long and winding discussion.

* * * * *

There’s a somewhat diffuse set of conversations going on over the last few weeks or so. I believe it’s been precipitated by remarks Willard made in Humanist 34.27: punctuation in the assignment statement. Almost at the end Willard remarked:

So I translate "X is to be MADE equal to the sum of Y and Z". Or, we might say, "Warning: this is NOT an algebraic statement!" Or, better, I think: "Here we must stretch our understanding of mathematics to include something new.

It’s that very last sentence that interests me, about stretching our understanding of mathematics. In Humanist 34.39 Willard elaborates on the target and scope of his inquiry:

I'm looking for evidence concerning the realisation or conviction that software, though mathematical in some sense, is "mathematics with a difference", as Mahoney wrote in "Computer science: The search for a mathematical theory". To ask whether software is mathematics or is essentially mathematical, expecting a yes-or-no response even if with arguments, seems to me too crude an instrument. So, I am wanting to ask, what is software in relation to mathematics? I don't assume that either is a well-defined (or confined) thing.

So, is software to be considered a kind of mathematics, with that little bit of notation as evidence bearing on the matter?

I’ll leave notation aside. It’s the relation between mathematics and software that concerns me. It seems to me that there’s a bit of ambiguity in the word “mathematics”. My dictionary tells me that it’s “the abstract science of number, quantity, and space…” That is, it is an intellectual discipline, something that people do. My dictionary also offers: “the mathematical aspects of something: the mathematics of general relativity.” That seems a bit different. Here “mathematics” is functioning not so much a discipline as it is the objects which that discipline is about.

What of “software”? Software is not at all a discipline. Computer programming is the discipline concerned with software. Whatever computer programming is, it is not reasonably considered a branch of mathematics. Nor for that matter does it make much sense to think of computer programs directly as mathematical objects, though we may subject them to mathematics analysis, which is a different matter (in principle, we can subject anything to mathematical analysis).

So, notation aside, I agree with Willard that “whether software is mathematics or is essentially mathematical, expecting a yes-or-no response even if with arguments, seems to me too crude an instrument.” Software is something else. Though it has some kinship with mathematics, it also has some kinship with natural language. But it does seem to me that we must think of it as something in itself, different from both mathematics and natural language. It is something new that entered the world in the decades after World War II.

This thoughtful paper by László Lovász explores how current developments in mathematics might alter how and what we teach. Though written in 2008, it asks questions that are still fresh and necessary, but not yet widely appreciated. https://t.co/vkKu94eBwB [PDF] (ht Etienne Ghys)

— Steven Strogatz (@stevenstrogatz) June 10, 2020

I’ve just come across (via Steven Strogatz on Twitter) a March 2008 paper by László Lovász that’s relevant to our ongoing discussion of software, mathematics, and the machine: Trends in Mathematics: How they could Change Education? Here’s the link:

https://web.cs.elte.hu/~lovasz/lisbon.pdf

I’m copying some paragraphs from section 5.1, Algorithms and programming.

The traditional 2500 year old paradigm of mathematical research is defining notions, stating theorems and proving them. Perhaps less recognized, but almost this old, is algorithm design (think of the Euclidean Algorithm or Newton’s Method). While different, these two ways of doing mathematics are strongly interconnected (see [6]). It is also obvious that computers have increased the visibility and respectability of algorithm design substantially.

Algorithmic mathematics (put into focus by computers, but existent and important way before their development!) is not the antithesis of the “theorem–proof” type classical mathematics, which we call here structural. Rather, it enriches several classical branches of mathematics with new insight, new kinds of problems, and new approaches to solve these. So: not algorithmic or structural mathematics, but algorithmic and structural mathematics!

So, we’ve got a distinction between algorithmic and structural mathematics. [And remember, “algorithm” is derived from the name of a mathematician, al-Ḵwārizmī.]

Moving on:

The beginning of learning “algorithmics” is to learn to design, rather than execute, algorithms [8]. The euclidean algorithm, for example, is one that can be “discovered” by students in class. In time, a collection of “algorithm design problems” will arise (just as there are large collections of problems and exercises in algebraic identities, geometric constructions or elementary proofs in geometry). Along with these concrete algorithms, the students should get familiar with basic notions of the theory of algorithms: input-output, correctness and its proof, analysis of running time and space, etc.

Here, notice the distinction between designing algorithms and executing them.

And now we come to the computer (programming language running on hardware):

One should distinguish between an algorithm and its implementation as a computer program. The algorithm itself is a mathematical object; the program depends on the machine and/or on the programming language. It is of course necessary that the students see how an algorithm leads to a program that runs on a computer; but it is not necessary that every algorithm they learn about or they design be implemented. The situation is analogous to that of geometric constructions with ruler and compass: some constructions have to be carried out on paper, but for some more, it may be enough to give the mathematical solution (since the point is not to learn to draw but to provide afield of applications for a variety of geometric notions and results).

So, an algorithm is to be distinguished from its implementation*. A given algorithm could be implemented using a variety of programming languages, with some being more hospitable than others. And the same is true for the underlying hardware. In particular, some algorithms may benefit from a parallel architecture, while others may not.

I present three more paragraphs without comment:

Let me insert a warning about the shortcomings of algorithmic language. There is no generally accepted form of presenting an algorithm, even in the research literature (and as far as I see, computer science text books for secondary schools are even less standardized and often even more extravagant in handling this problem.) The practice ranges from an entirely informal description to programs in specific programming languages. There are good arguments in favor of both solutions; I am leaning towards informality, since I feel that implementation details often cover up the mathematical essence. For example, an algorithm may contain a step “Select any element of set S”. In an implementation, we have to specify which element to choose, so this step necessarily becomes something like “Select the first element of set S”. But there may be another algorithm, where it is important the we select the first element; turning both algorithms into programs hides this important detail. Or it may turn out that there is some advantage in selecting the last element of S. Giving an informal description leaves this option open, while turning the algorithm into a program forbids it.

On the other hand, the main problem with the informal presentation of algorithms is that the “running time” or “number of steps” are difficult to define; this depends on the details of implementation, down to a level below the programming language; it depends on the data representation and data structures used.

The route from the mathematical idea of an algorithm to a computer program is long. It takes the careful design of the algorithm; analysis and improvements of running time and space requirements; selection of (sometimes mathematically very involved) data structures; and programming. In college, to follow this route is very instructive for the students. But even in secondary school mathematics, at least the mathematics and implementation of an algorithm should be distinguished.

* * * * *

*In a series of discussions I had with David Hays a number of years ago he emphasized the fundamental importance of implementation. As I said almost a decade ago:

...we talked of the universe as being fecund (Hays proposed the term), with later Realms of Being implemented in ones that had evolved earlier. Our notion of implementation, which derives from computer science, seems kin to Latour’s notion of composition. Objects of one kind can be said to be implemented in, composed of, objects of some other kind. But the implemented/composed objects cannot be reduced to the objects of which they are composed/implemented.

The full discussion:  Fecundity and Implementation in a Complex Universe.