What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU? Where &quot;switches&quot; are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive because that's a separate component.
I'm not sure if the exact number is known or provable, but an upper bound could be proven by implementing one or pointing to a known implementation.
I am assuming a binary computer with empty memory. You can, of course, load a program to make it work, but said program must be finite in length. Something like Wolfram's (2, 3) UTM, which requires the whole unbounded tape to be initialized, is out.
The first commercial microprocessor was the Intel 4004, with a transistor count of 2,250 (not sure if that's exact), so that's an upper bound.
But that already had a 4-bit data width and multiple opcodes, probably much more than is required for the theoretical minimum CPU. I have heard of 1- and 2-bit CPUs and one-instruction set architectures like Subleq, so I think we can do a lot better than the 4004. I suspect the true answer is &lt; 1000 switches, but I'm not sure.
The Rule 110 cellular automaton is apparently Turing-complete.  If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches.
See also https://softwareengineering.stackexchange.com/q/230538/34181.