In case you’re wondering why I’m not talking about the murder of Sarah Everard and the fallout from that, I try to avoid covering gender politics on this blog because I have another blog devoted to that alone, and I also tend to avoid saying anything (see Why I’ve Gone Quiet) because cis women need to be heard more than I do on these issues and I don’t want to shout them down. In fact the other blog is quite infrequent for the same reason. It doesn’t mean I don’t care or don’t consider it important.
You are in a living room, circa 1950. In one corner sits a bakelite box, lit up from within behind a hessian grill with a design like rays from a rising Sun at the front, and a rectangular panel carrying names like “HILVERSUM” and “LUXEMBOURG”. In the other corner sits another somewhat similar bakelite box with a series of lamps at the top and a slot at the bottom, into which cards with rectangular windows punched out of them can be inserted. There is a row of push buttons above it. This is the domestic computer. It didn’t exist, but could it have?
In this post I mentioned that some say the last computer which could be “completely understood” was the BBC Micro, released in 1981, and expressed my doubt that this was true because apart from memory size, even an upgraded IBM PC would probably be about as sophisticated. However, this got me to thinking about a tendency I have to minimalise in terms of IT, and wondering how far it could be taken and still leave useful hardware, and that also brings up the question of what counts as useful.
In this other post, I described a fictional situation where, instead of the Apple ][ being one of the first mass market microcomputers, Sinclair ended up bringing out the ZX Spectrum six years early, that is, just after its Z80 CPU was released. That isn’t quite what I said: read the post if you see what I mean. The point is that the specifications of the two computers are very similar and if the ULA in the Speccy is realised via discrete logic (smaller and simpler integrated circuits), all the hardware necessary to construct a functional equivalent to it except for the slightly faster microprocessor was available already, and if someone had had the idea, they could’ve made one. Then a similar mind game arises: how much further back is it possible to go and still manufacture a reasonaly small but workable computer? Could you, for example, even push it back to the valve era?
Apologies for already having said things which sound off-putting and obscurantist. As an antidote to this, I want to explain, just in case you don’t know, how digital computers work. Basically there’s a chip which fetches codes and data from memory. The codes tell the computer what to do with the data and the chip can make decisions about where to look next from the results of what it’s done with those data. It’s kind of like a calculator on wheels which can read instructions from the path its travelling on.
There are two basic design philosophies taken with microprocessors, which for the sake of brevity I’m going to call Central Processing Units, or CPUs. One is to get it to do lots of sophisticated things with a large number of instructions. This is called the CISC approach – Complex Instruction Set Computer. The CPUs in most Windows computers are CISCs. The other is to get it to do just a few things with a small number of instructions, and this is called a RISC – Reduced Instruction Set Computer. Chips in tablets and mobile phones are usually RISCs. In particular they’re probably going to be using one of the CPUs in the ARM series, the Acorn RISC Machine. The Pentium and the like are kind of descended from the very early Intel 8080, which had a large number of instructions, but the ARMs are the spiritual successors of the 6502.
The 6502, which was the CPU used in the Apple ][, BBC Micro and the similar 6510 used in the Commodore 64, were designed with simplicity in mind, and this involved using far fewer transistors than the Z80(A) found in the Spectrum. The latter had 694 instructions, many of which could only be accessed by prefix bytes acting a bit like shift keys on a typewriter. By contrast, not taking address modes into consideration, the 6502 only had fifty-six. Processors usually have single or double cells of memory used to store numbers to work on or otherwise use internally called registers. The Z80 had nineteen, I think, but the 6502 only had six. To be honest, I was always a lot more comfortable using the Z80 than the 6502, and as you may be aware this was a constant source of debate between nerds in the early ’80s, and to some extent still is. The 6502 always seemed really fiddly to me. However, it was also faster than its competitor, and comprised fewer transistors because of the corners which had been cut. Unlike the Z80, it used pipelining: it interpreted the next instruction while executing the previous one, but it was also faster because it used fewer instructions. It needed less time to work out what to do because the list of instructions was much shorter.
Research undertaken in the 1980s counted the proportions of instructions used in software, and it was found, unsurprisingly, that for all processors a small part of the instruction set was used for the majority of the time. This is of course the log-normal distribution which applies to a wide range of phenomena, such as the fact that eighty percent of the income from my clients used to be from twenty percent of them, and that one herb out of five is used in four out of five prescriptions, and so on. In the case of CPUs this meant that if the jobs done by the majority of instructions could be performed using the minority of often-used instructions, the others could be dispensed with at the cost of taking up more memory. An artificial example of this is that multiplying six by seven could be achieved by adding seven to itself six times, and therefore that an integer multiply instruction isn’t strictly necessary. Of course, this process of performing six additions could take longer than the multiplication would in the first place, but choosing the instructions carefully would lead to an optimal set, which would all be decoded faster due to the smaller variety.
The question therefore arises of the lowest possible number of instructions any CPU could have and still be Turing-complete. A Turing-complete machine is a computer which can do anything a theoretical machine Turing thought of in 1936 which consisted of an infinitely long strip of tape and a read-write head, whose behaviour can be influenced by the symbol underneath the head. It more or less amounts to a machine which, given enough time, can do anything any digital computer could do. My description of the calculator on wheels I mentioned above is effectively a Turing machine. What it means, for example, is that you could get a ZX80, rewire it a bit and have it do anything today’s most expensive and up-to-date PC could do, but of course very, very slowly. But it can’t be just any digital computer-like machine. For instance, a non-programmable calculator can’t do it, nor can a digital watch. The question is, as I’ve said, which instructions would be needed to make this possible.
There used to be a very simple programming language used in schools called CESIL (I created and wrote most of that article incidentally – there are various deeply obscure and useless articles on Wikipedia which were originally mine). As you can see from the link, there are a total of fourteen instructions, several of which are just there for convenience to enable input and output such as LINE and PRINT. It’s a much smaller number than the 6502 but also rather artificial, since in reality it would be necessary to come up with code for proper input and output. Another aspect of redundancy is the fact that there are three JUMP instructions: JUMP, JINEG and JIZERO – unconditional jump, jump if negative and jump if zero. All that’s really needed there is JINEG – jump if negative. It can be ensured that the content of the accumulator register is negative in advance, in which case JINEG can perform the same function as an unconditional jump, and since zero is only one greater than a negative integer, simply subtracting one and then performing JINEG is the same as JIZERO. Hence the number of instructions is already down to six, since multiplication and division are achievable by other means, although as constituted CESIL would then be too limited to allow for input and output because it only uses named variables. It would be possible, though, to ensure that one variable was a dummy which was in fact an interface with the outside world via some peripherals.
It has in fact been determined that a machine can be Turing-complete even if it has only one instruction, namely “Subtract One And Branch If Negative”. Incidentally, with special arrangements it can even be done with Intel’s “MOV” instruction, but it needs extensive look up tables to do this and also requires special address modes. Hence there can be a SISC – Single Instruction Set Computer. It isn’t terribly practical because, for example, to add two numbers in the hundreds this instruction would need to be executed hundreds of times. It depends, of course, on the nature of the data in the memory, and this has an interesting consequence. In a sense, this is a zero instruction set computer (which is actually something different officially) because it can be assumed that every location pointed to by the program counter has an implicit “SOBIN” instruction. The flow and activities of the program are actually determined by a memory location field which tells the CPU where to go next. This means that the initial value of the data in the accumulator needs to be fixed, probably as an entirely set series of bits equivalent to the word length.
This would all make for a very difficult machine to work with, but it is possible. It would be very inefficient and slow, but it would also reduce the number of logic gates needed to a bare minimum. It would simply consist of an arithmetic unit which would in fact be a binary adder because of two’s complement. Negative integers can be represented simply by treating the second half of the interval between zero and two raised to the power of the word length as if those numbers are negative.
This is a one-bit binary adder:
It works like this: 0+0=0 with no carry, 0+1=1 with no carry, 1+0=1 with no carry and 1+1=0 with carry. The symbols above, by the way, are XOR – “either – or -” at the top, AND in the middle and OR (actually AND/OR) at bottom right. These conjunctions describe the inputs and outputs where one, i.e. a signal, is truth and zero, i.e. no signal, is falsehood. Incidentally, you probably realise this but this logic is central to analytical philosophy, meaning that there are close links between philosophy, mathematics and computer science and if you can understand logic you can also understand the basis of much of the other two.
Most processors would do all this in parallel – an eight-bit processor would have eight of these devices lined up, enabling any two integers between zero and two hundred and fifty-five to be added and any two integers between -127 and 128 to be added or subtracted, either way in one go. But this could also be done in series if the carry is stored and the serial format is converted to and from parallel to communicate outside the processor. This reduces the transistor count further. All logic gates can be implemented by NAND gates, or if preferable by NOR gates. A NAND gate can be implemented by two transistors and three resistors and a NOR gate with the same components connected differently. Transistors could also be replaced by valves or relays, and it would also be possible to reuse some of the components in a similar manner to the serial arrangement with the adder, although I suspect the point would come when the multiplication of other components would mean this was no longer worthwhile.
I can’t really be precise as to the exact number of components required, but clearly the number is very low. Hence some kind of computer of a reasonable size could been implemented using valves or relays, or discrete transistors. ROM could be realised via fuses, with blown fuses as zeros and working fuses as ones, and RAM by capacitors, Williams tubes, which are cathode ray tubes with plates to feed the static charge back into the cathodes, or with rings threaded onto wires, all methods which have been used in the past. Extra parts would of course be needed but it is nonetheless feasible to build such a computer.
I feel like I’m on the brink of being able to draw a logic diagram of this device, but in practical terms it’s beyond me. I haven’t decided on input and output here, but that could be achieve via arrays of switches and flashing lights. And if this could be done with 1950s technology, who knows what the limit would be?
A Box Of Chocolates 