Are you sick of having to work out the Collatz Sequence by hand? Run out of whiteboard space? Hand cramping up with all your scribbling? Then you need my latest project, the Collatz-O-Matic!:

Shown with LEDs spooled, ready for computation on the go

This came about because after the previous posts on Cellular Automata, I sent a link to Stephen Wolfram, he kindly emailed back and said he thought it was cool. However the email ended with: (emphasis mine)

P.S. If you’re into such things, you might enjoy http://www.wolframscience.com/nksonline/page-0895c-text

I think in all these years nobody has yet actually implemented this…

Darn it, that sounds like a challenge.

I had actually already planned out what my next project was going to be, but unfortunately my brain felt this was enough of a nifty concept to make me drop what I was doing and start sketching tag systems. After a brief dialog with my shoulder angels, I gave in.

A Post Tag System is a method of computing very similar to a Turing Machine. There’s an array of symbols, or a tape, or a queue, however you want to call it, and a simple series of operations are performed on it at each timestep.

My machine is set up to follow the Collatz conjecture, which we’ll describe shortly. Every step the following things occur:

• 2 tags are deleted from the start of the tape
• If the first symbol deleted was:
  • A – then write BC to the rear of the  tape
  • B – then write A to the rear of the tape
  • C – then write AAA to the rear of the tape

That’s it. That simple behaviour is enough to implement the [modified] Collatz sequence below. (If the number is even, then divide by 2. If odd, then multiply by 3, add one, and divide by 2.  )

By the way, the Collatz conjecture is still an unsolved problem in mathematics. So far every positive integer tested flows to 1, but it’s not yet been formally proved that all positive integers will.

Back to the tag system! I started looking at systems with rolling balls, as Stephen Wolfram suggested. Hooking up a couple of servos to sort of sluice-gate the flow of balls from a set of hoppers is fairly doable. There are a number of ways to detect the different types of balls, but a colour sensor is probably easiest. I got some cedar spheres from the dollar store and started prototyping.

Computing in action.

Hmm… how many balls would I need? Based on wanting to calculate the Collatz sequence for each number 1 to 30, working out the maximum intermediate values for each… average ball size 23mm… let’s see…. length of the track is… Two hundred and twelve meters.

OK, perhaps a tad too ambitious for a quick project.

As an alternative strategy, I decided to use LED strip as the ‘tape’, and make a very simple interface with an arduino. Here’s how it works:

• When the machine’s stopped, the A/B/C buttons add that symbol to the end of the tape.
• If the tape holds only ‘A’s, ( no ‘B’s or ‘C’s), then update the numeric display at the bottom left to show the current number
• Each step two symbols are deleted from the start of the tape, the corresponding rule lamp is lit up, and new symbols are added to the far end of the tape.
• Clear button stops or resets the display, ‘Step’ runs one step of simulation forward (until the next number in the sequence is reached), and ‘Auto’ runs the sequence until it reaches 1.

Here’s the machine in action:

Fun fact, if you try and start from 27, then the machine will break! That’s because the values go up to 9,232 on the way to reaching 1. My (inefficient) code uses a byte per tag symbol, and the arduino only has ~2k of memory, so I run out of space long beforehand!

I put in some code to detect the tape running out, and here’s what it looks like after a few minutes of churning away:

Your modern electronics are no match for the might of the number 27.

Inside the machine is an Arduino Nano, some LEDs and switches, and a couple of meters of Adafruit Neopixels

Not my finest work, but it should be reasonably sturdy

The files are up on Thingiverse here for anyone that wants to make their own:

http://www.thingiverse.com/thing:1810442