Pure mathematics and computer science intersect more than the people in either field would have you believe. As a software developer studying mathematics, this area of pure-applied-maths-programming fascinates me. This summer I had the privilege of researching this exciting area of pure-applied-maths-programming. The mathematics and the code that I work with are both “object oriented,” so it should be easy to translate between them, right?
Mathematicians create powerful metaphors called “mathematical objects” to describe and abstract logical relationships. We’re all familiar with numbers and with the operations we use on them: addition, subtraction, multiplication, division. By generalising the rules that numbers and operations abide by, mathematicians came up with abstract algebras. These are templates for sets of things that interact in defined ways. Similarly, mathematicians generalised surfaces to topological spaces and shapes to abstract geometries.
Computer science developed differently, but in many ways in parallel to mathematics. Much of the software we rely on in our day to day lives is so-called “object oriented.” The 0’s and 1’s that load our websites and trigger our car’s parking sensor are organised into neat data structures that interact with each other according to defined rules. With polymorphism and generic programming, software developers can write templates that describe how things of a certain type should look and behave. Almost like a mathematical object.
The mathematics and the code that I work with are both “object oriented,” so it should be easy to translate between them, right? I was presented with a paper that explained how to solve a group theoretic problem, the integral conjugacy problem, in a way that is impenetrable to most people. That’s because it’s described entirely in terms of mathematical objects – matrices, rings and modules to name a few – and the complex rules by which they interact.
The author claims that the procedure can be easily translated into “quite practical computer algorithms”. I can confirm that translating mathematical objects into signals that a CPU can understand is rarely a simple task. Sometimes a line of code tells a thousand words and sometimes the opposite is true. The languages of mathematics and coding developed with different goals, so unsurprisingly they differ vastly in structure.
If a problem is decidable, that means that an algorithm exists that is guaranteed to produce a solution in a finite number of operations. This is what mathematicians care about. For an algorithm to be computationally feasible, replace finite with reasonable. The problem I worked on fell into the category of decidable, but usually not computationally feasible.
This raised a question that has divided programmers and mathematicians since the beginning. If a problem is decidable but the algorithm that decides it is not computationally feasible, has the problem really been solved?
University of Wollongong