Manufactoria: Computer Science Disguised as a Game
Ever wanted to create discrete finite automata in a Flash app? Wait—that probably wasn’t appealing.
Let’s try this: Set up a factory in Manufactoria to distribute robots and accidentally learn computer science at the same time!
In Manufactoria, your job is to test robots to see if they match a certain standard. To do this, you’re checking to see if their colored dots (red and blue) match a pattern you’re given, and you have to do it with conveyor belts and switches. Examples include testing to see if a robot has at least three blue dots, or if the number of red dots is the same as the number of blue dots.
Beyond the robots, conveyor belts, and quality assurance aspect, this doesn’t look particularly geeky—until you consider what the game is analogous to. It turns out that the system you build with switches and conveyor belts is an excellent description of a deterministic finite automaton, and deterministic finite automatons are equivalent (if inefficient) to Turing machines. For what it’s worth, your computer is a Turing machine with some minor limitations. This means that if you consider the conveyor belt system a computer and the red and blue circles to be binary, you’re effectively programming in a Flash game.
Update: As Anonymous CS Student points out in the comments, discrete finite automata are definitely not equivalent to Turing machines (or the machines created in Manufactoria.) They are, in fact, much weaker.
Posted by carneywilson on May. 24, 2010
Comments
Just for your information, DFAs are NOT equivalent to Turing Machines.
Posted by Anonymous CS student on 05/28/2010 03:52 PM
Sir, you are quite correct. I had my equivalence severely confused.
Posted by Carney Wilson on 05/28/2010 04:16 PM
This is an evil, time sucking robot QA game and you are evil for posting this.
*goes back to playing*
Posted by Peter Mallett on 05/27/2010 02:12 PM