jump to navigation

Case Study III: Computer Science: The bestiary of potential infinities December 15, 2007

Posted by Alexandre Borovik in Uncategorized.
trackback

We quote a professional computer scientist who left the following comment on the blog of one of us:

I would caution everyone … not to confuse “mathematical thinking” with “The thinking done by computer scientists and programmers”.

Unfortunately, most people who are not computer scientists believe these two modes of thinking to be the same.

The purposes, nature, frequency and levels of abstraction commonly used in programming are very different from those in mathematics.

We would like to illustrate the validity of these words on a very simple example.

Let us look at a simple calculation with MATLAB, an industry standard software package for mathematical computations.

>> t= 2

t = 2

>> 1/t

ans = 0.5000

What is shown in this screen dump is a basic calculation which uses floating point arithmetic for computations with rounding.

Next, let us make the same calculation with a different kind of integers:

>> s=sym(‘2’)

s = 2

>> 1/s

ans = 1/2

Here we use “symbolic integers”, designed for use as coefficients in symbolic expressions.

Next, let us try to combine the two kinds of integers in a single calculation:

>> 1/(s+t)

ans = 1/4

We observe that the sum s+t of a floating point number $t$ and a symbolic integer s is a symbolic integer.

Examples involving analytic functions are even more striking:

>> sqrt(t)

ans = 1.4142

>> sqrt(s)

ans = 2^(1/2)

>> sqrt(t)*sqrt(s)

ans = 2

We see that MATLAB can handle two absolutely different representations of integers, remembering, however, the intimate relation between them.

The example above is written in C++}. When represented in C++, even the simplest mathematical objects and structures appear in the form of (a potentially infinite variety of) classes linked by mechanisms of inheritance and polymorphism. This is a manifestation of one of the paradigms of the computer science: if mathematicians instinctively seek to build their discipline around a small number of “canonical” (actually) infinite structures, computer scientists frequently prefer to work with a host of potential infinities controlled and handled with the help of a special technique which is category-theoretic by its nature. In the context of Computer Science, a category-theoretic approach frequently has an advantage over the set-theoretic: in the example above, the set of “symbolic” integers appears as a process for building its elements; it is not closed, its boundaries are not defined. We find ourselves in the situation summarised in the famous words by Henri Poincare:

“There is no actual infinity; and when we speak of an infinite collection, we understand a collection to which we can add new elements unceasingly.”

When we move from integers to other algebraic structures ofinterest for practical applications, for example, (finite)abelian groups and finite fields, we see a real explosion in variety and diversity of their computer realisations. Ofcourse, any two Galois fields of the same order p^n are isomorphic, but they can be constructed in different ways. What is important, the variation of computational complexity of different realisations of the same structure is the key issue of algebraic cryptography, with tremendous implications for information security. In the traditional discussion of “identity” or “sameness” of mathematical objects, the complexity-theoretical aspect of the problem has been mostly ignored.

The link between computer science and category theory is especially interesting because we shall look, in the next case study, at the real time emergence of yet another form of actual infinity in a developing mathematics discipline: the higher-dimensional category theory.

Advertisements

Comments»

1. Peter - December 16, 2007

Your example from Computer Science reminds me of something often forgotten or overlooked in present-day discussions of infinite structures: that some of the motivation for the study of the infinite in mathematics in the 19th and early 20th centuries came from physics where (strange as it may seem to a modern mathematician or a computer scientist) the infinite was used as an approximation to the very-large-finite.

The study of collectivities of particles in condensed matter physics, for example, was made mathematically easier by assuming an infinite, rather than a finite, collection of particles. The same metaphor (the infinite as an approximation for the large-finite) underlies the entire discipline of (parametric) mathematical statistics, with its reliance on the central limit and other convergence theorems, and on probability distributions from the exponential family, such as the Normal distribution. Application of this metaphor to small-finite situations, naturally enough, is problematic, something statisticians, if not always others, usually acknowledge.

I would recommend von Plato’s enjoyable book on the history of probability theory for more on this metaphor.

@BOOK{vonplato:boook94,
author = “J. {von Plato}”,
title = “Creating Modern Probability: Its Mathematics, Physics and Philosophy in Historical Perspective”,
publisher = “Cambridge University Press”,
year = “1994”,
series = “Cambridge Studies in Probability, Induction, and Decision Theory”,
address = “Cambridge, UK”}

I wonder if omega-categories are another instance of this metaphor — ie, the study of an infinite space or object is needed to give us a profound understanding of an apparently finite property (“sameness”). If so, this strikes me as yet further evidence of the mystical nature of mathematics.

2. Jonathan Vos Post - December 19, 2007

Should we call: “There is no actual infinity” by the name: Henri Poincare’s Axiom of Non-infinity?

There do seem to be some extreme Constructivists who accept it.

3. Mitch - December 19, 2007

The purposes, nature, frequency and levels of abstraction commonly used in programming are very different from those in mathematics.

We would like to illustrate the validity of these words on a very simple example.

I still don’t get it…I can accept that there is a particular worldview where this difference occurs, but I have yet to see any evidence supporting it (beyond the superficial).

The “purposes, nature, frequency and levels of abstraction commonly used in programming” are all -mathematical-. They might well not be the ones commonly used in ‘mainstream’ areas of mathematics, but combinatorics and logic .

If you are trying to draw a distinction between the cultures bound up with the infinity of the continuum and that of the naturals, that is certainly something, but quite irrelevant to ‘… and levels of abstraction…’.

And then you connect thinking in CS and category theory (perfectly understandable) but is that in contrast to the rest of mathematics?

The more times this contrast is stated, the more it makes me think how much they are the same.

4. Jacques - December 21, 2007

Conflating Matlab and computer science is almost criminal. Matlab does not even properly represent numerical analysis! Certainly one cannot derive anything from Matlab other than that its designers had a non-standard view of mathematics.

Now, a proper study of all forms of computerized mathematics would be much more instructive. There is dedicated software out there for statistics (R, SAS, SPSS, etc), numerical computation (Matlab, Scilab, Octave), symbolic computation (Maple, Mathematica, Mupad, Axiom, etc) and theorem proving (Coq, Isabelle, Mizar, PVS, etc). Each and every class of software has a radically different view of mathematics; and even within a class, there can be interesting differences. For symbolic computation, an older but still relevant comparison is Michael Wester’s critique of CA systems.

5. dcorfield - December 21, 2007

Thanks for your comment Jacques. This is perhaps the case study in which we have least collective expertise, but one which I hope will give us much to think about.

6. Alexandre Borovik - December 22, 2007

Jacques said:

“Conflating Matlab and computer science is almost criminal. Matlab does not even properly represent numerical analysis!”

It depends on the point of view. We are looking at the basic underlying structures of the two disciplines, mathematics and computer science. It is immediately noticeable that mathematics deals with mathematical object and structures up to isomorphism, while computer science is concerned with the much more subtle issues of algorithmic implementations. In mathematics, any two finite fields of order pn are isomorphic, while the cryptography has to deal with potentially unbounded families of implementations of finite fields in software/hardware, sometimes having dramatically different security properties in relation, say, to side channel attacks.

Computer science, cryptography, programming are the areas where it becomes really obvious that the issues of infinity / finiteness of particular classes of objects have to be preceded by clear understanding of identity / sameness / difference of objects.

It could be a rather offensive formulation, but mathematics can be defined as part of computer science which abstracts away from data formats.

7. Jacques - January 3, 2008

I will repeat my basic objection: one should not take any commercial implementation of a (part of) mathematics as representative of anything regarding computer science. As an analogy, few would ever think to conflate Windows and what proper computer scientists think of as an “operating system”.

Now, as far as the substantive comments in your comment of December 22nd go, I completely agree! The difference between denotation and connotation has been a concern of mine for a while, but I (unfortunately) have not written much about it — although I have just finished teaching a graduate course on that topic.

As you have noticed, mathematicians really worry about extensional objects (and classes thereof), while computer scientists have to worry about intension a lot more. Nevertheless, mathematicians use intension all the time, especially when teaching basic Calculus. For example, when students are taught how to compute closed-forms for indefinite integrals, they are often presented with theorems (such as integration by parts) which are stated (and proved) as extensional theorems but almost always used intensionally! In other words, one uses integration-by-parts by pattern-matching on the syntax of the problem, even though the underlying rule works (and is stated) for any product of functions.

I will finish this comment with one of my favourite exercises in “symbolic analysis”:
1) Let x be a real number. How many solutions are there to y^2-x^2 = 0 ?
2) Let y(x) be a real-valued function of a real variable. How many solutions are there to y(x)^2-x^2 = 0 ?
The answer is quite topical for this blog, as at its core are different notions of infinity.

8. MJ - February 16, 2009

i need cases of computer science


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: