CELLULAR AUTOMATA

My program ant.c implements a generalization of Chris Langton's cellular automaton rule. (A fancier simulator has been developed by Scott Sutherland, and as of 2001, a really spiffy Java version has been posted on the Web by Steve Witham.) To implement the Truchet-tile feature of my program (added by Scott Sutherland), you will also nead to get a copy of the file ant.pro. For background, see Further Travels with My Ant (by David Gale, Scott Sutherland, Serge Troubetzkoy and myself; published in the Mathematical Intelligencer, volume 17 (1995), summer issue, pages 48-56).

More recently, I've been exploring a class of deterministic automata that model random behavior. The simplest of these "quasi-random" automata are based on simple mechanisms I call "rotor-routers". Hal Canary and Francis Wong have created an applet to demonstrate some of the features of these machines. It's very much a work in progress, so if you have suggested for how version 1.0 of the applet could be improved, please let me know! If you want to download your own copy of the applet, get rotor.tar.gz (2010 version; bug fixed by David Einstein).

TILINGS

The program vaxmaple.c (developed by Greg Kuperberg, David Wilson David Wilson and myself and described in vaxmaple.doc); it allows one to count the perfect matchings of a bipartite planar graph using the method of Kasteleyn. In 2016 Frederic Chapoton created a Sage version (also available as a text file because the UML site apparently doesn't like .py files). If for some reason you find yourself needing to know how many ways there are to cover a 6-by-8 grid with 1-by-2 rectangles, this is the program for you. Or use vaxmathematica.c (information on compilation and use appears in the header). I and my students have also developed software that'll let you choose uniformly at random from the set of all such tilings; contact me if you're interested.

An especially neat implementation of Kasteleyn's trick is embedded in the vaxmacs package of David Wilson. It gives you all the power of vaxmaple and more in an easy-to-use interactive environment based on the popular editor emacs. The documentation for this package is contained in the program itself. You will need emacs-19.30 (or a later version of emacs) in order to get full use of vaxmacs.

An even newer program, that takes full advantage of the "urban renewal" method of counting, analyzing, and generating random dimer configurations, is Harald Helfgott's C program "ren". ren is written in C, in the form of two files, ren.c and ren.h (and it makes use of two supplementary files, r250.c and r250.h). Matthew Blum's documentation for the program is also available. Many of the source files are available here too, such as drawtiling, vax2wt, findarctic, and printtiling.

If you want to count matchings of some non-bipartite planar graph, Matt Blum's TCL-program graph.tcl lets you define an arbitrary planar graph, and Ben Wieland's perl-program planemaple.pl (which graph.tcl "knows about") lets you count the matchings of this graph efficiently, exploiting Kasteleyn's method. The program graph.tcl will also let you count matchings of non-planar graphs, but it does so by the brute-force method of finding them all, which will not be practicable when the graph is large. Both programs require the user to make some modifications to the header.

Billy Hillegass has created a new version of graph.tcl that may be easier to use on Windows systems.

You can also check out the very nice applet --> applet created by Jason Woolever in the 1990s which allows one to generate random tilings of a variety of kinds by means of "coupling-from-the-past" (a general method of generating unbiased random combinatorial objects, invented by David Wilson and myself and described in a joint article published by Random Structures and Algorithms). In 2009 Ben Wieland made some modificiations to the code for the specific purpose of generating random alternating-sign matrices; see http://math.brown.edu/~wieland/asm-frozen/. Sometime around then, though, browsers stopped supporting Java. Fortunately, in 2024, Scott Vorthman showed me a workaround for those who have a Mac that can run Java: just type (for instance) "appletviewer https://faculty.uml.edu/jpropp/applets/hexagon.html" into a command window. Unfortunately this doesn't work if your version of Java is too recent, since (for instance) Java 21 won't let you run appletviewer. To fix this, install Java 8 (Macs will let you install multiple versions of Java and switch between them as needed). In May of 2024, Scott found an even better method; click here to give it a try. If that's not good enough for you, send me email.

Finally, if you just want to see a spiffy implementation of the domino-shuffling algorithm of Elkies, Kuperberg, Larsen and myself, and you've got access to perl/tcl/wish, download and run Matt Blum's program shuffle.tcl.