Finding those math theorems or conjectures just too hard to prove? Then, you need to attend this workshop.
Category Archives: Computer science
Rho calculus
One important thread in computer science is the study of extensions of the lambda calculus. The lambda calculus is a model of computation that uses rewrite rules based on a simple notion of a function. The rho calculus extends the lambda calculus to allow more general rewrite rules based on pattern matching. For a survey, see the paper Matching Power or the web site The Rho-Calculus Home Page.
Via Lambda the Ultimate.
3x+1
Jeffrey Lagarias has been maintaining a summary of work on the Collatz problem, which is arguably the easiest open problem in mathematics: The 3x+1 problem: An annotated bibliography. It’s disturbing that such a simple problem is unsolved.
Wikipedia on corecursion
If anyone’s interested in contributing to Wikipedia, here’s an opportunity. To fix some errant links, I’ve just created a stub page on corecursion. Unfortunately, I know almost nothing about the topic, so if you do, now’s your chance to show off.
Alg-top in CS
In a post below, I mentioned algebraic topology in computer science. A nice application of alg-top is for study of concurrency in distributed systems. For instance, one approach is to consider execution traces of a computational system being represented by time-directed paths through a space, and then to use alg-top methods to ask and answer questions about the structure of this space.
This approach leads naturally to a concept of homotopies of paths, equivalence classes of paths which may be transformed into one another via other paths in the space. What is different from traditional homotopy theory is that the paths are directed, and so these are referred to as directed homotopies or dihomotopies. Paths which are not dihomotopically equivalent represent execution traces on which there are events not reachable from one to another. For more on this, start with the GETCO conference pages.
New uses for Grothendieck topologies
I’ve been saying for a while that the big problems in computer science (eg, P vs NP; a theory of distributed systems; effective GO-playing machines; etc) need radical new methods, and I have suggested algebraic topology as a likely source of ideas. Joel Friedman has just applied some alg-top to boolean complexity, motivated by the P vs. NP problem, in Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity.
Lothaire is back!
A few months ago I claimed that there was a “new“ Lothaire book, Algebraic Combinatorics on Words. This was a brazen lie on my part — the book, published in 2002, has already reached the advanced age of 3. I came across the web page of Jean Berstel, which has a link to an an actual new Lothaire book, Applied Combinatorics on Words. This one really is published in 2005.
Berstel also has a link to the text of Theory of Codes, a book he cowrote with Dominique Perrin.
Computing with real numbers
I just spotted an interesting paper on Arxiv: Computing over the Reals: Foundations for Scientific Computing, which suggests a new model of computation with real numbers.
The Muddy Children Problem
Many mathematicians grew up on a diet of puzzles like those set by Raymond Smullyan and Martin Gardner. Unfortunately, ingenious and elegant as these puzzles often are, they frequently have solution methods that don’t give rise to generalisable theory.
So I was recently surprised to find that one of my favourite puzzles of this type, the Muddy Children Problem, is actually an important example that appears in courses on mathematical logic, epistemology, computer science and even quantitative finance. If you haven’t met the problem before then have a go at solving it before looking at the various papers and courses on the subject. A fairly detailed elementary treatment can be found here though there are easier to understand informal arguments in existence.
The main academic approaches to the problem are via modal logic and Kripke models.
In less politically correct days it was known as the unfaithful wives problem and Smullyan’s version of this problem involved logicians with coloured hats.
Did I mention that it’s also a drinking game?
Expander Graphs
It’s basically impossible to know all of the important concepts and results in mathematics. It’s impossible to even have heard of all of the important concepts and results in mathematics. For example, I’d never heard of expander graphs, which apparently have widespread applications in combinatorics and computer science, and even have an interpretation in terms of group representations.
Michael Nielsen has a series of posts on expander graphs beginning here. For more background, he links to lecture notes on the subject by Linial and Wigderson.