# Proof That find + mkdir Are Turing-Complete

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.

# Turing Complete Origami

Origami can be an interesting starting point for a project, but we weren’t expecting [Thomas C. Hull] and [Inna Zakharevich]’s Turing complete origami computer.

Starting with the constraint of flat origami (the paper folds back on top of itself), the researchers designed a system that could replicate all the functionality of the previously-proven Turing complete Rule 110 automaton. The researchers walk us through the construction of AND, OR, NAND, NOR, and NOT gates via paper as well as the various “wires” and “gadgets” that connect the operators or filter out noise.

Everything ends up a large mess of triangles and hexagons with optional creases to make the whole thing work. While the origami computer probably won’t be helping you slice 3D prints anytime soon, much like a Magic computer, the engineering and math involved may prove useful in other applications.

We’re no strangers to origami here, having covered origami machines, medical robots, or using a desktop vinyl cutter to pre-score your project.

# A Computer In The Game Of Life

We often hear the term “Turing-complete” without giving much thought as to what the implications might be. Technically Microsoft PowerPoint, Portal 2, and Magic: the Gathering all are Turing-complete, what of it? Yet, each time someone embarks on an incredible quest of perseverance and creates a computer in one of these mediums, we stand back in awe.

[Nicolas Loizeau] is one such individual who has created a computer in Conway’s Game of Life. Unlike electricity, the Game of Life uses gliders as signals. Because two orthogonal gliders can cancel each other out or form a glider eater if they intersect with a good phase shift, the basic logic gates can be formed from these interactions. This means the space between gates is crucial as signals need to be in phase alignment. The basic building blocks are a period-60 gun, a 90-degree glider reflector, a glider duplicator, and a glider eater.

All the Python code that generates these structures is on GitHub as the sheer size of the machine couldn’t possibly be placed by hand. The Python includes scripts to assemble the basic programs as a bank of selectable glider generators. It’s all based on Golly, which is an excellent program for simulating Conway’s Game of Life, among other things. While this isn’t the first computer in the Game of Life as [Paul Rendell] published a design in 2000 and [Adam Goucher] published a Spartan universal computer constructor in 2009, we think this is a particularly beautiful one.

The actual architecture has an 8-bit data bus, a 64-byte memory with two read ports, a ROM with 21 bits per line, and a one-hot encoded ALU supporting 8 different operations. Instructions have a 4-bit opcode which is decoding in a few different instructions. The clock is four loops, formed by the glider reflectors as the glider beams rotate. This gives the computer four stages: execution, writing, increment PC, and write PC to memory.

The Game of Life is an excellent example of Cellular Automaton (CA). There are several other types of CA’s and the history behind them is fascinating. We’ve covered this field before and delved into this beautiful fringe of computer science. Check out the video below to truly get a sense of the scale of the machine that [Nicolas] has devised.

# Tic-Tac-Toe Implemented In Single Call To Printf()

[Nicholas Carlini] programmed a C implementation of two-player Tic Tac Toe, and he did it in a single call to `printf()`. The arguments for that single function call get mind-bendingly complex, so it may come as no surprise that it was written for The International Obfuscated C Code Contest (IOCCC).

Most of us are aware that `printf()` is one of those functions that is considerably more complex under the hood, and capable of far more, than it may appear to be. But did you know that it is capable of Turing-complete computation?

[Nicholas] clearly steps through the theory, so give it a read. In short, a maze of arguments handles the logic of the game while an embedded `scanf()` reads user input, and printing the game board is always preceded by an escape code to clear the screen.

[Nicholas] is certainly no stranger to in-depth understandings; we’ve seen his work before in demonstrating how to fool speech recognition with hidden commands, including a powerful example showing how two virtually identical-sounding audio files transcribe entirely differently.