Monday, October 10

The Collatz-O-Matic: a State Machine with Style!

If you have ever thought that working out a Collatz sequence by hand was alright but lacked buttons and lights, the Collatz-o-matic by [mechatronicsguy] has you covered!

collatz-o-matic-closeupThe device is a type of Tag system calculator. [mechatronicsguy] explains that a Tag system is a method of computing similar to a Turing machine; it consists of a read & write FIFO array (or tape or queue) of indeterminate length, and at every step the system reads the symbol at the “head”, deletes a fixed number of symbols from the “head”, and depending on what that first symbol was, appends one or more symbols to the “tail”. Then the process repeats with whatever new symbol is at the head.

The Collatz-o-Matic uses an RGB LED string to represent the queue, and is set up in the following way:

  1. Delete two symbols (tags) from the front of the queue.
  2. If the first symbol deleted was:
    1. A – then write BC to the rear of the queue
    2. B – then write A to the rear of the queue
    3. C – then write AAA to the rear of the queue

Numbers are as easily represented as any other symbol, and the Collatz conjecture is that no matter what integer you start with, the system (probably) always eventually reaches state 1. There is video of the device demonstrating exactly that embedded below.

LED strips are clever stand-ins for a tape of indefinite length. The similarity to a Turing machine is clear, and we’ve seen a variety of physical implementations of Turing machines in the past – some with exquisite workmanship.


Filed under: misc hacks

No comments:

Post a Comment