Manufactoria

Last Friday I stumbled on Manufactoria, a cute web-based game in which the object is to build machines for testing and repairing robots.

This is done by manipulating a robot’s code, a sequence of red and blue symbols. Each part of the testing machine consumes a symbol, or pushes the robot into another part of the machine. And if the symbols for the robot match its design requirements, then the robot passes the test and is pushed through the exit; if not, it’s dumped unceremoniously onto the factory floor. A simple machine looks like this:

As long as the robots start and end with a blue, they can have as many red dots as you like. In other words, br*b!

At this point, the average programming blog reader is probably thinking: “Hmm, matching a sequence of symbols, you say? That sounds familiar!” Indeed it does. Each problem is (almost) equivalent to: construct a finite state machine for recognising the specified regular language.

It’s like the Alligator Eggs game. But it’s arguably more playable, because it’s easier to make a simple machine to do something interesting and concrete, than it is to practice husbandry on carnivorous coloured alligators and interpret the results as abstract computation. (But someone should definitely make a web game about alligators, just to prove me wrong!)

Programming with colours

I spent a large part of Friday’s lunch hour, and the weekend, working through its puzzles. The game begins simply by asking the player to build a series of conveyor belts moving the robot from the entry to the exit: no matching required. But each new puzzle gets a little bit harder. Features — matchers, printers, additional colours — are introduced gradually. In this way the player learns to build surprisingly complicated machines.

At the same time, most discussion of theory is avoided: the game about matching and printing colours, and moving robots round a factory. Each robot has a brief comment on its practical purpose, and they become more advanced, culminating in the Engineer robot: “Robot engineers. Designed to build testing machines. Harmless.” Once those can be built, the player is obsolete, but the new robot overlords graciously allow him to continue experimenting.

In the main set I just need to complete the machine for testing Judge robots: accept all even-length sequences that repeat half way through. This one is the combination of two earlier challenges:

1. Police robots: put a yellow symbol into the middle of an even-length sequence.
2. Seraphim robots: accept two occurrences of the same sequence separated by a green.

Building both those machines (swapping the roles of yellow and green in the second one) and connecting them in series would solve the Judge puzzle. Unfortunately, the space required by the Police machine is almost as much as is provided for the Judge machine, leaving little room for the subsequent Seraphim machine.

At one stage a small set of supplementary robot types appeared; it’s possible that completing them or the Judge will reveal further challenges. Given the largest board size of 13×13, there are (1 + 4 + 4*4 + 2*2*4)^(13^2 – 2) = 243,569,224,216,081,305,397 distinct machines that can be built.

Can you figure out what this one does?

Of course, most are not the solution to any succinctly-described problem. Many will behave identically. Some will loop forever. Most will probably crash (i.e. dump the robot on the floor with a loud crash!) at the first opportunity.

Musings on computation

Manufactoria tests each machine by running a small set of test inputs through it. But, for simple machines, it could probably do this more analytically: if the machine matches the exact regular expression described by the problem statement, then it passes.

The exact computational power of regular expressions is easily defined as that of simple finite state machines; there are well-established theorems for converting between the two equivalent representations. And there are many computational analyses which can be carried out on finite state machines.

One of which is as follows: construct the machine corresponding to the puzzle’s regular expression. Take the difference between that machine and the submitted solution. And the difference the other way round. If both differences are trivial machines that don’t match anything, then there are no inputs matched by one machine but not the other, and therefore the solution is 100% correct. Just try that with Turing machines or the like — you’ll run into trouble before you can say entscheidungsproblem.

Are the simpler machines — those that match colours but don’t print them — in Manufactoria equivalent to finite state machines? They must almost be, but they have some limitations:

1. They must occupy a finite floor space in the factory. I believe this limitation should largely be disregarded for questions of general computation, because the factory floor could always, in principle, be expanded into a larger finite area. If there are theoretical computations that would require infinite space, that is another matter.
2. They can only operate on two colours: red and blue. We could define a mapping from regular expressions on multiple colours to one on binary codes: for instance, if the original problem was specified in terms of 8 symbols, we could build a Manufactoria machine in which each match operation read 3 binary colours in succession, and lead to up to 8 distinct states, one for each 3-bit symbol. So, for general computation, a limit of two symbols is not an issue.
3. The machines in Manufactoria must be planar: conveyor belts cannot cross each other! [Edit. Actually I’m mistaken about this; they can cross. But for the sake of the proceeding discussion let’s pretend they can’t.] This one is not so easily dismissed. Does every finite state machine have a planar equivalent that accepts the same regular language? Apparently this is the wire-crossing problem.
4. Planarity has related limitations: the entry and exit must be in the same plane, because they are both on the edge; what’s more, a matcher can only branch on two colours, and routes other colours and the end of input to the same place, where they must be further distinguished by the other matcher type. Although this can be done compactly, there are only so many orders in which the outgoing edges are arranged from the matcher.

The limitation of planarity is addressed in this interesting paper (.ps). It shows that deterministic planar finite automata are not computationally equal to finite automata: so Manufactoria machines cannot be made to match all regular languages. The proof is based on a minimal deterministic machine of six symbols and six states. Each state leads to each other state: the graph of the machine must contain K₅ and hence, by Kuratowski’s theorem, be non-planar.

Printing is power

The addition of printing components to the machines makes them more interesting. Match-only machines have only finite state: the state must be represented in terms of which part of the machine is currently active. But in a printing machine, a symbol does not have to be discarded once it is read: it can be stored at the end of the tape, to form a new input for further processing. In this way it’s easy to build a machine that passes over the tape, performing a finite automaton’s computation in each pass, but able to loop indefinitely. Such machines clearly have more computational power, and are capable of matching classic non-regular languages such as:

• Palindromic sequences of arbitrary length.
• Sequences in which symbols must be counted in some way, up to any arbitrary number.
• Sequences of repeating arbitrary-length strings.

These are all advanced puzzles in Manufactoria, so even its limited machines are capable of recognising those languages.

But does the ability to print fully undo the limitations of planarity? That is unknown, but we might be able to prove it if we can find a way to rewrite the six-state non-planar example from the Planar Finite Automata paper as a printing-machine, where some of the state is stored on the tape and not in the machine.

Assuming the limitations of planarity are overcome, how computationally powerful are printing machines? Are they Turing complete? They initially reminded me of Post-Turing machines, which are known to be Turing complete.

My guess is that they are not. But it’s worth remembering people have built fully functional computers in Minecraft: the fact that something hasn’t been acheived yet is not a good basis for betting that it’s impossible.

Postscript. The machines are based on queue automata, which are Turing complete after all.