For the Languages and Compilation course at Lancaster we have students create a variety of automata on JFLAP. The idea of this project was to construct a turing machine that could interpret and run the turing machines they build, and due to a complete lack of mechanical skill my medium was lego.
There's already someone out there who's made one of these, and I set out in part to best them. I soon realised, however, that even the mindstorms lego sets aren't designed to make anything with much finesse, so a number of my original plans had to go out the window.
This page gives a brief overview of the design so that you can learn from my mistakes. Construction and coding this took about 26 hours, but much of that was spent rebuilding failed designs.
All of the images taken during construction are sitting in a Picasa Album. In it you'll see a few failed designs for the read/write system, and a million different layouts for the wheels and followers.
Until I've sorted out the read/write logic, here's a fairly silent video of a previous version running back/forth on the tape, and operating its arms.
Initially, I had intended to avoid the techniques used by the other machine, however, it soon became apparent that the limited number of IO devices (and skill) made this tricky.
The device moves along its tape by sensing transitions between black and white patterns it sees on the floor. For ease of use, this sensor is aligned with the read/write head. The thing itself runs along a rail, which is nothing more than a bit of dowel taped to the desk (or anything the guide wheels can grab onto).
Read-write systems proved to be particularly tricky: bits are indicated by the position of a block — if they lie over one side of the machine, that position is set to 1/on/true, else it is 0/off/false. This means that the read/write head must:
On this machine, one half of the read/write head is a slider, and the other half is an arm that swings down. When moving over a new position, the slider is shuffled to its "off" position, and the arm is raised out of the way of any blocks. Writing a block is as simple as moving the arm or slider to push it off/on. Reading a block's position is accomplished by lowering the arm and monitoring the state of a light sensor mounted at the end — if the light sensor triggers before the end of the arm is reached, then a block is there. Each 'read' operation is followed by a write to undo any damage the arm may do.
In order to optimise the read/write cycle, a second light sensor is mounted on the slider's head. This allows for detection of three states: empty, 0 and 1, as well as offering feedback when both arms are in operation.
The lego set I was working with was a lego mindstorms "robotics invention systen 2.0", which has the RCX-2.0 in it. This is the precursor to the NXT used in the project mentioned above, and has some fairly severe limitations:
Through careful design and planning it may be possible to create a read/write and movement system with just three sensors, but I didn't do any — Lego sensors can be stacked to AND their values, meaning that an analogue sensor can be paired with a digital one: if the value is above a certain value (say 99% of the sensor's input range), then the digital one is activated. This technique allows us to ignore one sensor whilst reading the other, so long as we don't want both at once.
It's also possible to use the same sensor input for many different mechanisms, so long as it's possible to ensure that all other sensors on that channel are off during an operation. This method was also used to attach a few boolean touch sensors to the same input.
A diagram of the wiring is somewhere off to the right
I knocked up a printable track in scribus for setting the thing up, and made a series of little blocks out of lego that act as data. The machine will read almost anything that triggers the light sensors, so mints, bottlecaps etc all work well as bits. The only blocks I had were black, so they needed post-its to make them reflective enough.
Programs can be loaded onto it directly from JFLAP using this compiler (apologies for the messed up render). NQC's function inlining can make generating concise source tricky, so a trampoline is used to launch functions. Even so, it's only capable of interpreting simple automata (which is good, because it's binary-only and tricky to code for)
