Hofstadter's MIU System

A different sort of blog post today: I figured we'd take a quick break from SICP and have a look at a puzzle from another book I've been working my way through lately. Gödel, Escher, Bach: an Eternal Golden Braid by Douglas Hofstadter is a famous book that I've seen on dozens of must-read lists for both computer science and mathematics.

It's not hard to see why, either. Though the book is touted as ultimately being about the nature of "consciousness" and whether we can get computers/robots to emulate such a thing, from the small amount of it I've read so far I can see that it touches on many other mathematical concepts too: the idea of formal systems, isomorphism and its relation to meaning and especially recursion and self-reference.

Early on in the book, Hofstadter shows us a formal system – the MIU system. Given a string of letters in the MIU system, we can generate additional strings by applying particular rules. This forms the context for the MU puzzle: can we start with a string, say the string MI, and through successive application of the rules of the system, end up with the string MU?

I won't spoil the solution here, of course! But the entirety of the book's discussion on the MIU system itself – with its rules, its strings, and its metaphorical "genie" that can generate infinitely many MIU strings given enough time – well, it was pretty much daring for a programmatic implementation.

So that's the topic for today. With JRuby as our programming language, together with some very basic use of regular expressions, we'll devise a code implementation of this MIU system and use it to generate some strings!

The N-Queens Puzzle and 0-1 Integer Linear Programming

We saw in the last post how we can tackle the N-Queens Puzzle recursively by considering each column in turn. This way, we can generate all of the possible solutions to the puzzle (eventually!)

However as we'll see today, we can also consider the puzzle in terms of an optimization, according to some constraints upon the rows, columns, and diagonals of the chessboard. By formulating the N-Queens puzzle as an instance of a 0-1 Integer Linear Program, we can pummel it with the full force of modern combinatorial optimization tools!

So that's the plan. First we'll develop a mathematical formulation for the N-Queens puzzle. Then we'll see how we can translate the variables and constraints of the problem into a matrix representation in Java code, which we can pass into some open-source linear programming tools: the SCPSolver together with the GNU Linear Programming Kit (GLPK).

The N-Queens Puzzle and Recursion

One of the cooler exercises from the Structure and Interpretation of Computer Programs is Exercise 2.42: finding solutions to the N-Queens Puzzle.

The N-Queens Puzzle is a sort of chess puzzle. Suppose we have an NxN chessboard, and N queen pieces. We want to find a way to position the pieces so that none of the queens can capture each other. In fact, we want to find all possible ways to do this.

Over the next couple of blog posts, we'll consider two techniques for getting a grasp on this puzzle:

• Today, we'll look at a recursive method that constructs the set of all feasible solutions by building them up a column at a time, which we'll implement using Clojure.
• In the next post, we'll see how we can formulate the N-Queens puzzle as a 0-1 Integer Linear Program (ILP), which we can solve using Java in conjunction with some open source operations research tools; namely the SCPSolver with the GNU Linear Programming Kit (GLPK).

Higher-Order Functions and Accumulation

The notion of a higher-order function – that is, a function that operates on other functions – is a fundamental idea in mathematics.

As an easy example, take the concept of differentiation from Calculus. Whereas a "normal" function like sin(x) operates in terms of numbers (ie. pass it a number, and it'll return you a number as a result), the act of taking a derivative is a little different. When we take the derivative of a function, we get back another function.

This is actually an incredible idea. Now not only can we talk about transformations (of numbers), but we can talk about transformations of transformations!

So in yet another of my blog posts about things I've investigated while working my way through the Structure and Interpretation of Computer Programs, we're going to look at this idea of higher-order functions by considering the process of accumulation.

We'll write some procedures for calculating sums and products, and then show how we can abstract away the common process of successively combining new elements with a current total. We'll then go a step further and write a more general procedure for filtered-accumulation, where we only take those elements that satisfy a particular condition.

[The relevant SICP exercises for this one are 1.30, 1.31, 1.32, and 1.33.]

We're gonna be using good old Java today. In fact, this topic gives us the perfect opportunity to explore the new functional interfaces and lambda expressions of the latest Java 8 release!

Newton's Method

As a follow-up from the previous post dealing with fixed-point iteration, another particularly useful family of numerical techniques deals with the iterative approximation of zeros (or roots) of a given function – that is, those points x where the value of a function f is zero, or f(x)=0. One such technique is Newton's Method (or the Newton-Raphson Method, if you like.)

The idea behind Newton's Method is as follows. If we suppose that we can use Taylor's Theorem to get a polynomial approximation to a function f in the neighbourhood of points that we care about, then we can actually use our fixed-point iteration to converge upon an approximation for a root of f.

So we'll do just that: we'll derive an expression from Taylor's theorem that we can use for the fixed-point iteration, and then code it up. We can then use our code to find the roots of some polynomials, as well as to implement another square-root finding procedure. As for the JVM language we'll use? We haven't seen JRuby make an appearance yet on this blog, so it's about time for its debut! 

Finding Fixed-Points of Functions

Quite often in scientific computing we're interested in finding the fixed-points of a function or transformation: those points where the value of the function f at a point x is equal to x itself, ie. f(x) = x. You can see how these might be useful – if the function f models any kind of real-world phenomenon, then a fixed-point suggests a sort of equilibrium or steady-state.
 
In fact, fixed-point iteration can be used in many numerical methods. Newton's method for finding the zeros of a differentiable function (which we'll look at in a later post) can be written in terms of a fixed-point computation, and many methods for solving ordinary differential equations apply these same fixed-point ideas.

In this post we'll code up a Scala function to (hopefully!) converge upon the fixed-points of a given transformation, and look at some examples; including a method for finding square roots of a number. We'll also look at the general technique of average-damping that we can apply to ensure/quicken convergence in particular cases.

[Inspired by the Structure and Interpretation of Computer Programs. (noticing a pattern yet?) The book is here, and the relevant Scheme solutions are for Exercises 1.35 and 1.36.]

Recursive Sine Approximation

For a quick smaller post today, we'll look at an approximation for the sine of an angle. (As always, SICP is the inspiration, and the Scheme solution for the relevant Exercise 1.15 can be found here.)

We saw in the last post that we could approximate the tangent function using Lambert's continued fraction representation. We can find a similar idea of an approximation for the sine function by using the following trigonometric identity:

So the plan is to implement that idea with some Scala code. We'll quickly look at the efficiency of the implementation, and then use it to compute a few examples. Easy.