Proof That find + mkdir Are Turing-Complete

August 5, 2024 by Donald Papp 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.

A large array of triangles and colored lines showing the folding pattern of the origami computer

Turing Complete Origami

February 21, 2024 by Navarre Bartz 6 Comments

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

November 21, 2020 by Matthew Carlson 21 Comments

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.

Continue reading “A Computer In The Game Of Life” →

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

June 5, 2020 by Donald Papp 34 Comments

[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.

A Nurse Call System Becomes Turing Complete

March 9, 2019 by Bryan Cockfield 3 Comments

George Mallory, a famous English mountaineer, once suggested that it was of no use to climb mountains. Instead, he posited, the only reason to climb a mountain is because it is there. Likewise, when you become an expert in nurse call systems like those found in hospitals, you may find that you do things with them that are of similar use. Making a Turing-complete nurse call system is something you do because you can.

[Erik] has been working on this particular call system, known as Netrix, and used Wireshark to sniff out all of its protocols. With this information he realized that it would be possible to use the system’s routing features to perform all of the tasks that any Turing complete system can do: conditional branching and memory access. He set up a virtual machine and set about implementing all of these tasks using the nurse call system’s features.

The setup for this project is impressive, and belies an extensive knowledge of this one proprietary system but also of computer science in general. It’s interesting to see how something can be formed into a working computer system from parts that otherwise might not be used that way. Even things that aren’t electronic can be used as Turing-complete computers.

Photo via Wikimedia Commons