Kerm, please excuse my mild exaggeration, and I MEANT to say that for every output you need ONE gate with several inputs. The gist of what I was saying is that even basic signal decoding takes MANY transistors. Thanks for correcting me before I corrupted his (or her... sorry Ashbad if I got that whole thing wrong.) mind or anything.
@Ashbad
In the long run, an FPGA would be the cheapest for building you own CPU. However, instead of learning soldering, PCB layout, and other useful skills, you would need to learn Verilog, software design, and stuff. Either way, you need to write some things out that you want to do that are feasible.
If you are at all serious about this project, read this book: http://www.scribd.com/doc/13388965/Build-Your-Own-Z80-Computer
It takes you through the ENTIRE process of building your own computer, from the power supply to a CRT monitor. Most of the parts are common and still available. The ones that aren't, I could help you find an alternative. You don't really BUILD your own CPU, but I'll be darned if you don't learn a lot by trying! Think about it...
Some basic criteria I recommend you try to attain are:
1) Build a 8 or 16-bit CPU
a) 4 registers the same size as the CPUs word-size
b) Register processing commands that can put data in and out of the registers.
c) At least 3 ports on the CPU that you can take data from the register and send out so you can have keyboard and video.
d) You need the basic 4 operators add subtract divide and multiply. Tips for multiply and divide are to use shift algorithms so you can multiply and divide by 2.
e) You need a clock that can keep the CPU running at a set speed. Paper is only cool for prototypes.
2) Build a motherboard so you can USE said CPU.
3) Debug and reprogram, or if you decide on logic chips, do what I did and buy a desoldering iron and desolder 200 hours worth or work to start fresh... (Wire wrap is easier to tear apart and stuff, and is a lot like a solderless breadboard in construction...)

And please excuse my excitement over meeting someone with the same daft idea I had! I really do feel like I'm coming on strong with advice! Overall, have fun building it if you continue.

I'm glad to hear you're considering an EE career! As an EE, I do my best to encourage others to get EE degrees. Microcontrollers are chips like PICs and Atmegas (the chip in the Arduino board), and are relatively inexpensive and powerful.

The Java virtual machine uses only about 166 instructions and even commercial processors (like the SuperH and probably ARM) use less than 100. Heck, if you felt like programming it, you could get away with one instruction. 100 is definitely too many for a handbuilt computer.

Definitely agreed, Qwerty. It seems like 16 or so would be more that sufficient to implement something rudimentary and functional to me.

Not really. All the so called "one instruction" computers cheat and have that one instruction take an argument to determine what to actually do.

As for ARM, it actually has a *lot* of opcodes these days. It has long since stopped being a RISC design, even though it is still frequently called RISC. Much simpler than x86, granted, but it has picked up quite a number of extensions and additional instructions over the years.

Just thought http://www.carobotics.org/projects/calculator/ would be a little inspiring for you,

Ah yes, I saw that on all the usual suspect hacking sites like Hackaday. Very impressive; I particularly like the clicking every time it does a calculation. Adept, on IRC you mentioned that you were going to start a new version of your project shortly for next years' competition; could you tell us more about that?

I wouldn't mind seeing someone try to build a simple IC or Processor in macro using only parts available in 1955, and in a small enough size that it can fit on the hood of a DeLorean...

The transistor was invented in 1947, so vacuum tubes were still highly dominant in 1955. You could build some simple logic gates and therefore ICs with a handful of vacuum tubes, but to do any decently-complex calculations or for a microprocessor, you'd have to have a ridiculous quantity of tubes. My memory of some movie is being so vaguely tweaked, I'll try to remember what I'm remembering, something about building a replacement for a broken system out of vacuum tubes.

Well the replacement I'm referring to was for an IC that was fried by a lightning strike. If I understand correctly, the lighting could have hit the first IC in the series and then went to ground, leaving the rest of the time circuits intact. If this were the case, you only really need to replace the one IC with 1950s parts.

Also keep in mind that in 1955, Doc Brown was a millionaire inventor, he easily had the funds and connections to acquire transistors. This would make an interesting Electrical Engineering project if I ever get that far in this hobby, and have the spare time/cash to acquire and work with period parts and equipment.

That makes sense, I understand now, and that would certainly be very fun, and perhaps even feasible. Getting back to the topic at hand, Ashbad, is this project still underway, or did you abandon it for now?