12
\$\begingroup\$

I'm wondering what the simplest design for a general-purpose (Turing complete) computer is. To my surprise, I haven't found much on the web. Surely this is a known problem?

\$\endgroup\$
11
  • 6
    \$\begingroup\$ simplest design[…]haven't found much [information] A more useful metric is cost effective, including end-user time, if any, and development cost/developer time. \$\endgroup\$
    – greybeard
    Dec 10, 2022 at 7:34
  • 4
    \$\begingroup\$ Somewhere between a few hundred, and NaN. The space-constrained Turing complete category is of course the more practical and relevant case (all real computers have finite memory/states), but it also leaves open the option for near-fatally limited systems, like the toy projects with a 4-bit word size operating on 32 words of memory; I don't think that's enough to implement a higher-level VM that could perform IO on an external store. (Has anyone done this to prove it, though?) \$\endgroup\$ Dec 10, 2022 at 8:26
  • 38
    \$\begingroup\$ Computers existed before transistors were invented; so no transistors are needed at all. Or are these ruled out? \$\endgroup\$
    – Justme
    Dec 10, 2022 at 9:02
  • 3
    \$\begingroup\$ Interesting question, though definitions of 'general purpose' or 'useful' might bog you down. How much memory do you need? Would 2+2 be an adequate test program, or do you want to play Doom? Maybe Retrocomputing might be a better site, they're used to thinking small there. Truing tarpit languages need not use much logic, with few instructions to interpret. Have you looked at the character set of Brainf*ck for instance? \$\endgroup\$
    – Neil_UK
    Dec 10, 2022 at 9:43
  • 4
    \$\begingroup\$ You say "general-purpose (Turing complete)". These are two very different things. No computer is Turing-complete, for the simple reason that it's embedded in a universe that has a finite total storage capacity. \$\endgroup\$
    – TLW
    Dec 10, 2022 at 21:27

8 Answers 8

19
\$\begingroup\$

6 transistors should do the trick.

Of course, there's the question of what counts as a "Turing-complete" computer, since it's not actually possible to build a Turing-complete computer using any finite amount of matter. I'm going to assume that a computer is "practically Turing-complete" if it can easily be made to simulate a Turing machine for an arbitrarily large number of steps by giving it an arbitrarily large amount of memory and allowing it to run for an arbitrary large amount of time.

I'm also assuming that we're allowed to have a shift register for free, on the grounds that a shift register is merely memory and doesn't compute anything.

Given a shift register and a handful of logic gates, we can implement Rule 110. We need a shift register which, for some large \$n\$, outputs the \$n\$th-last, \$n+1\$th-last, and \$n+2\$th-last input bits. (Alternatively, we can use 3 shift registers: one which outputs the \$n\$th-last bit, one which outputs the \$n+1\$th-last bit, and one which outputs the \$n+2\$th-last bit.) We also need a combinational logic circuit which implement the Rule 110 transition rule. If we simply connect the outputs of the shift register to the input of the logic circuit and vice versa, and initialize the shift register with a Rule 110 pattern, then the circuit will compute the evolution of the pattern.

The Rule 110 transition rule can be implemented using 3 NOT gates, 2 2-input NOR gates, and one 3-input NOR gate, as follows: nor(nor(b, c), nor(not(a), not(b), not(c))). Using resistor-transistors logic, each of these gates can be implemented using several resistors and one transistor.

So that's my answer: you can build a general-purpose computer out of a shift register, some resistors, and 6 transistors.

\$\endgroup\$
10
  • 5
    \$\begingroup\$ "shift-register for free" didn't jump out at me on first reading. But I would disagree that something within memory is a "general-purpose computer." "Rule 110" in the article "is capable of supporting universal computation." But without the shift register, a device would not be a rule 110 device. \$\endgroup\$
    – WGroleau
    Dec 12, 2022 at 7:19
  • \$\begingroup\$ @WGroleau Well, I think a shift register could be implemented using a magnetic tape or something. You'd probably need a few more transistors or something to amplify the signal. As for your statement that you would disagree that something within memory is a general-purpose computer, I'm not quite sure what part of my answer you're disagreeing with, because I'm not claiming that something within memory is a general-purpose computer. My claim is that the combination of a shift register, some resistors, 6 transistors, a power source, and a clock source is a general-purpose computer. \$\endgroup\$ Dec 12, 2022 at 13:46
  • 2
    \$\begingroup\$ @Tanner-reinstateLGBTpeople a tape-based Rule 101 would be pretty neat, if you could make it work. Totally useless, of course. Even more useless than a tape-based Turing machine. \$\endgroup\$
    – user253751
    Dec 12, 2022 at 16:19
  • \$\begingroup\$ I don't know whether it was my typo or the interface of that <censored> autocorrect, but I meant "without". \$\endgroup\$
    – WGroleau
    Dec 12, 2022 at 18:26
  • \$\begingroup\$ In the late 1970s, I worked with a machine that had lots of transistors, but its software was on a spinning magnetic drum. So I'll have to concede such a drum (or tape) could be considered a shift register. The program was not in sequence—the programers had figured out how long it would take to do each instruction and placed the next one so it would arrive at the read head at the right time. \$\endgroup\$
    – WGroleau
    Dec 12, 2022 at 18:33
11
\$\begingroup\$

From "the history of information" page on the Manchester transistor computer:

The 1953 machine had 92 point-contact transistors and 550 diodes, manufactured by STC. It had a 48-bit machine word. The 1955 machine had a total of 200 point-contact transistors and 1300 point diodes, which resulted in a power consumption of 150 watts.

So, 92 transistors is probably the number to beat. However,

The Computer also used a small number of tubes in its clock generator, so it was not the first fully transistorized machine

so you may have to add a few more for the clock driver (or stick with valves there)

\$\endgroup\$
6
  • 3
    \$\begingroup\$ While “92 transistors” is technically true, surely the diodes were used for logic gates? \$\endgroup\$
    – Michael
    Dec 10, 2022 at 21:34
  • \$\begingroup\$ @Michael But of course. \$\endgroup\$
    – user16324
    Dec 10, 2022 at 21:35
  • \$\begingroup\$ One can opt for thermionic valves all the way and use ZERO transistors. The clock gen can be derived from the power supply. Utility power has pretty stable frequency these days. Be prepared for a higher power bill (ENIAC used 150 KILO Watts). \$\endgroup\$
    – fraxinus
    Dec 10, 2022 at 23:24
  • 4
    \$\begingroup\$ @fraxinus that's obvious, but changing the rules of the question. Using mains as the clock, you may be able to use relays and avoid valves too, but 50Hz cripples the machine; long before 1953, the Pilot Ace (valve) was clocked at 1 MHz. \$\endgroup\$
    – user16324
    Dec 11, 2022 at 14:32
  • \$\begingroup\$ @fraxinus: If one were willing to sacrifice speed for parts count, I wonder if it would have been possible to use a resistor-capacitor-transformer-triode blocking oscillator to hold a decimal digit? Have most oscillators set up to run at about 1/20 of the master clock rate, but get "nudged" by the master clock, so that the oscillator will be able to run at any of twenty phases relative to a primary reference phase generator. \$\endgroup\$
    – supercat
    Dec 12, 2022 at 21:42
8
\$\begingroup\$

"Turing-complete" is a very abstract concept, and you're using it as a shorthand for "Turing-complete-with-usable-but-not-infinite-memory", or in your phrase, "general purpose computer."

To get an answer, you're going to have to refine your criteria until it's answerable. For example, while Conway Life and the Minsky Register Marchines are Turing Complete, you need a big one to be a "general purpose computer". Interesting material about this is here. These kinds of machines have extremely simple "CPU"s but lots of memory, and we're excluding memory because there's no reasonable way to specify how much. So a real, small, general-purpose computer will have a more complex functionality but smaller amount of memory.

To get an answer to your question, you'll need to define what the "general purpose" computer has to be able to do. Run Linux? Run Windows? Run Python? A video game? Does it have to be implemented? Be clear that whatever you choose, there are "no true Scotsman" reasons to exclude it.

One answer is obtainable from looking at an implemented computer with TTL chips, able to play a certain level of videogame, such as the Gigatron. If you look up the 15 different kinds of chips you'll be able to count the transistors, or see the estimate kindly added by Davide.

As its website says:

How many logic gates does the processor have?
930, depending a bit on what you include in the count.

Emphasis mine: we should exclude the RAM, surely. The ROM? If we continue like this we'll be down to the ALU. And then, well, why not exclude the multiplication logic because we can code that in software (ie, use more memory). It's a very slippery slope with no, clear, distinguished place to stop.

So your question needs to be: How many transistors does it take to make a useful general purpose computer which can do X.

The following is the chip list for the Megatron, which gives you an indication of scale and complexity. Which would you exclude for your metric? Perhaps the RAM? The ROM?

Function/module Description Part/value Count
1 Clock Hex inverter (74HCT) 74HCT04 1
2 Program Counter, X register 4-bit presettable counter '161/'163 74HCT161 6
3 Program ROM EPROM 1Mb (64Kx16) 27C1024 1
4 IR,D,XOUT registers 8-bit D-type register 74HCT273 3
5 Databus en input Octal bus driver non-inv 74HCT244 2
6 Control unit Dual 2-to-4 decoder 74HCT139 1
7 Control unit, ALU Dual 4-to-1 multiplexer 74HCT153 9
8 Control unit 3-to-8 decoder 74HCT138 2
9 Control unit Octal inverting buffer 74HCT240 1
10 Control unit Quad 2-input OR 74HCT32 1
11 ALU 4-bit adder 74HCT283 2
12 AC, OUT and Y registers Octal D-type flip-flops with common enable 74HCT377 3
13 Address unit Quad 2-to-1 line data selector 74HCT157 4
14 Data RAM SRAM 32k x 8 62256 1
15 Input register 8-bit shift register with 3-state output 74HC595 1
38

Edited to add: Then, assuming an average of 26 transistors per 74xx IC, that's a total of about 1000 transistors. Assuming an average of 2.5 transistor per bit for the RAM, that's 640,000 transistors, dwarfing the number of transistors in all the other ICs.

\$\endgroup\$
9
  • \$\begingroup\$ You can cut the transistor count down by a lot if you use mask ROM instead of EPROM. \$\endgroup\$
    – Hearth
    Dec 10, 2022 at 16:24
  • 3
    \$\begingroup\$ If you're minimizing transistors, you also want a bit-serial design. A significant portion of your logic can be TDM'd. \$\endgroup\$
    – TLW
    Dec 10, 2022 at 21:25
  • \$\begingroup\$ @TDM thanks for comment, what does "TDM" stand for? \$\endgroup\$
    – jonathanjo
    Dec 10, 2022 at 21:36
  • 2
    \$\begingroup\$ @jonathanjo: Time-Domain Multiplexed i.e. the same resource is used for different data at different times. \$\endgroup\$ Dec 12, 2022 at 4:03
  • \$\begingroup\$ @dave_thompson_085 ah of course, didn't recognise it as a verb. (But as they say, "the great thing about English is you can verb any word"). Certainly, all true scotsmen multiplex to minimise transistor count. :-) \$\endgroup\$
    – jonathanjo
    Dec 12, 2022 at 12:16
6
\$\begingroup\$

The first fully integrated CPU was the Intel 4004 with 2300 transistors. Of course, you bump up the transistor count by adding memory.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Early models of the PDP-8 minicomputer had a similar number of transistors in the CPU. \$\endgroup\$
    – Dave Tweed
    Dec 10, 2022 at 13:00
6
\$\begingroup\$

Well... Call me pedantic, but...

The answer is zero. You don't need transistors to make a general purpose computer.

This isn't even theoretical, many, many computers have been made that don't use transistors.

This is how things were done before we invented/discovered semiconductors.

Interestingly, it's also looking like we might be going back in that direction for some specific use-cases.

\$\endgroup\$
1
3
\$\begingroup\$

You can implement a Turing complete computer with one instruction. This will probably reduce the amount of hardware you need to implement the CPU. Now you just need to decide how many bits, bytes, or Terrabytes of memory you need to add until you would call it a general purpose computer.

\$\endgroup\$
1
  • \$\begingroup\$ Indeed, that Wiki article says The first carbon nanotube computer is a 1-bit one-instruction set computer (and has only 178 transistors). Not sure if that implementation is Turing-complete; with only 1 bit per instruction (if that's what they mean by 1-bit), that's not much branch displacement for a dec-and-branch or whatever instruction they implemented. It might still be a Turing-complete; software can maybe deal with that limitation. \$\endgroup\$ Dec 13, 2022 at 3:43
0
\$\begingroup\$

A Turing complete machine is a theoretical construct that was never intended as an actual and practical to construct machine. One problem with the actual construction of such a machine is that it is assumed to have an unlimited amount of storage space. If it does not have that unlimited amount of storage, then it is not really a Turing complete device. It is, instead a finite state machine. Many "examples" of a Turing complete machine show this storage as a (paper) tape which can have different symbols written/erased/rewritten in each location. But this could also be a more modern form of memory. If a modern memory system were used, it would still need to be infinite. And that would require an infinite number of transistors.

Even with a tape memory an infinite amount of tape would be required and, using modern and practical methods of managing such amounts of tape storage would also require an infinite amount of electronics which again means an infinite amount of transistors or similar devices.

If you only want to simulate a Turing Complete machine which would be limited to problems that could be computed with limited memory, then the number of transistors would, of necessity, be dependent on the actual set of problems selected. Thus, your question can not be answered without more information. And, in general, I suspect that it would be a difficult, if not impossible problem to come up with an actual minimum number of transistors unless you elect to use zero transistors by using other logical elements instead.

And there lies your actual answer. You do not need any transistors to build a Turing complete machine. But you are going to need one or more elements of some type to construct logical devices.

It appears that most research on Turing complete is done with computer languages instead of actual, physical devices. In any case I would suggest that you do some research on Turing complete languages and machines. Here is a start:

https://en.wikipedia.org/wiki/Turing_machine

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Why would managing an infinite tape require anything else than "move tape one bit left" and "move tape one bit right"? You don't even have to check if you reached the end! \$\endgroup\$
    – pipe
    Dec 10, 2022 at 12:33
  • 1
    \$\begingroup\$ Don't forget that the TM state table also requires an arbitrarily large (but finite) amount of storage. \$\endgroup\$
    – Dave Tweed
    Dec 10, 2022 at 12:54
  • 4
    \$\begingroup\$ @DaveTweed The Universal Turing Machine construction lets you pack the instructions onto the data tape. \$\endgroup\$
    – wizzwizz4
    Dec 10, 2022 at 23:31
0
\$\begingroup\$

I'd suggest that the important point to understand is that a bit-serial computer uses far fewer switching devices than a bit-parallel one. So something like the LGP-30 had roughly 100 "tubes" and there are designs around using roughly 100 relays. In all cases however this excludes a suitable memory device, often a drum or a disc supplying a bit-serial operand which is combined with another from a shift register, and excludes the minimal electronics needed to support e.g. an ASR-33 Teletype.

Somebody else has made the point that older machines typically contained a substantial number of diodes, used for both OR gates and sometimes microcode. However these can be usually be replaced by resistors, provided that enough attention is paid to the switching threshold of the next active device.

\$\endgroup\$

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