Tag System

2 Articles

Proof That find + mkdir Are Turing-Complete

August 5, 2024 by 10 Comments

Data manipulation is at the heart of computation, and a system is said to be Turing-complete if it can be configured to manipulate data in a way that makes implementing arbitrary computation possible. [Keigo Oka] shared a proof that find and mkdir together are Turing-complete, which is to say, a system with only GNU’s find and mkdir has access to enough functionality to satisfy the requirements of Turing completeness, which ignores questions of efficiency or speed.

[Keigo Oka]’s first attempt at a proof worked to implement Rule 110, an elementary cellular automata configuration that has been shown to be Turing-complete, or ‘universal’, but has been updated to implement a tag system as it’s proof, and you can see it in action for yourself.

Seeing basic utilities leveraged in such a way illustrates how computation is all around us, and not always in expected places. We’ve also seen Turing-complete origami and computation in cellular automata.

The Collatz-O-Matic: A State Machine With Style!

October 10, 2016 by 2 Comments

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. Continue reading “The Collatz-O-Matic: A State Machine With Style!” →