NAND gates?

For those who haven't checked either nandgame or nand2tetris out, I would recommend them as fun little diversions in boolean logic and computer architecture.

Maybe I am starting to spam the thread a bit here but I think the answer is canonical S-expressions, but proving that to be the case is more tricky than it looks although it is also kinda obvious from the surface level; vectors in s-expressions.

But yeah the real answer is lambda calculus, see lambda lisp and justine.lol

Any sufficiently rich data structure is probably enough on its own. Lists certainly are. For example, you don't need arithmetic separately, since you can simulate it with lists in any number of ways; e.g., the von Neumann-esque `0 = ()` and `succ n = n : n`, according to which a number is represented by a canonical list of that length. Once you can define `succ`, you can define all other arithmetic. If you're willing to give up canonical representatives, and represent a number by any list of that length, then you get an easy definition of addition by concatenation.

If you'll forgive my giving an answer that clearly wasn't what you intended, rather famously, lambdas are sufficient: https://en.wikipedia.org/wiki/Lambda_calculus. See also https://en.wikipedia.org/wiki/Combinatory_logic.