1
$\begingroup$

Where "switches" 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 < 1000 switches, but I'm not sure.


Update: I discovered "Cedric", the first working carbon-nanotube CPU, which used just 178 transistors. It used a variant of Subneg, another Turing-complete instruction similar to Subleq.

178 is my new upper bound.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think the universal machine implemented on Rule 110 requires the whole unbounded tape to be initialized, a condition I specifically excluded when I specified "empty memory". If the CPU could somehow do the initialization on its own, it might count, but that could significantly add to the switch count. $\endgroup$
    – gilch
    Jan 2 at 8:14
  • 1
    $\begingroup$ @gilch, it's easy to keep track of the range of initialized memory and implement logic to clear it whenever you move outside the range. $\endgroup$
    – D.W.
    Jan 2 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.