memory for the simplest possible computer (Pi0K)
There are many people who have built computers out of discrete transistors, ICs, relays, and even vacuum tubes. They range from 4-bit machines all the way up to 32-bit.  The 4-bitters of course will be the simplest you can build and do anything.  The very first microprocessor was Intel's 4-bit 4004.

I would start by searching Google for "home-brew 4-bit computers" (without the quotes).

Here's a board from a transistorized 4-bit computer:



As far as memory goes, some of these projects which otherwise are using discrete transistors "cheat" and use SRAM chips.  They are incredibly cheap for moderate amounts of memory, 32KB is $3.28 and requires no clocks and no refresh.

Even if the rest of your computer uses relays, using them for memory will be prohibitively expensive.

If you can get by with 1K bits, you could build one with transistorized flip-flops; 2048 2N3904's will cost 3¢ apiece ($60 altogether, plus the other components which will be even cheaper -- resisters for 1/2 a cent etc). You can get PCB's made for $10 apiece, then hire a kid to stuff them.

Relay computers date all the way back to the late 1930's, and one of the first was the Harvard Mark I.  It's where the name Harvard architecture comes from (separate program space and data, compared to von Neumann architecture that combines the two).

The most famous home-brew relay computer is one built by Harry Porter.



Check out the videos of the computer running.  Reminds me of an old electromechanical telephone exchange.

Here's a portion of another home-brew relay computer called Zusie:



Lots of blinking lights.

And finally, here's a link to a video of a 4-bit adder, made up of 24 relays.  Adders like this are the heart of the ALU (arithmetic logic unit) in a computer.