A Recursively Enumerable Grammar for Binary Addition

As part of my 2nd semester CS course, I introduce students to the Chomsky hierarchy of grammars. We only go into details about regular grammars and the main learning objective is regular expressions, but I talk about context-free, context-sensitive, and recursively enumerable as well. Part of the reason is to show that there are limits to what you can do with grammars at each level, at least up to recursively enumerable, RE. I tell them that RE grammars are Turing complete, so they can compute anything that any computer could. I often use the example of a factorial because it is a fairly simple function that they are used to coding that doesn't seem at all like it would be doable with grammars.

This year I had a student ask about that on the questions they give me at the end of each class. He said that he couldn't see how a grammar could calculate factorial. I went to be that night trying to think of how to illustrate that a grammar could do math. I knew that I wasn't likely to write factorial, but I figured that if I started with addition might might be enough to show that you can build more complex math. The next question was how to represent that numbers. Addition in strings that use a unary format is simple, so I decided to go to binary. As an assignment in the 1st semester class I have students implement addition, multiplication, and exponentiation using only recursion, successor, and predecessor. I decided to take the approach here that I would do for addition there. We say that a+b = (a+1)+(b-1) and have a base case when b is 0. It turns out that you can implement successor and predecessor in binary strings fairly easily.

I put my code for doing this in a GitHub Gist that you can see at the link below. There are 14 productions in the grammar. In addition to the '0', '1', and '+' that I need to represent binary addition, I bracket the numbers with 'N' so that I can tell when I am at the beginning or end of a number. There are a few productions at the end that are used to "clean up" at the end so we get a single number in a string. There are only three productions that are used to create the successor functionality, which is done by putting in a 'S' character. The harder part is getting predecessor because the 'P' character needs to be inserted at the right end of the second number, and when it is done, we have to have that information sent back to the plus sign to say that the current operation is done. So while there are only two productions labeled as predecessor, the left and right message productions are also part of making the predecessor work.

Gist of the Code To see how this works, I ran it and entered the numbers 5 and 6. You can see the output of that here. The first line shows that we are adding 5 and 6. Each line below that is the application of a single production. The ones that don't have a ' after the plus sign are completed steps in the addition algorithm. The last line is printing the final result, which you can see is 11 in binary.

N101N+N110N
N101SN+'NL110N
N101SN+'N1L10N
N10S0N+'N1L10N
N10S0N+'N11L0N
N10S0N+'N110LN
N10S0N+'N110PN
N110N+'N110PN
N110N+'N11P1N
N110N+'N1R01N
N110N+'NR101N
N110N+N101N
N110SN+'NL101N
N110SN+'N1L01N
N111N+'N1L01N
N111N+'N10L1N
N111N+'N101LN
N111N+'N101PN
N111N+'N10R0N
N111N+'N1R00N
N111N+'NR100N
N111N+N100N
N111SN+'NL100N
N111SN+'N1L00N
N111SN+'N10L0N
N11S0N+'N10L0N
N11S0N+'N100LN
N1S00N+'N100LN
N1S00N+'N100PN
NS000N+'N100PN
NS000N+'N10P1N
N1000N+'N10P1N
N1000N+'N1P11N
N1000N+'NR011N
N1000N+N011N
N1000N+N11N
N1000SN+'NL11N
N1000SN+'N1L1N
N1001N+'N1L1N
N1001N+'N11LN
N1001N+'N11PN
N1001N+'N1R0N
N1001N+'NR10N
N1001N+N10N
N1001SN+'NL10N
N1001SN+'N1L0N
N1001SN+'N10LN
N1001SN+'N10PN
N100S0N+'N10PN
N100S0N+'N1P1N
N100S0N+'NR01N
N1010N+'NR01N
N1010N+N01N
N1010N+N1N
N1010SN+'NL1N
N1011N+'NL1N
N1011N+'N1LN
N1011N+'N1PN
N1011N+'NR0N
N1011N+N0N
N1011N+NN
N1011N
N1011N

Straw at Saturn's Keeler Gap

The term "straw", in relation to planetary rings, was coined during the orbital insertion of Cassini at Saturn when images like the following, available from the JPL site, were taken with high resolution because the probe was so close to Saturn and the rings. The "ripples" that run through this image diagonally are density waves. In the bottom left corner there is a large density wave that has course structures in it. Someone in the room when these images came down thought that they looked like straw, and the name stuck.

Just a bit before Cassini arrived at Saturn, I had been doing simulations of the Encke gap that showed extremely large self-gravity wakes forming near the gap edge. These gravity wakes form as the Pan wakes damp out downstream from the moon. They were described in an Icarus paper (Web supplement with movies). The figure below comes from that paper, and the top four panels in the right column show some frames where these oversized wakes appeared in four different simulations. Since that time, "straw" type features have been seen at the edge of the B ring as well, but I am not aware of any observations of them at the Encke gap. Perhaps the end of life mission will manage to fix that with higher resolution images of the rings as Cassini dips inside the D ring.

It is natural for gravity wakes to form in these simulations. The frames on the left column show the situation early in the simulation when the clumping is from normal sized gravity wakes. The surface density of the simulations varies by row, and generally increases from the bottom row to the top. The size of the gravity wakes is a direct function of the surface density. Notice that the size of the clumps is much larger at the inner edge of the right column cells than it is anywhere in the left column.

This last year, Nicole Albers at the Laboratory for Atmospheric and Space Physics (LASP) found some interesting features in Cassini UVIS occultations of the Keeler gap region. These features are basically holes in the ring material roughly a kilometer in radial extent that are located just a bit inside of the edge of the gap itself. So you have the gap, with effectively no material, followed by a few kilometers of ring material, followed by a kilometer or so of no material, then back to the normal rings. These holes are found in the region a few degrees downstream from Daphnis, the moon that maintains the Keeler gap. (I hope to do a systematic search for these things myself using public data from the rings PDS node. I'll put up another blog post on that so I can make figures without infringing on what Nicole has done.) Some of these holes also appeared around the Encke gap.

I've been simulating the Keeler gap for a while, so I was wondering if I might see something similar in simulations. The problem was that I needed to do a big simulation to get to the region where these were seen by Cassini. My hypothesis was that straw might form near the edge of the Keeler gap, and the regions between those oversized gravity wakes would be cleared out enough to appear as a hole. To test this hypothesis, I have been running a very large simulation of the Keeler gap involving 80 million particles with collisions and particle self-gravity. At this time, the simulation has been running for about three months, and it is a bit over half way done. The animation below shows a large-scale view of the simulation. It is using a gray scale to show the geometric optical depth. That is just a ratio of how much area the particles in a small region cover divided by the total area of that small region. This isn't exactly what one would see looking at this material in the rings, but it is a reasonable approximation.

There is a lot going on in this plot. The coordinate system is centered on the average position of Daphnis. The particles drift from right to left with a drift speed that is proportional to their radial distance from the moon. When they go past the moon, the gravity of the moon pulls them onto eccentric orbits. This leads to the wavy structures that are visible. Daphnis has a fairly eccentric orbit relative to the width of the gap, so the magnitude of how much it pulls on the particles varies with time. The fact that Daphnis has a non-negligible eccentricity and inclination makes this part of the rings difficult to simulate. I'll plan to write a different post describing how these simulations are done, compared to the Encke gap where those values can be set to zero without losing too much information about the system. The combination of the wavy motion and the shear that results from more distance particles drifting faster leads to compression regions that we call moon wakes. Since Daphnis is the moon, I will sometimes call them Daphnis wakes. The collisions in these wakes dissipate the forced eccentricity caused by the gravitational pull of the moon, so the waviness decreases as you go to the left after passing by the moon.

The first question is, does straw form? If we believe from the Encke gap simulations that straw is just long, stringy gravity wakes that have grown over-large due to systematic motions of the population of particles, then this is equivalent to asking if large gravity wakes form near the edge of the Keeler gap in this simulation. The answer to this question turns out to be yes. It took 12 orbits downstream from the moon for them to begin to appear, but the figure below, which shows a region ~16 orbits after passing the moon, clearly shows that there are large gravity wakes. Going back to the figure above, if you look at the last few wake peaks, those just past 2000 km downstream from the moon, on the inner edge, there is coarse graininess that was not present in the earlier wakes. This appears to be what those large wakes manifest as in the binned data.

This simulation still needs to go another 10 orbits or so further downstream before it gets to the point where the first "holes" have been seen in occultations. That should take about another two months gives the current speed the simulation is running at. At this point we can say that straw definitely forms near the edge of the Keeler gap, but it is very unclear if the straw can cause the observed holes.