Single-instruction Turing-complete programming language
Go to file
Anthony Wang 494de8e432
Add note about infinite Flip programs for Turing completeness
2023-02-15 21:31:39 +00:00
LICENSE Add GPLv3 license 2022-10-14 13:19:27 -04:00
README.md Add note about infinite Flip programs for Turing completeness 2023-02-15 21:31:39 +00:00
flipper.py Implement NAND 2022-10-14 12:41:42 -04:00
nand.f Write README 2022-10-14 12:59:00 -04:00

Flip

Flip is a single-instruction Turing-complete programming language.

Let me break that down for you:

  • Turing-complete means that Flip can do basically anything given enough time and memory. Anything!

  • Single-instruction means that Flip only has one instruction. WTF, one instruction?

Flip uses a single 2-by-infinity array of bits for memory, initially all 0. That's all the memory you get, sorry.

The only instruction is flip(x, y) where x is 0 or 1 and y is an integer. This flips the bit at index (x, y) in the array and returns the flipped value. You can nest flip(x, y), but only for the first parameter. So, flip(flip(flip(a, b), c), d) is valid while flip(flip(a, b), flip(c, d)) is not.

You'll probably get tired writing flip and parentheses all day, so unlike in Lisp, you can throw out all the parentheses and flip instructions. Thus, Flip programs look like this:

0 0
0 1
0 0 2
0 2 1 3
0 3

That means the same thing as

flip(0, 0)
flip(0, 1)
flip(flip(0, 0), 2)
flip(flip(flip(0, 2), 1), 3)
flip(0, 3)

We think you'll agree that the first version is way more aesthetically pleasing and forgiving for your pinky finger.

If you haven't figured it out yet, the Flip program above is NAND! Currently, the final line outputs 0, but remove either of the first two lines, and the final output becomes 1. This makes Flip (drumroll please)... Turing complete!

There's only one catch. Since finite Flip programs are guaranteed to terminate, Turing completeness requires Flip programs to possibly be infinitely long. Good luck!

Even better, a Flip interpreter can be trivially implemented in your favorite programming language. See Flipper for the official reference implementation written in Python.

So if you're ever feeling down about how horrible today's modern programming languages are, try writing some Flip to flip your day around!