←back to thread

Show HN: Compile C to Not Gates

(github.com)
145 points tomhee | 2 comments | 17 Jan 25 19:36 UTC | HN request time: 0.407s | source

Hi! I've been working on the flipjump project, a programming language with 1 opcode: flip (invert) a bit, then jump (unconditionally). So a bit-flip followed by more bit-flips. It's effectively a bunch of NOT gates. This language, as poor as it sounds, is RICH.

Today I completed my compiler from C to FlipJump. It takes C files, and compiles them into flipjump. I finished testing it all today, and it works! My key interest in this project is to stretch what we know of computing and to prove that anything can be done even with minimal power.

I appreciate you reading my announcement, and be happy to answer questions.

More links:

- The flipjump language: https://github.com/tomhea/flip-jump https://esolangs.org/wiki/FlipJump

- c2fj python package https://pypi.org/project/c2fj/

Show context
jvanderbot ◴[18 Jan 25 14:20 UTC] No.42748513[source]▶
Is the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.
replies(1): >>42748809 #
1. tomhee ◴[18 Jan 25 14:56 UTC] No.42748809[source]▶
The power is within the self modification of the code. The jump might be implemented by a multiplexer, though it can be implemented in other ways too.
replies(1): >>42751039 #
2. jvanderbot ◴[18 Jan 25 20:10 UTC] No.42751039[source]▶
A CNOT is universal (transistor effectively) I don't think a NOT is universal.

I'm sure you can self modify your code so it executes only using XOR (bit flips), which is a CNOT, but I do not think this could be compiled down to an FPGA using only a billion not gates.

Actually I just convinced myself you can make an AND from three NOT gates if you can tie outputs together to get OR, so I believe you now. Sorry for the diversion! (Though I still dont see how bit flips and jumps directly can be built into a circuit, I know AND and NOT are universal so it's all good).