What's the argument that AND is less complex than NAND? It's true that NAND has ...

TylerE · on Aug 29, 2023

It seems naively obvious to me that a(b(x)) is more complex than b(x). Practically tautology.

thaumasiotes · on Aug 29, 2023

You have to justify why you've chosen the particular starting point. NAND isn't defined as being "first you do AND, and then you negate it". It's defined like this:

    +---+---+-------+
    | a | b | a ↑ b |
    +---+---+-------+
    | 0 | 0 |   1   |
    +---+---+-------+
    | 0 | 1 |   1   |
    +---+---+-------+
    | 1 | 0 |   1   |
    +---+---+-------+
    | 1 | 1 |   0   |
    +---+---+-------+

AND is defined like this:

    +---+---+-------+
    | a | b | a & b |
    +---+---+-------+
    | 0 | 0 |   0   |
    +---+---+-------+
    | 0 | 1 |   0   |
    +---+---+-------+
    | 1 | 0 |   0   |
    +---+---+-------+
    | 1 | 1 |   1   |
    +---+---+-------+

You may notice that they are almost exactly the same.

> It seems naively obvious to me that a(b(x)) is more complex than b(x).

This is just obvious gibberish; if you define b(x, y) = x & y and a(x) = ~x, then you can say "I think a(b(x, y)) looks more complex than b(x, y)", but how do you respond to "when c(x, y) = x ↑ y, I think c(c(x,y), c(x,y)) looks more complex than c(x,y)"? The two claims can't both be true!

Everything, no matter how simple, can be described as the end of an arbitrarily long chain of functions. So what?