Wouldn't it be more accurate to say that you need NAND gates and a clock? Identifying a minimal set of primitive components necessary to implement a self-timed computer would be a more interesting problem.

You can build your clock using, guess what, NAND gates, one capacitor and one resistor (not a great clock source, still).

You also need a power source, so you can say the only digital component you need are NAND gates.

TECS (http://www1.idc.ac.il/tecs/) is a great book that leads you through that entire process, too!

Another great book along these lines is CODE, by charles petzold:

http://www.charlespetzold.com/code/

He starts with electricity and builds all the way up to modern computers. It isn't a hands on guide, but it is a very entertaining read.

This is truly a great book and I can't recommend it enough. I've been working through the projects for the past couple weeks.

As the author states, it can be hard for CS students to see the forest for the trees among all the computing topics. I know that while I was learning these topics individually I never took the time to step back and really connect them.

With TECS you get to build each layer and define a an interface between them from logic gates to virtual machines, to compilers, to operating systems, etc. In the end you have a fully functioning computer that you have built from scratch. By removing all the "magic" from the system I feel like I have a much deeper understanding of these topics than I did before.

Isn't an FPGA basically a bunch of NAND or NOR gates whose connections can be arranged as necessary?

No, it's a bunch of registers to hold state and look-up tables that map to your logic. (http://en.wikipedia.org/wiki/Karnaugh_map)

Registers can be made by using a bunch of flip-flops, which are again made using NAND/NOR.