[zokier]

Adders belong to category of combinational logic, which by definition excludes memory. So OP is right, they do not yet demonstrate Turing Completeness. I imagine, but don't actually know, that they would be about as expressive as dfa, which are few steps below turing machines

[davrosthedalek]

He builds the adders from ANDs, ORs and NOTs. With these, you can also build flip-flops, which are memory. (Actually, it's enough to have only NAND (or NOR) to build all logic circuits, including memory)