Todays entry isn’t so much a pathological language itself as it is a delightful toy which can be used to *produce* pathological languages. I’m looking at Chris Pressey’s wonderful language [ALPACA](http://catseye.mine.nu:8080/projects/alpaca/), which is a meta-language for describing different kinds of cellular automata.
Frankly, I’m very jealous of Alpaca. I started writing a cellular automata language something like this on my own; I spent about two weeks of my free time working on it, and got it roughly 90% finished before I found out that he’d already done it, the bastard!
Alpaca definitely qualifies as a real language, in that it is capable of generating turing complete automatons. We can show this in two different ways. First, Conway’s life is a trivial program in Alpaca, and you can build a turing machine simulator using life. And second, Alpaca includes an implementation of a Brainfuck clone as a cellular automaton.
Alpaca’s a very simple language, but it lets you define pretty much any cellular automaton that works in a two-dimensional rectangular grid. And it comes with some very fun, and some very pathological examples.
In case you’re non familiar with cellular automatons, here’s a very quick explanation.
In a cellular automaton, you’ve got a grid made up of something almost like a collection of identical finite state machines, which are called a *cell*. A cell can be in any one of some finite list of *states*. Each time you step time forwards, the cell gets to modify its state by looking at its own current state, and the states of its immediate neighbors. The entire grid steps simultaneously.
It’s a very simple idea, but a remarkably powerful. Some incredibly complicated and fascinating behaviors can be produced by simple cellular automata. Alpaca lets you define pretty much any two-dimensional rectangular grid based cellular automaton.
For example, the most famous cellular automaton is Conway’s “Game of Life”. In life, each cell can have one of two states: live, or dead. Each step, if a cell is dead and it has three neighbors that are alive, it switches to alive, otherwise it stays dead. If it’s alive, and it has 4 or more life neighbors, it dies (overcrowding); if it has less that two neighbors, it dies (loneliness), and if it has three or four neighbors, it stays alive. That’s it – that’s enough to [simulate a turing machine!](http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf)
Life is trivial in Alpaca:
state Dead ” ” to Alive when 3 Alive and 5 Dead;
state Alive “*” to Dead when 4 Alive or 7 Dead.
You nawe the states, and the rules by which they’ll change states. The thing in quotes is
the character that will be used in input files to represent a cell in that state.
Here’s an example of a very simple input file for the life automaton: it’s called a *glider*.
* * * **
If you run the glider, what you’ll get is basically that figure moving diagonally across the grid. Here’s a few steps:
Or much cooler, here’s a pattern called the turbine:
****** ** ****** ** ** ** ** ** ** ** ** ** ** ****** ** ******
If you run the turbine in life, it will go though a cycle of eight steps over and over again:
Another wonderful example of what you can do in Alpaca is wireworld. Wirewold is an amazing automaton which simulates digital circuits. I wrote a bit about wireworld back on the [old GM/BM](http://goodmath.blogspot.com/2006/04/wireworld.html).
In wireworld, you have wires and sparks. Sparks are divided into two parts: the leading edge of a spark, and the trailing edge of a spark. So you end up with four states: empty, wire, spark, and tail. The rules for wireworld are:
1. If you’re the leading edge of a spark, next step, you turn to tail.
2. If you’re wire, and *one or two* of your neighbors is the leading edge of a spark, you turn into the leading edge of a spark.
3. If you’re the trailing edge of a spark, next step, you turn to wire.
4. Otherwise, just stay the way you are.
Written in Alpaca, wireworld is:
state Empty ” “;
state Spark “#” to Tail;
state Tail “-” to Wire;
state Wire “=” to Spark when 1 Spark and not 3 Spark.
And here’s an example of wireworld running, with empty cells as black, wire as gold, leading edge of a spark as green, and tail of a spark as red:
Now, it’s time to get *seriously* pathological. To demonstrate that this is turing complete, Chris implemented a bit-oriented brainfuck variant called Braktif as a cellular automaton. Here’s the alpaca program for it, documentation included:
/*
* The Braktif Cellular Automaton
* June 2005, Chris Pressey
*
* Braktif is an esoteric programming language very similar to
* ‘Brainfuck F’ and ‘Archway’, with a small but significant
* difference: Braktif is formulated as a 28-state cellular automaton.
*
* Braktif playfields are divided into a program on the right and
* a data storage area on the left. (The data storage area can be
* considered to extend indefinately to the left.) The program
* and data area are connected by a ‘bus’. On the bus sit the
* instruction pointer, which rests underneath the part of the
* program which is currently executing, and the data pointer, which
* rests underneath the part of the storage which is currently being
* addressed. The instruction pointer and data pointer communicate
* by means of signals (from the IP to the DP) and replies (from the
* DP to the IP) sent along the bus.
*
* The instructions of a Braktif program resemble those of Smallfuck
* or Brainfuck F:
*
* * flip current data bit
* > advance DP one cell to the right
* +]
*
* Braktif:
* WendCmd) or (> SkipBack),
to SkipStart when ^< SkipReply and ^ InstrMark,
to SkipFore when v< SkipStart or when > is Signal,
to ^> when ^> is Signal,
to v> when v> is Signal,
to < when < is Reply,
to ^< when ^< is Reply,
to v< when v LeftTool or < RightTool,
to ContReply when < ContTool,
to SkipReply when InstrPtr and ^> LeftCmd,
to RightSig when > InstrPtr and ^> RightCmd,
to FlipSig when > InstrPtr and ^> FlipCmd,
to QuerySig when > InstrPtr and ^> WhileCmd,
to InstrPtr when < WakeMark or v< WakeMark or ^< Wakemark,
to InstrPtr when < InstrPtr and ^ SkipBack,
to SkipStop when < SkipFore,
to InstrPtr when FlipSig,
to LeftTool when > LeftSig,
to RightTool when > RightSig,
to SkipTool when > QuerySig and ^ OffBit,
to ContTool when > QuerySig and ^ OnBit;
state FlipTool “f”
to ContTool;
state LeftTool “l”
to Bus;
state RightTool “r”
to Bus;
state ContTool “c”
to DataPtr;
state SkipTool “s”
to DataPtr;
/* —————– Data Store: Tape Contents —————– */
state OnBit “1”
to OffBit when v FlipTool;
state OffBit “0”
to OnBit when v FlipTool;
/* —————– Program: Instruction Pointer ————– */
state InstrPtr “i”
to Bus when ^ Space,
to InstrMark;
state InstrMark “I”
to WakeMark when < ContReply,
to Bus when < SkipReply;
state WakeMark "W"
to Bus;
/* —————– Program: Instruction Skipper ————– */
state SkipStart "!"
to Space;
state SkipStop "%"
to Bus;
state SkipFore "}"
to Space;
state SkipBack "{"
to Space;
/* ——————– Program: Instructions ——————- */
state FlipCmd "*";
state LeftCmd "”;
state WhileCmd “[“;
state WendCmd “]”.
I don’t know how to capture the execution of a braktif program for you to watch; I tried using a screen recorder, but it doesn’t interact well with the terminal where I can run the Alpaca Braktif interpreter. I definitely recommend downloading it and running the braktif example programs: it’s *fascinating* to watch. There’s a data bus connecting the program to the data tape, and as the program runs, you can watch data operations flow across the bus to move the data pointer and alter data on the tape. Fascinating, brilliant, and quite definitely, pathological.
This is just completely and amazingly wonderful. And I hold you directly responsible for the predictable loss of productivity I’m about to experiment. 🙂
Conway, Wolfram, Nash, Selten, Harsanyi and Borcherds – Game Theory in the nature of physics and biology
Is the search for GUT or TOE related to a game of energy economics?
John Conway, mathematics at Princeton University, With Simon Norton he formulated the complex of conjectures relating the monster group with modular functions, christened by them monstrous moonshine.
http://en.wikipedia.org/wiki/John_Horton_Conway
Conway’s Game of Life [game of cellular automata]
It made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner’s “Mathematical Games” column. From a theoretical point of view, it is interesting because it has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway’s Game of Life.
http://en.wikipedia.org/wiki/Conway's_Game_of_Life
Stephen Wolfram, particle physicist, “known for his work in theoretical particle physics, cellular automata, complexity theory, and computer algebra, and is the creator of the computer program Mathematica” and author of ‘A New Kind of Science’.
http://en.wikipedia.org/wiki/Stephen_Wolfram
Nash [equilibrium with at least one stable outcome], Selten [perfection concepts for outcome predictions], Harsanyi [incomplete information analysis] were awarded the 1994 Nobel Economics “for their pioneering analysis of equilibria in the theory of non-cooperative games”
http://nobelprize.org/nobel_prizes/economics/laureates/1994/
and
http://nobelprize.org/nobel_prizes/economics/laureates/1994/presentation-speech.html
The Nash embedding theorem states “that every Riemannian manifold can be isometrically embedded in a Euclidean space R^n”.
http://en.wikipedia.org/wiki/Nash_embedding_theorem
Richard Borcherds invented the notion of vertex algebras, which Igor Frenkel, James Lepowsky and Arne Meurman used to constuct [sp] an infinite-dimensional graded algebra acted on by the monster group. Borcherds then used this, and methods from string theory, to prove the Conway-Norton conjecture, relating the monster to the coefficients of the q-expansion of the j invariant. The result was not only a great increase in understanding of the monster group, a very large finite simple group whose structure was previously not well-understood, but tied the monster to various aspects of mathematics and mathematical physics [monstrous moonshine]”.
http://en.wikipedia.org/wiki/Richard_Borcherds
Will string theory, loop quantum gravity, information theory, attractors [chaos] or game theory be the first to solve GUT or TOE?
Are these various branches of mathematics related?
Ooh, I wanna see it. Now that I’ve finally gone and formatted my Dell laptop and put Linux on it, I’ll be able to more easily run a lot of your pathological languages. ^_^
I lost you when you started to implement Bratkif.
By the way, “if it has three or four neighbors, it stays alive” is a mistake – a live cell stays alive if it has two or three neighbors.
Hmm…
I’ve been trying, since I saw this yesterday, to try to figure out a way that this could be used to create some kind of cellular automata based interpreter for combinators, or a combinator-based language like Unlambda or a SKI machine or Lazy K would represent.
I was thinking at first you could try to graph out the tree-like structure of a lazy k s-expression, which the ALPACA rules would operate on until it was fully evaluated. But thinking about it now that doesn’t really seem so much possible, since would need to operate on entire sections of trees, and in the cellular automata world it only really seems to be possible to operate on individual symbols.
Is this an entirely hopeless train of thought?
By the way, Mark, what did you use to create the automata graphs in your post? Were those automatically generated by something?
How do I actually run ALPACA programs?
I don’t know anything about Python scripts, and I can’t figure out what to do!
Andrew:
It’s certainly not hopeless, but it’s *not* going to be a remotely easy thing to do. Combinator evaluation is based on tree expansion and contraction – and to do that in a CA requires using something like the data bus in braktif – a channel that carries communication between different parts of the tree.
I think you would need a two-panel approach, like braktif; one panel would be the expression in tree form, and the other would be an “interpreter state” area. You’d have an instruction pointer like braktif, which would traverse the tree, and send data over to the state area describing the tree it traversed.
You might also want to read the paper I linked to about the Life Turing machine; the techniques that that uses for communication would likely help you understand more about the kind of approach that you’d need to follow.
Andrew:
The graphs were drawn by hand using omnigraffle on the mac.
At some point, I’m going to write a series of articles about CAs; for that, I’ve been working on a program to generate graphics. I’ve been toying around with both SVG and XPM formats. XPM is easier to generate, but then you need to go through an annoying extra translation step to turn the file into a format that’s useful for web pages. SVG is better in that respect, but I don’t have an SVG library for the languages I’d rather use (Scheme or OCaml), which is a pain.
Carl, excellent piece! You’re THE MAN!!!
I haven’t tried this, but do you think it would be possible to implement rule 110 (http://en.wikipedia.org/wiki/Rule_110) in Alpaca? It, like Brainfuck, is Turing complete, but would be much simpler the implement (despite the fact that it requires an infinite input string). Also, Matt Cook is awesome.
Alex:
Unfortunately, no, you can’t do 110 in Alpaca. Alpaca is 2-d rectangular-grid only, and R110 is a one-dimensional automaton. You could sort of cheat and build a 2d-110 by only changing state if your left, right, and below neighbors are all in the “empty” state, and then do the 110 rule using the states from the row before. But even then, the fact that 110 is only turing equivalent if it’s got an infinite input string would be a problem. I don’t think that the turing complete property of R110 has any practical application, because it’s so close to impossible to ever implement anything with it.
Also, since we know that Conway’s life is TC, and Alpaca can do Life in two lines, the fact that it’s TC is obvious. What’s amazing about the brainfuck-variant interpreter is how he implemented a bus/tape machine using a cellular automaton. I mean, it’s a pretty crazy thing to do, and he managed to do it in *such* a simple way.
(Quick explanation: the BF interpreter as CA doesn’t look simple. But compare it to the Life turing machine I linked to, which is 1800 by 1800 cells, *without* anything on the input tape. Comparatively, implementing a turing machine in a CA using 28 states, and generating something which is actually *comprehensible* once you watch it a little is an *amazing* feat.)
I can’t seem to reach that Russian site. Any other sources?
In fact, I just managed to figure out that mine.nu (OK,not Russian) has apparently been vacated and returned to it’s provider. So where can we get this thing?