# Why Mark is a Computer Scientist at Heart

So, I came across a question on Quora about showing that no reversible two-bit gates are universal. (NAND is universal for boolean logic but not reversible!)

My first thought was the CS one: well, how many 3-bit reversible functions are there? We could probably just do exhaustive search on combinations of two-bit gates and exhaust the space, there are far less than 8^8 reversible functions and that's only 16 million. (Hmm... how many are there? Must be something like 8! since each output must appear once and only once, so a reversible function is a permutation of the identity function.)

But the mathematical answer is the one I had to look up. All the 2-bit reversible functions are binary. That is, they are of the form f(x,y)=M(x,y)+(a,b) for some 2x2 matrix M. And the composition of linear transformations is always linear. But you can come up with a nonlinear 3-bit reversible binary function. (The Toffoli gate, which *is* universal, is one of them.)

If given enough time, I could probably come up with the second answer. But the first one is a lot more fun. :)
Tags:
• Post a new comment

#### Error

default userpic