How many logic gates are realistically feasible?
You're in luck. Devices already exists that can implement this logic circuit for you. They're called FPGAs.

They consist of millions of logic blocks which can be individually programmed, as well as interconnects which can also be reprogrammed.

It's hard to say what the price would be. If the speed doesn't have to be crazy you might be able to use multiple cheaper devices. But it looks like if you wanted to do this whole thing on one chip, you could. If you can drop like 20k on one chip..

No matter what you do, the resulting device could be pretty small.