Re:Show HN: Compile C to Not Gates
by jvanderbot on Saturday January 18, 2025 @09:20AM
(#42748513)
Is the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.
[ Parent
| on HN ]
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.
Re:Show HN: Compile C to Not Gates
by jvanderbot on Saturday January 18, 2025 @03:10PM
(#42751039)
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).