# Classical Computation without NOT [closed]

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible universal sets of gates that do not utilise the NOT transformation. Thanks!

• All classical boolean logic can be represented using either just NOR gates or just NAND gates - do you regard those as a NOT? Jul 17, 2015 at 17:44
• This doesn't really belong on physics.se. Jul 17, 2015 at 17:57
• I'm voting to close this question as off-topic because it is about abstract computational logic, not physics. Jul 17, 2015 at 20:59
• I agree. Not only too abstract but of course this could be done, with a bunch of extra circuitry. But why? Maybe in a fictional unicverse. This maybe should be in the Sci-Fi SE. And by the way, try it out yourself. Draw up some circuits this way then use Karnaugh maps to reduce them to their simplest, without NOTs. Then compare them to straightforward normal logic circuits, again reduced by Karnaugh. Start with a simple flip-flop or an adder. You will see why nobody would want this. Apr 10, 2017 at 22:43

$$[Y][Z]/i = [\text{NOT}]$$
Where $[Y]$ and $[Z]$ are Pauli gates. It's already known that quantum computing can do universal computations, using only a specific sets of gates. One such set is the Hadmard gate, a phase shift gate, and the CNOT gate. Substitute the CNOT gate with either a controlled $[Y]$ or a controlled $[Z]$, and you can recreate the CNOT using the controlled gate together with the single qubit gates, thus forming a new universal set.