More Laws of Form

I mentioned earlier that I was taking a fresh look at G Spencer Brown's Laws of Form because I found a document by Mark W Hopkins that redescribes the content of this book in more traditional mathematical notation.

Hopkins starts by converting Brown's spatial notation to a linear notation using 1 to represent the empty space and () to represent distinction. We have the usual transformation rules:

(()) -> 1 and ()() -> ()()

He places this in the framework of a transformational category which is esentially a category in which the objects are expressions and the arrows are applications of transformation rules. It's pretty obvious that the above system is isomorphic to the usual boolean algebra (0,1,\/,/\,~) with

1 -> 0
() -> 1
(a) -> ~a
a b -> a \/ b

Not much of interest there.

Brown also describes expressions with feedback. But these are nothing other than sequential logic circuits, ie. circuits where the state at time t+1 is a boolean function of the state at time t. Hopkins formalises these as simple finite state automata. Nothing new there either. I certainly don't see any advantage over a language like Verilog which is designed for sequential logic.

Now, suppose A= 1. Then ((A)A)->1. Similarly, if A=() then ((A)A)->1. So we have the rule ((A)A)->1. So if we extend the language of Laws of Form to include variables we'd like to be able to deduce ((A)A)->1 within the language. We certainly can't deduce it with the rules introduced above. So we must introduce some new transformation rules. One of them is ((A)A)->1. Mark Hopkins describes two such systems and shows how they are complete in the sense that we can make all of the deductions we expect to be able to make in the presence of variables. This is vaguely interesting but really we're just learning how to manipulate boolean expressions, nothing profound.

Unfortunately I don't have a copy of Laws of Form to hand so I can't check Hopkins description against Brown's. My last reading of the book certainly didn't make as much sense as Hopkins explanation so I'm anxious to compare. But if this really is the content of Laws of Form then there really isn't much to it. However, I didn't see any discussion of imaginary logic values in Hopkins' document. It may be that these values are simply oscillating states in sequential logic circuits. I really must obtain the book again.

Anyway, it's fun to explore the Laws of Form web site. Apparently a group at the now defunct Interval Research company was trying to make use of Laws of Form in reconfigurable computing. I also came across this. This last document claims to simplify mathematics but all it seems to do so introduce a cumbersome notation. I'd rather use lambda calculus or combinatory logic.

Update: I just found this published critique of Laws of Form.

Primer

At the weekend I watched the movie Primer. An interesting time travel story made on a budget of $7,000. I mention it because unlike movies like Back to the Future it seems to have a certain rigour. There are no people slowly fading out as characters fail to achieve their goals in another 'timeline' and apparently no people remembering things that aren't in their own histories.

Or at least I think this is the case. Unfortunately the rigour of the movie might be its downfall - it makes no concessions to the audience to make the story easy to follow. When we see one of the characters in a scene it's not easy to tell which of the scenes, either earlier or later in the movie, are in that characters history at that time. And of course by time a potential candidate to be in his history does appear later in the film, we no longer remember the details of the earlier scene. Memento was a straightforward film shown in reverse. (And also inconsistent, as if reversing the story was too much for the scriptwriter to handle.) Primer forks, loops and twists like no movie I've ever seen. As a topological space it has a high genus.

Unfortunately, it was too much of a challenge for me. I really have no idea what happened, although there appears to be an interesting sequence where one of the characters repeatedly travels back in time, each time making slight modifications to his actions, in an attempt to iteratively optimise an outcome. But what that outcome was, and why he tried to achieve it, is beyond me. I guess I'll have to watch it a few more times. It's very rare that a movie has provided as much of an intellectual challenge.

And one point in its favour - not only was the technobabble not excruciatingly bad, it was even believable in places. Primer is one of the few truly Science Fiction movies I have seen.

Laws of Form

Laws of Form is a book published by G Spencer Brown, I think in around 1972. It starts off pretty straightforwardly by introducing a form of boolean algebra using one symbol a bit like an L rotated through 180 degrees. The key feature of this symbol is that it makes a distinction between an inside and an outside so we can replace it with parentheses. If I write (A) then A is inside the parentheses and in ()A the A is outside. This distinction between inside and outside is in fact what he names his symbol, a 'distinction'.

We can write a distinction on its own as (). Now we can introduce some simple rules. A distinction inside a distinction isnothing. Ie. (()) =. I haven't left out the right hand side. As it might be confusing I'll use the symbol 1 to represent a blank space. So (()) = 1 and trivially (1)=() and ()1=() as 1 is just another way of not writing anything at all. Brown also introduces the rule ()() = (). These rules now have an interpretation in boolean algebra:

1 -> false
() -> true
(a) -> not a
a b -> a or b

This is a nice notation for boolean algebra and may originally have been invented by C S Peirce.

But after a few pages I find Laws of Form to be completely incomprehensible. Brown suddenly makes a leap from simple Boolean algebra to completely bizarre operations that result in the description of some kind of binary sequential circuits related to solutions to recurrent equations. I more or less dismissed Brown as a crackpot.

Curiously, however, Louis H Kauffman, a well known Knot Theorist among other things, has taken to Laws of Form with zeal. He sees a commonality with the types of diagrams that he uses for Knot Theory. But he goes further and sees connections with the properties of spacetime. Kauffman has a Paper here as well as some material in his great book Knots and Physics. Still, when you look closely the comments are all pretty vague and really don't go beyond the simple boolean algebra that Brown discusses towards the beginning of Laws of Form.

So even though there's at least one reputable mathematician who's interested in his work he still seemed like a crackpot. Take a look at USENET discussions about the book and you'll see endless quasi-mystical discussions about the book with very little meat - all tending to confirm the crackpot hypothesis. And if you wanted any kind of confirmation that he was a crackpot you just have to make note of the fact that a conference on Laws of Form was held at Esalen.

But then I came across Mark W Hopkins' USNET posts on the subject, in particular here. For the first time in my knowledge a mathematician has attempted to redescribe the later parts of Laws of Form (what Hopkins calls LOF2 and LOF3) in a non-trivial way. I haven't read the posts yet but judging by the quality of many of his other posts it should be interesting.

My question now is this: who is Mark W Hopkins. I've learned a ton of stuff about finite state machines and regular languages from his posts but his web presence is pretty ephemeral and seems to end a few years ago.

I'm a descendant of Bessel and Gauss

Via Artin in fact.

No, we don't share any genes, but instead I have inherited their memes. See here for details.

Dual Photography Part II

It worked. The following playing card was successfully read even though it wasn't in the line ofsight of any light sensor.




Rather than write anything here I'll just refer you to the article on my home page.

I now have a couple of mirrors mounted on steppers so I may see if it's possible to get better results with these than with servos.

Derivatives of Regular Expressions

This paper from 1964 has an interesting algorithm for converting regular expressions into finite state automata. I've just figured out what it's all about.

The idea is that if you have a regular expression over some alphabet of symbols you can differentiate it with respect to a symbol. Basically, if R is a regular expression then dR/da is a regular expression that matches all of the strings that match R when prepended with an a. For example da/da={1} (where 1 = empty string), db/da = 0 (where 0 = the empty set and b!=a), d(a*)/da = a* and d(abc)/da = bc. You can write down a complete set of rules for differentiating regular expressions that are analogous to the Leibniz rules for differentiation.

Now here's the first crucial point: Given a regular epxression, R, you can compute repeated derivatives in an infinite number of ways by repeatedly differentiating with respect to different symbols. Many of these expressions turn out to match the same sets of strings, and when they do they are said to be equivalent. So we may form equivalences classes of derivatives. It turns out that the set of equivalent classes is finite.

Here's the next crucial point: differentiating an element of one of these classes with respect to a symbol gives you a representative of another class. So make a directed graph whose vertices are these classes and whose edges are labelled by symbols. We draw an edge from [S] to [T], with label a, if dS/da = T. This graph is none other than the graph of the finite state automaton to recognise matches with R.

The catch is recognising when [S]=[T], ie. when S and T match the same strings. But if we're building a machine we don't have to get this exactly right. We can use sloppy methods to try to identify [S]=[T]. It turns out that it's easy to produce an algorithm that doesn't guarantee to spot when they recognise the same strings, but that gives us a weaker equivalence which still results in a finite number of classes. This might give us a suboptimal automaton, but it still works.

This approach also leads to an elegant way to extend regular expressions with some other useful operations such as 'interleave' and 'complement'. ('interleave' should be familiar to anyone who's read Hoare's book on Communicating Sequential Processes.)

For further information see JH Conway's book on regular machines. Mark Hopkins posted an implementation in C on comp.compilers in 1994. Mark Hopkins also made this post to comp.theory which fills in the details I left out above. (Search USENET for postings by Mark Hopkins, they are frequently very insightful.)

Fermat's Last Theorem 'Disproved'

This story from the Manila Times is a good illustration, in a mathematical context, of how sarcasm doesn't travel well, especially between cultures.

For those who aren't getting it...Wiles's response isn't 100% serious.

Dual Photography Part I

At the end of this paper is an interesting parlour trick. The authors demonstrate a method of reconstructing what is on the face of a card even though the only light that reaches the camera from the face travels via reflection in a diffuse surface, a page of a book. The first thing that came to my mind was that the page of the book has a highly blurred reflection of the card on it and that what must be required is a form of deconvolution. But a moment's reflection suggests that would be really hard. However, after looking at a few comments on Slashdot claiming that the paper was trivial, I realised that this trick is easy! Even better, it can be done if you replace the camera with a photocell and requires only a few lines of code to process the data. (Note that the rest of the paper isn't quite as trivial!)

The idea in the paper is that a light source (and its characteristics) and a light sensor (and its characteristics) can be swapped and the sensor will record the same amount of light falling onto it. For example, suppose we have a scene illuminated by a laser, which produces a tight beam, and it is viewed by a photocell, which collects light over a wide area. Then the sensor responds as if it collected light from the same narrow beam originating from a lamp spreading light over the same wide area. And this is how we perform the card trick. We point a photocell at the page of the book and rasterize the card using a laser. As the laser scans, the photocell registers exactly as if it were a tightly focussed photocell scanning the card. There's nothing clever here - point a laser at a white object in a dark room and the rest of the room will be illuminated more than if you pointed the laser at a black object.

But I don't want to just claim this is easy. I intend to do it. So far I have hooked up a photocell to an analogue to digital converter on a microcontroller and I've tried 'rasterising' objects by hand. It's pretty clear from the microcontroller data that the sensor is correctly distinguishing light and dark regions on an object completely out of view. So it looks like my dual camera (cocamera?) should work. The only thing left now is to mount the laser on a servo-driven pan-tilt head so I can rasterise automatically. If it all works out I'll have pictures in Part II some time in the next couple of weeks.

Note that the dual in dual photography is the vector space dual.

Diagram Chasing

A few months ago I was looking at a catalogue from a flooring company called FLOR. I spotted that a couple of the pictures of rooms had mathematics on the wall. And not just basic material. One had a commutative diagram with what looked like a piece of a long exact sequence in it. I decided that I had to understand how such a thing could have appeared in a catalogue selling floor tiles.

After a bit of poking around I eventually found the pictures on the company web site, but no clue why they were there. I then posted to sci.math and was eventually led to this article from the Notices of the AMS. It turns out that the artist Bernar Venet specialises in paintings derived from mathematical digrams. He seems to have made a speciality of painting commutative diagrams.

The Neighbourhood of Infinity is now Open

Sorry about the (mathematical) pun!