Monthly Archives: June 2011

Turing Machines and Conway’s Dreams

Posted on by
1

Additional Patterns

Last time we left the reader with the assertion that Conway’s game of life does not always stabilize. Specifically, there exist patterns which result in unbounded cell population growth. Although John Conway’s original conjecture was that all patterns eventually stabilize (and offered $50 to anyone who could provide a proof or counterexample), he was proven wrong. Here we have the appropriately named glider gun, whose main body oscillates, expelling a glider once per period. Here is an initial configuration:

An initial position for the glider gun

And its animation:

This glider gun was the first one of its kind ever discovered. To distinguish it from the now large class of “gun” patterns, it is called Gosper’s glider gun. It has the smallest initial population of any known gun (hint, hint: find a smaller one and get famous!).

Second, we have examples of moving patterns which leave stationary patterns as they travel. These are commonly called puffers. For the sake of amazement, we give the coolest puffer we could find, which actually lays Gosper guns! (credit to Wikipedia for the image)

At the end of the animation, the red colored cells are the puffer, the green are Gosper guns, and the blue are the emitted gliders.

So (after the work of many in searching for these patterns), we see that under special circumstances Life can grow without bound. This has an interesting connection to computability. Specifically, any model of computation in which every computation is guaranteed to stop (in the case of cellular automata, this is reaching a stable state) cannot be Turing-complete.

[Note: the details on Turing machines are covered in this blog's primer on the theory of computation, but the reader may recall that a system for computation which is Turing-complete can do any computation that can be done on any other Turing machine. This includes performing arithmetic, simulating Conway's Game of Life, and performing the functions of a web browser.]

So colloquially, being able to simulate an infinite loop (or infinite recursion) is required to do interesting computations. More rigorously, if an automaton is to simulate a Turing machine, then it must be able to loop infinitely, because a Turing machine can.

But we have just found that Life can simulate infinite loops. Specifically, a Gopser gun or the puffer above both simulate an infinite counter, counting the number of emitted/laid patterns. Admittedly, we can’t do much with just an infinite counter, but it gives us the hint that we may be able to construct the elementary pieces of a real computation engine. We conjecture now that Life is Turing-complete, and will prove it by construction. While it would be amazing to fit such a proof in a blog post, in reality we will explain a sketch the proof, elaborate on certain parts, and defer to the large body of work already done on this problem to assert our claim.

Bits and Gates

Recall there is a sufficient pair of conditions for a computational model to be Turing-complete: the ability to implement arbitrary logic functions and the existence of a model for random access memory (the read-write tape and write head).

In standard computers, these logic functions are built up via elementary logic gates. High and low current, representing 1 and 0, respectively, are sent through the logic gates, which output the appropriate level of current corresponding to the logic function. The easiest set of complete logic gates are And, Or, and Not, from which any arbitrarily complex truth table can be built.

On the other hand, it is not hard to prove that the Nand (X Nand Y := Not (X And Y)) function alone is sufficient to implement all logic functions. And so in contemporary circuit design, Nand gates (which are cheap to manufacture) are used in the billions to implement all of the necessary logic in a computer chip.

Hence, the ability to simulate a complete set of logic gates in Life is necessary for its Turing-completeness. From our investigation of the patterns above, there is one obvious candidate for current: a Gosper gun. A stream of emitted gliders corresponds to high current, and an absence to low. We include a special “eater” stationary pattern which controls the current.

The Gosper gun current, with an eater to control flow. The glider passes through iff the red cell is alive.

Further, another copy of this eater can be used to manage the output, and multiple eaters can be combined to handle two input streams, thus implementing logic. Indeed, the construction is very detailed, and requires a lot of tinkering to understand. Here we present the And gate, and send the reader to LogiCell for the designs of Or and Not.

Logical And gate

A and B represent the input currents to the gate, while C is a continuous stream. The two eaters at bottom center allow a current to pass through if and only if the current hitting it comes from B and only B. Current coming from A collides with C, cancelling both streams. If A is off (as it is in the diagram above), then B cancels with C and the eaters simultaneously, and no gliders get through. If A is off but B is on, then A cancels with C, and B still does not hit get through. However, if A and B are both on, then everything works great.

So building up from the And, Or, and Not pieces, we may implement every possible logic function. Thus, as in the original proof of Life’s Turing-completeness, we can model a finite state machine attached to two counters, which itself is Turing-complete.

[The proof of the two-counter Turing-completeness is sketched as follows. Every Turing machine can be simulated by two stacks. i.e., If H is the position of the read-write head of a Turing machine, then the head of one stack corresponds to the values to the right of H including H, while the second stack corresponds to the values strictly to the left of H. Then, any stack can be simulated by two counters, where the bits of one counter are the bits in successive cells in the stack, and the second number is required extra space for stack operations. Hence, a two stack machine can be simulated by four counters. Finally, four counters may be simulated by two counters, where one counter contains a number x=2^a3^b5^c7^d, where a,b,c,d correspond to the integer values of our four simulated counters, and the second counter is used in the arithmetic to modify x. Therefore, one counter contains the information of all four stacks. Working backward, a finite state machine which can control two counters has the same computing power as a Turing machine. It is thus Turing-complete.]

A Gargantuan Pattern

Now, proving Turing-completeness and implementing a computing machine within Life are two very different things. For one thing, we require some system of registers and memory access. Amazingly enough, researchers have created fully universal Turing machines (which can simulate other Turing machines). We point the reader to a picture of the initial configuration for a small Turing machine and a very detailed description of its parts and instruction set.

The glorious promise of Turing-completeness must be taken with a grain of salt. If we were to run within Life some wonderful computation that we might actually find useful as human beings, it would probably take longer than the life of the sun to complete. Indeed, we don’t actually care about computational speed or the prettiness of its output. Our true goal was the theoretical proof that this model is equivalent in power to a Turing machine. This has a number of profound implications (most of which have been voiced before by the Big Names of mathematics).

Specifically, we initially started with a very simple set of rules. From this, we observed much chaotic behavior, but found some order in still patterns, gliders, and oscillators. After thoroughly mastering these pieces, we suddenly found the ability to compute anything that can be computed! All of this order was hiding in chaos.

Furthermore, given an infinite grid with random initial configuration, a Turing machine sub-pattern is guaranteed to exist in it with probability 1 (see the Infinite Monkey Theorem). Not only that, but there are guaranteed to exist sub-patterns corresponding the Turing machines for every possible computation. This includes the Facebook social graph, Halo 3, the proof of the Four Color Theorem, and every program that will ever be written in the future. All in the same grid.

So with the minuscule initial design of a few simple rules, and given enough randomness, there is guaranteed to be order and elegance of the most magnificent and mind-boggling nature. Not even in Conway’s wildest dreams would we find such beauty! This is a gem of mathematics. We leave it to the reader to extrapolate philosophy and debate theories of intelligent design; we are content to admire.

At some point in the future, we wish to investigate using genetic programming to search for “interesting” Life patterns. Furthermore, the idea came upon us to run a Life-like game with k-regular cells where k is arbitrary. For large k, tessellation of these cells is only possible in the hyperbolic plane, but with the appropriate geometric software, this may give an interesting visualization of a variant of Life where, say, each cell has eight, nine, or ten neighbors (hexagonal cells has been done, as tessellation is easy in the Euclidean plane). Of course, even though a hyperbolic tessellation is indeed infinite, the cells grow exponentially smaller as they near the edge of the plane, effectively restricting our working space. Implementing this variant would require a bit of research, so we will likely write on other topics in the mean time.

Until next time!

About these ads

The Wild World of Cellular Automata

Posted on by
12
So far on this blog we’ve been using mathematics to help us write interesting and useful programs. For this post (and for more in the future, I hope) we use an interesting program to drive its study as a mathematical object. For the uninformed reader, I plan to provide an additional primer on the theory of computation, but for the obvious reason it interests me more to write on their applications first. So while this post will not require too much rigorous mathematical knowledge, the next one we plan to write will.

Cellular Automata

There is a long history of mathematical models for computation. One very important one is the Turing Machine, which is the foundation of our implementations of actual computers today. On the other end of the spectrum, one of the simpler models of computation (often simply called a system) is a cellular automaton. Surprisingly enough, there are deep connections between the two. But before we get ahead of ourselves, let’s see what these automata can do.

A cellular automaton is a space of cells, where each cell has a fixed number of possible states, and a set of rules for when one state transitions to another. At each state, all cells are updated simultaneously according to the transition rules. After a pedantic, yet interesting, example, we will stick to a special two-dimensional automata (n \times n grids of cells), where the available states are 1 or 0. We will alternate freely between saying “1 and 0,” “on and off,” and “live and dead.”

Consider a 1-dimensional grid of cells which has infinite length in either direction (recalling Turing Machines, an infinite tape), where each cell can contain either a 0 or 1. For the sets of rules, we say that if a cell has any immediately adjacent neighbor which is on, then in the next generation the cell is on. Otherwise, the cell is off. We may sum up this set of rules with the following picture (credit to Wolfram MathWorld):

The state transition rule for our simple cellular automaton.

The first row represents the possible pre-transition states, and the second row is the resulting state for the center cell in the next generation. Intuitively, we may think of these as bacteria reproducing in a petri dish, where there are rigorous rules on when a bacteria dies or is born. If we start with a single cell turned on, and display each successive generation as a row in a 2-dimensional grid, we result in the following orderly pattern (again, credit to Wolfram MathWorld for the graphic):

The resulting pattern in our simple cellular automaton.

While this pattern is relatively boring, there are many interesting patterns resulting from other transition rules (which are just as succinct). To see a list of all such elementary cellular automaton, see Wolfram MathWorld’s page on the topic. Indeed, Stephen Wolfram was the first to classify these patterns, so the link is appropriate.

Because a personification of this simulation appears to resemble competition, these cellular automata are sometimes called zero-player games. Though it borrows terminology from the field of game theory, we do not analyze any sort of strategy, but rather observe the patterns emerging from various initial configurations. There are often nice local or global equilibria; these are the treasures to discover.

As we increase the complexity of the rules, the complexity of the resulting patterns increases as well. (Although, rule 30 of the elementary automata is sufficiently complex, even exhibiting true mathematical chaos, I hardly believe that anyone studies elementary automata anymore)

So let’s increase the dimension of our grid to 2, and explore John Conway’s aptly named Game of Life.

What Life From Yonder Automaton Breaks!

For Life, our automaton has the following parameters: an infinite two-dimensional grid of cells, states that are either on or off, and some initial configuration of the cells called a seed. There are three transition rules:

  1. Any live cell with fewer than two or more than three living neighbors dies.
  2. Any dead cell with exactly three living neighbors becomes alive.
  3. In any other case, the cell remains as it was.

Originally formulated by John Conway around 1970, this game was originally just a mathematical curiosity. Before we go into too much detail in the mathematical discoveries which made this particular game famous, let’s write it and explore some of the patterns it creates.

Note: this is precisely the kind of mathematical object that delights mathematicians. One creates an ideal mathematical object in one’s own mind, gives it life (no pun intended), and soon the creation begins to speak back to its creator, exhibiting properties far surpassing its original conception. We will see this very process in the Game of Life.

The rules of Life are not particularly hard to implement. We did so in Mathematica, so that we may use its capability to easily produce animations. Here is the main workhorse of our implementation. We provide all of the code used here in a Mathematica notebook on this blog’s Google Code page.

(* We abbreviate 'nbhd' for neighborhood *)
getNbhd[A_, i_, j_] := A[[i - 1 ;; i + 1, j - 1 ;; j + 1]];

evaluateCell[A_, i_, j_] :=
  Module[{nbhd, cell = A[[i, j]], numNeighbors},

   (* no man's land edge strategy *)
   If[i == 1 || j == 1 || i == Length[A] || j == Length[A[[1]]],
    Return[0]];

   nbhd = getNbhd[A, i, j];
   numNeighbors = Apply[Plus, Flatten[nbhd]];

   If[cell == 1 && (numNeighbors - 1 < 2 || numNeighbors - 1 > 3),
    Return[0]];
   If[cell == 0 && numNeighbors == 3, Return[1]];
   Return[cell];
   ];

evaluateAll[A_] := Table[evaluateCell[A, i, j],
   {i, 1, Length[A]}, {j, 1, Length[A[[1]]]}];

This implementations creates a few significant limitations to our study of this system. First, we have a fixed array size instead of an infinite grid. This means we need some case to handle live cells reaching the edge of the system. Fortunately, at this introductory stage in our investigation we can ignore patterns which arise too close to the border of our array, recognizing that the edge strategy tampers with the evolution of the system. Hence, we adopt the no man’s land edge strategy, which simply allows no cell to be born on the border of our array. One interesting alternative is to have the edges wrap around, thus treating the square grid as the surface of a torus. For small grids, this strategy can actually tamper with our central patterns, but for a large fixed grid, it is a viable strategy.

Second, we do not optimize our array operations to take advantage of sparse matrices. Since most cells will usually be dead, we really only need to check the neighborhoods of live cells and dead cells which have at least one live neighbor. We could keep track of the positions of live cells in a hash set, checking only those and their immediate neighbors at each step. It would not take much to modify the above code to do this, but for brevity and pedantry we exclude it, leaving the optimization as an exercise to the reader.

Finally, to actually display this code we combine Mathematica’s ArrayPlot and NestList functions to achieve a list of frames, which we then animate:

makeFrames[A_, n_] := Map[
  ArrayPlot[#, Mesh -> True]&, NestList[evaluateAll, A, n]];

animate[frames_] := ListAnimate[frames, 8, ControlPlacement -> Top];

randomLife = makeFrames[RandomInteger[1, {20, 20}], 200];
animate[randomLife]

Throwing any mathematical thoughts we might have to the wind, we just run it! Here’s the results for our first try:

What a beauty. The initial chaos almost completely stabilizes after just a few iterations. We see that there exist stationary patterns, the 2×2 square in the bottom left and the space-invader in the top right. Finally, after the identity crisis in the bottom right flounders for a while, we get an oscillating pattern!

Now hold on, because we recognize that this oscillator (which we henceforth dub, the flame) is resting against the no man’s land. So it might not be genuine, and only oscillate because the edge allows it to. However, we notice that one of the patterns which precedes the flame is a 3×3 live square with a dead center. Let’s try putting this square by itself to see what happens. In order to do this, we have an extra few lines of code to transform a list of local coordinates to a pattern centered in a larger grid.

patternToGrid[pts_List, n_] :=
  With[{xOff = Floor[n/2] - Floor[Max[Map[#[[2]] &, pts]]/2],
        yOff = Floor[n/2] - Floor[Max[Map[#[[1]] &, pts]]/2]},
   SparseArray[Map[# + {yOff, xOff} -> 1 &, pts], {n, n}, 0]];
square = {{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 3},
  {3, 1}, {3, 2}, {3, 3}};

Combining the resulting two lines with the earlier code for animation, we produce the following pattern:

While we didn’t recover our coveted flame from before, we have at least verified that natural oscillators exist. It’s not hard to see that one of the four pieces above constitutes the smallest oscillator, for any oscillator requires at least three live cells in every generation, and this has exactly three in each generation. No less populated (static or moving) pattern could possibly exist indefinitely.

Before we return to our attempt to recreate the flame, let’s personify this animation. If we think of the original square as a densely packed community, we might tend to interpret this pattern as a migration. The packed population breaks up and migrates to form four separate communities, each of which is just the right size to sustain itself indefinitely. The astute reader may ask whether this is always the case: does every pattern dissipate into a stable pattern? Indeed, this was John Conway’s original question, and we will return to it in a moment.

For now, we notice that the original square preceding the flame grew until its side hit a wall. Now we realize that the wall was essential in its oscillation. So, let us use the symmetry in the pattern to artificially create a “wall” in the form of another origin square. After a bit of tweaking to get the spacing right (three cells separating the squares), we arrive at the following unexpected animation:

We admit, with four symmetrically oscillating flames, it looks more like a jellyfish than a fire. But while we meant to produce two flames, we ended up with four! Quite marvelous. Here is another beautiful reject, which we got by placing the two squares only one cell apart. Unfortunately, it evaporates rather quickly. We call it, the fleeting butterfly.

We refrain from experimenting with other perturbations of the two-square initial configuration for the sake of completing this post by the end of the year. If the reader happens to find an interesting pattern, he shouldn’t hesitate to post a comment!

Now, before returning to the stabilization question, we consider one more phenomenon: moving patterns. Consider the following initial configuration:

A few mundane calculations show that in four generations this pattern repeats itself, but a few cells to the south-east. This glider pattern will fly indefinitely to its demise in no man’s land, as we see below.

Awesome. And clearly, we can exploit the symmetry of this object to shoot the glider in all four directions. Let’s see what happens when they collide!

Well that was dumb. It’s probably too symmetric. We leave it as an exercise to the reader to slightly modify the initial position (given in the Mathematica notebook on this blog’s Google Code page) and witness the hopefully ensuing chaos.

Now you may have noticed that these designs are very pretty. Indeed, before the post intermission (there’s still loads more to explore), we will quickly investigate this idea.

Automata in Design

Using automata in design might seem rather far-fetched, and certainly would be difficult to implement (if not impossible) in an environment such as Photoshop or with CSS. But, recalling our post on Randomness in Design, it is only appropriate to show a real-world example of a design based on a cellular automaton (specifically, it seems to use something similar to rule 30 of the elementary automata). The prominent example at hand is the Conus seashell.

A Conus shell.

The Conus has cells which secrete pigment according to some unknown set of rules. That the process is a cellular automaton is stated but unsupported on Wikipedia. As unfortunate as that is, we may still appreciate that the final result looks like it was generated from a cellular automaton, and we can reproduce such designs with one. If I had more immediate access to a graphics library and had a bit more experience dealing with textures, I would gladly produce something. If at some point in the future I do get such experience, I would like to return to this topic and see what I can do. For the moment, however, we just admire the apparent connection.

A Tantalizing Peek

We have yet to breach the question of stabilization. In fact, though we started talking about models for computation, we haven’t actually computed anything besides pretty pictures yet! We implore the reader to have patience, and assert presciently that the question of stabilization comes first.

On one hand, we can prove that from any initial configuration Life always stabilizes, arriving at a state where cell population growth cannot continue. Alternatively, we could discover an initial configuration which causes unbounded population growth. The immature reader will notice that this mathematical object would not be very interesting if the former were the case, and so it is likely the latter. Indeed, without unbounded growth we wouldn’t be able to compute much! Before we actually find such a pattern, we realize that unbounded growth is possible in two different ways. First, a moving pattern (like the glider) may leave cells in its wake which do not disappear. Similarly, a stationary pattern may regularly emit moving patterns. Next time, we will give the canonical examples of such patterns, and show their use in turning Life into a model for computation. Finally, we have some additional ideas to spice Life up, but we will leave those as a surprise, defaulting to exclude them if they don’t pan out.

Until next time!

Tiling a Chessboard

Posted on by
3

Problem: Take a chessboard and cut off two opposite corners. Is it possible to completely tile the remaining board with 2-by-1 dominoes?

Is it possible to tile this board with 2-by-1 dominoes?

Solution: Notice that every domino covers exactly one white tile and one black tile. Counting up the colors, we have 32 white and 30 black. Hence, any tiling by 2-by-1 dominoes will leave two extra white squares unaccounted for. So no such tiling is possible.

Problem: Cut one corner off a chessboard. Is it possible to tile the remaining board with 3-by-1 dominoes?

Solution: Analyzing this problem with the normal chessboard admits no nice proof like before. Specifically, any tile covers either two white and one black tile, or two black tiles and one white tile, so a counting argument is much more difficult.

In a moment of divine inspiration, we realize that the standard coloring of the chessboard is arbitrary. We decide to repaint our board as follows:

Our new coloring makes the proof trivial.

Clearly, any 3-by-1 domino covers exactly one black square. Counting up the colors once more, we see that there are 22 black squares. Since there are 63 squares in all, we must have 21 3-by-1 dominoes, each covering one black square. This leaves one black square unaccounted for, and so no such tiling is possible.

Notice that if we omit the word “chessboard” and just give a colorless grid, this “divine inspiration” would certainly be much more miraculous.

Furthermore, this gives a nice method of proof for any n-by-1 dominoes on an m \times m board, where n < m, and we cut off a certain number of squares. Just look for a useful coloring, such that each domino covers a helpful number of squares of a certain color.

Teaching Mathematics – Graph Theory

Posted on by
21
Note: this post is entirely about mathematics, but I plan to follow it up with posts on teaching and learning experiences in computer science, comparing them with mathematics in turn.

Community Service

Mathematics is supposed to be a process of discovery. Definitions, propositions, and methods of proof don’t come from nowhere, although after the fact (when presented in a textbook) they often seem to. As opposed to a textbook, real maths is highly non-linear. It took mathematicians quite a lot of fuss to come up with the quadratic formula, and even simple geometric conjectures were for the longest time the subject of hot debate.

I feel like if I’m going to be a teacher worth anyone’s time, I have to let students in on the secret that questions guide mathematics. This urge to teach is especially strong at the high school level, where it is generally agreed that “mathematics education” is a farce.

And so, as the only community service I do regularly (and too seldom, at that), I go to local high schools and middle schools and give “lectures” on mathematics. Though I have ideas for a lot of lectures I could give, and wish I had more than just an hour to work with a class, I usually stick to a particularly intuitive lecture on graph theory. I will reproduce one such lecture here, picking out the best of the student’s innovation that I can remember. Regular text paraphrases what I speak and what is written on the board, quoted text is student response, and square brackets [ ] contain commentary.

As a note to the reader, this will serve as a very detailed introduction to Graph Theory, as opposed to the terse primers I’ve been providing thus far.

Two Puzzles

Today we are going to do three things:

  1. Think about some puzzles,
  2. Do some mathematics, and
  3. Use math to change the world.

So here are the two puzzles:

First, [after asking a student to provide her name, I invent a city name based on it] imagine you’re the mayor of Erintown. In Erintown there are seven very old and beautiful bridges, and as mayor you’d like to promote their prominence in tourism. To do this, you wish to provide a route through the city which crosses every bridge exactly once, never visiting the same bridge twice. The seven bridges are arranged as follows [a much more detailed picture than what one draws on a white board]:

Bridges of Erintown

[The informed reader will recognize this immediately as the Seven Bridges of Königsberg problem, which historically founded graph theory, and was solved by Leonard Euler in the 18th century. But honestly, what (potentially immature) high school student is interested in a problem with a name like that? As we will see throughout the post, personalization (and the engagement inherent in it) is essential to the success of the lecture.]

Unfortunately, after a few tries you are unable to find a route which works. Hence the first puzzle is: does such a route exist? If not, how can we prove it?

[At this point, we clarify some rules of the puzzle. High school students are adept at producing loopholes, and rightfully they enjoy doing so. So typically we talk about swimming, aircraft, traversing bridges halfway, teleportation, etc., banishing each possibility as it comes up. This is an important step, because in part the whole point of the mathematical formulation of this problem is to eliminate these possibilities from consideration. We very much need to rephrase this problem entirely in our minds to extract the aspects we care about and discard the rest. Even when in real life swimming is an option, our mathematical formulation must ignore swimming, and hence we must design it appropriately (and hopefully elegantly).]

For the second problem, say you’re at a party of one hundred people. At this party, someone decides to start tallying up who at the party is friends with whomelse (he’s one of those guys, a drama king). He shows his list to you, and you notice that there are two people at the party who have the same number of friends at the party. The thought occurs to you that this will always be the case, no matter how many people attend and who is friends with whom.

So the second puzzle is: at a party of n people, must it be true that there exist two people with the same number of friends at the party?

[Again, we have the requisite loopholes, like whether there are stalkers at the party, and whether you are friends with yourself. The former drives us to distinguish that we want "symmetric" friendships, i.e. if you are friends with someone then they are friends with you. The former translates to undirected edges later, while the latter hints at simple graphs. Both are usually made clear by appealing to the rules of Facebook friendship. Finally, we might make the clarification that there are at least two people at the party, in order to prevent a discussion of vacuously true statements.]

Now take five minutes and try to solve these problems, by yourself, with a friend, or with a group, however you feel most comfortable tackling a problem. [They never get very far, but at least once I've encountered a student who knew of the Seven Bridges problem ahead of time, spoiling much of the fun and thoroughly confusing the rest of the class.]

New Mathematics

[After five to ten minutes pass and the group is quiet again] So, who thinks they’ve solved the first problem? [hands raise, most proclaiming impossibility; those who try to explain their reasoning mostly resign to awkward case-checking or saying they just couldn't find one that worked] And what about the second? [nobody raises a hand, most enjoy thinking about the bridges problem because it is very visual. In classrooms blessed with a SmartBoard, I can have a number of them come up to the front and attempt to draw a route with their finger (and hitting undo when they invariably fail, so that I don't have to redraw the diagram every time).]

So, it appears that we haven’t come up with a good solution for either problem. Now a mathematician might say at this point, “screw this, I’m going to make up my own math to solve it!” And that’s what we’re going to try to do.

The first step is to compare the problems: what is similar and what is different? [Discussion ensues, but often times the students don't understand what I'm looking for, and usually the problem is that they're trying to come up with the "correct" answer instead of making observations; it is a curse of the schooling paradigm. Additional leading questions include:] what are the subjects of our study? How are they related? does it matter where you walk on a landmass between visiting bridges? Does it matter where the people in the party are standing? [And the most important question] Is there a better way to draw these problems?

[Soon enough students make the right observations, that our drawings of the two problems are almost identical!] It doesn’t actually matter how big or where the landmasses are, since all we care about is the order in which we cross bridges. Hence we can compress the landmasses down to dots! Additionally, we can just draw people as dots, and arrange them in any way we wish. Then, the bridges and friendships become lines connecting the dots. This yields a much nicer picture for the bridges problem, and a similar one for the party problem.

Our new form of the seven bridges problem.

By writing the problem this way, we have distilled out the relevant facts: all we really care about is the structure of how these things are connected. Unfortunately we have one problem: we don’t have names for these things! We certainly don’t want to call them bridges and landmasses, or people and friendships, because we want the picture to apply to both problems at the same time.

So to start, what would we call the picture as a whole? Appeal to your imagination about what it looks like. [Though this part is sometimes difficult, especially at the middle-school level, eventually someone calls out something truly clever] “How about a constellation?”

I like that! So here we are, this is our invention:

Constellation Theory

What are we going to call the individual dots? “Stars!” And what about the lines connecting them? “How about…connections?” Okay. So here is our first definition:

Definition: A constellation has three parts:

  1. A set of stars S [we just accept the intuitive definition of a set without issue],
  2. A set of connections C,
  3. A function f: C \to S \times S which accepts a connection and tells us which two stars it is connected to.

[Before the third, I ask the class whether the first two alone are enough. If I get nods, I draw a random collection of dots and lines, with the lines not at all connected to the dots, and they see we need some statement of incidence.]

Don’t be afraid of the third part (even if you don’t know what a function is), it’s just a formality that uses other (well-established) maths to make our definition consistent. Math can sometimes be a notational nightmare, but all this means is that we can take any connection and easily say which two stars it connects. Since we will always draw constellations as a picture, we can just use the picture as our “function.”

Now can someone remind me again what we were looking for in the bridges problem? Right, a route through the city that hits every bridge exactly once. First we need to translate a “route” into our language of constellations. Does anyone have a good name? [After a few generic suggestions like "trail," "path," and "route," we settle on the imaginative "waltz".] This gives our second definition:

Definition: A waltz through a constellation (S,C,f) is a list of alternating stars and connections, which we label (s_1, c_1, s_2, c_2, \dots, s_{n-1}, c_{n-1}, s_n), where the ith connection c_i is connected to its neighboring stars in the list s_i, s_{i+1}. In terms of our function, f(c_i) = (s_i,s_{i+1}) for each i=1 \dots n-1.

This is just a way to write out on paper what the waltz is. [I label the seven bridges picture and provide an example.] You who suggested the name “waltz,” what is your name? “Phil.” What is your last name, Phil? “Osman.” Great! Now we have another definition:

Definition: An Osmannian waltz through a constellation is a waltz which uses each connection in C exactly once.

[A few giggles resound when they realize I'm incorporating the student's name into the definition.] Now can somebody rephrase the original problem in terms of constellation theory? “We want to find out if there is an Osmannian waltz in that particular constellation.” Excellent!

Now let’s turn our attention to the party problem. Can someone remind me what we were trying to find out about parties? “Whether there are two people who have the same number of friends.” Right, whether that has to be the case for any party. Now in terms of constellations, what is that? “The number of connections at each star.” Great. What’s your name? “Olivia.” Olivia, what’s your last name? “Bisel.” Okay. Here’s another definition:

Definition: The Bisel-degree of a star is the number of connections in C connected to it.

Now there are a couple of other details we have to consider. Specifically, in a general constellation we never ruled out multiple connections connecting the same two stars. And we never said a connection can’t go from a star to itself. But we must rule these out to make a sensible party problem. So we will call a constellation which rules out doubled connections and self-connections simple. [For the sake of time, we just provide a name, and it's not that imaginative of a property anyway.]

So can someone translate the party problem into the language of simple constellations? “It’s whether every simple constellation has to have two stars with equal Bisel-degree.” Wonderful!

Now that we have a working language, let’s take another ten minutes to try to solve the problems. But this time, you aren’t allowed to use “bridges,” “landmasses,” “people,” or “friendships” anymore, you have to use the terms we invented. [The students still don't get far, especially on the bridges problem, but every now and then a student solves the party problem. As they work, I give subtle hints, like, "what happens if you add extra connections or remove some? Does it work then? What aspect of the intrinsic structure have you altered by doing this? Try lots of examples!"]

[After bringing the class back together] So who thinks they’ve solved the first problem? [a few hands raise] “I think it has something to do with whether the Bisel-degree is even or odd.” Interesting. Did you get much further than that? “No…” Okay. What about the party problem? “I think I have it. So if everybody had a different number of friends, then one person would have to have no friends and someone would have to be everyone’s friend, but that can’t happen.”

Did everyone hear that? [I reiterate on the board in detail, explaining the idea behind proof by contradiction, and drawing a picture of the resulting constellation.] This is a very elegant proof. And if anyone can come up with a solid proof of the bridge problem, I have no doubt your teacher would give ample extra credit.

Changing the World

Now, for the mathematician this is enough. This new mathematical object, a constellation, is full of wonderful patterns that we could spend our entire lives thinking about (and many have done just this). However, it’s probably true that most of you aren’t going to become mathematicians. So let’s try to think of things in the real world that we can model as constellations. Any ideas?

[The students suggest a variety of different (and usually complex) ideas, including trade between nation-states, distributions of power among people, and the structure of galaxies. For each example, I usually have to verbally augment our representation of a graph (for the sake of time), bringing constellations with numerically labeled edges or directed connections. Since I always tell the students to "think bigger," they inevitably say "galaxies," and I have to explain why that doesn't work, because the whole point of constellations (the mathematical ones) is that the relative sizes and positions of the stars don't matter, whereas at the galactic level that completely determines the connection (which is invariably gravitational pull). We apologize for the terminological confusion.

[Eventually, we might get to the cases of modelling all roads and intersections, after which I claim that is exactly how Google Maps (and all other mapping/directions software) works. Sometimes they take the "friendship" hint and recognize Facebook as a constellation, and we often begin to talk about friend suggestions and degrees of separation. Finally, (and this is the main example I wish to work toward), we model the entire internet as a constellation, with directed connections corresponding to links between web sites. Then I talk about how Google based their company on the soundness of this particular model, making 25 billion dollars and changing the world. We do not discuss software representations of constellations, nor algorithms to extract data from them (this would be a whole course worth of information, at least).

[Depending on the amount of remaining time, I either provide the proof of the party problem, if the students didn't solve it on their own, or continue with anecdotes about Google's PageRank and its pitfalls. I don't usually give the proof of the seven bridges problem, but if pressed a short sketch of the proof is easy. More often than not, the bell ends my lecture before I'm ready anyway.]

Reflections

This lecture has generally been successful among students for three obvious reasons.

First, it is exploratory. People intrinsically like puzzles. In sharp contrast to the typical high-school style of memorization and repetition, the students drive the method! Of course, they do so in a discordant, chaotic way, but this can just as easily be said of the same students English essays or history papers. They simply have less practice with this particular kind of argument, and so they are expectantly less coherent.

Unfortunately the shortage of time forces me to guide them much more directly than I should. The amount of content we cover in an hour lecture really deserves a week of discussion, formulation and reformulation, and debate, with as little intervention as possible. I would absolutely love a chance to work with them for an extended period of time to see how it plays out. And of course, it would be much less linear, and we’d explore the questions of the students interest. However, I do fear that they might prefer a more rigid structure, being used to the humdrum of their education heretofore.

Second, the lecture is personal. I don’t have them make up names for nothing. Mathematics is a generative subject. The students not only need to see that, but also experience the process of taking an intuitive idea and nailing it down (often with more logical rigor than anything they’ve experienced in math to date). Inventing a name for the resulting definition secures the idea in their memory, and accentuates the notion that this thing is unique to their special classroom community. Since they don’t yet have the practice or motivation to make their own proofs (the ultimate mathematical self-expression), this is the next best thing. But most of all, naming the concepts is fun!

So I frame the problems in their imaginations, not history. I give them no false pretense for why we are doing this. The puzzle is a means to its own end, and we only later discover that our work is applicable. For a large portion of mathematical history, one might argue, this is how progress worked. Certainly Leonhard Euler anticipated neither Facebook’s social graph nor Google Maps in the mid 18th century. This is the easiest way to impress upon them that many different things have similar patterns in their structure, so even studying a trivial thing can be very enlightening. The puzzles really are worth doing for their own sake.

Compare this to being given the definitions and propositions in the established mathematical language. To an untrained, uninterested student, this is not only confusing, but boring beyond belief! They don’t have the prerequisite intuition for why the definition is needed, and so they are left mindlessly following along at best, and dozing off at worst.

Third, the lecture is a conversation. While ultimately I have to dish out judgement on their suggestions (this name doesn’t make sense, that idea doesn’t pan out for this reason, etc.), I make an honest effort to explain why and reiterate our goals, showing the discrepancy, and then requesting another suggestion. Unfortunately that keeps it as a bona-fide lecture, but if I had a week, the students would ideally critique each other’s work.

At the same time, I do (to some bounded level) entertain their admittedly immature suggestions. When they keep insisting swimming or long jumping across the river, I usually quip with something like, “Pretend the tourist is your grandmother. Would she swim that far?” If not to just deny their question, this reminds them that the original puzzle was meant for all tourists, including the “weakest link” as far as swimming goes. Even when they riposte with “Yes. My grandmother is a body-builder,” I dismiss it with a smirk and a wave of the hand, perhaps sarcastically saying, “Okay.” I feel that such a level of humorous improvisation is necessary, both to keep the students on their toes and to mirror their creativity with my own, thus fueling it and directing it toward the mathematics.

Of course, I might not always spend so much time with such verbal fencing. But for a first exposure to real mathematics, and to establish my role in part as an equal but more so as an obstacle, I deem it necessary. I need to be the out-witter, so that when they exhaust their loopholes, they have no choice but to beat me by solving the problem. Given a lengthier period of time (taking into consideration the students’ maturity level), I would gradually transition to a more pointed focus on the problems, and make it clear when silliness is appropriate. With luck and planning, interest in the problems would compensate for a perhaps dull state of order.

If I Had a Class

Sometimes I entertain the thought that I might end up teaching high school, and that with the providence of the school’s administration I could have my own elective course called “Real Math,” or something perhaps more enticing to the skeptical student (“Math Soup for the Teenage Soul”? “Math as Art”? “Mathematical Composition”?).

This course would start with a week of lectures similar to the one detailed above, and then alternate each week between some objective curricula (likely the basics of set theory and methods of proof) and an exploratory topic. The latter might likely start off as more explorations into graph theory (I’d debate whether to replace their invented names with the established language) and then continue into other basic topics. During the exploratory week, students would present and critique arguments in front of the class. The problems come from a list of problems given at the beginning of the week or the students’ own minds. And though I’d prefer most of the problems being the students’ own, it’s likely that initially most of the problems would come from me. Partial solutions, interesting observations, and even the process of an incorrect solution would all be presentation-worthy.

And finally, perhaps the only original idea I would have for this course, the students would each keep a journal. It would double as a notebook for their own investigation of the material brought up during exploratory weeks and a portfolio to turn in for grading. Its grading would be largely subjective, but the students would have to display some level of effort in terms of the depth to which they explore a particular problem and the number of problems attempted. As the year would progress, I would get to know the students’ ability levels and work tendencies much more clearly, and would thus have a more refined and personalized grading method.

Of course, not long after building up these ideas in my imagination, I came across the essay A Mathematician’s Lament, in which Paul Lockhart mercilessly (and rightfully) berates the current state of mathematics education in America. He more or less advocates the kind of teaching style I propose, and then argues that today’s mathematics teachers cannot play such a role for a lack of their own love for mathematics, and would not want to, because teaching this way is extremely hard! It requires much more work than the average teacher is paid to do.

After repeating the lecture above for five classes of students in the course of a single day, I certainly agree with Lockhart on the difficulty of this teaching method. Though I feel I have a natural knack for presentation and engagement, to handle the standard number of students per day expected of American teachers is quite tiring (and I am a lively and strapping young lad!). That being said, I consider it my duty to take every opportunity to do a lecture, while it provides me both with intellectual joy and the satisfaction of beneficence.