bookmark_borderAn Essay on Computation

Since ancient time, humans have been building surprisingly intelligent computers. Computation is a very broad term. It happens not only in man-made computers but also in nature. The basis of computation is deceptively simple: if there is a notion of memory, one can count. By using counting, it is possible to perform addition. Addition is in the basis of multiplication. With addition and multiplication we are half-way there, having almost all of mathematics. Of course, this opening argument just promote me to be the dean of the faculty of gross generalization.

One of the fundamental foundational questions, popularized by Scientific American, is if the universe is analog or digital. While the correct answer is probably “neither and both, it is quantum, it is the solution of the Schrödinger equation for all particles in the universe, it is a complex vector that only the universe can compute”, I find quantum computers juxtaposing analog and digital concepts. A qubit is a superposition (linear combination) of zeros and ones although there is nothing special about choosing zero and one. It is possible, and although sounding exotic, I am sure there are, quantum computers whose state is made of ternary (for example) qubits.

Let’s switch the topic and talk about errors in computation. All our machines make errors and everything around us is imperfect. What is worse, is that people want to scale computation, taking the output of one computational block and feeding it to another. Modern computational platforms are truly humonguous. An average Pentium processor has thousands of NAND-gates. A NAND-gate is the basic logical computational building block of modern von-Neumann computing. As we will see in more tehcnical detail in subsequent posts, a NAND gate is a very primitive device. Even to add two 16-bit numbers we need hundreds of them.

A NAND gate in the device on which you are reading this is made out of CMOS transistors. The CMOS transistor is an analog device, even though we use only two voltages values (the values depend on the process being used), there is always some amount of noise, leakage, and imperfection. The ingenius thing behind the NAND gate is that, after feeding the input voltages, the electrical circuits of the NAND gate bring the output to either the power ground or to the power suppy rail. These two latter values are used for logical zero and one. Let’s say that zero is everything between 0 V and 1.5 V and one is everything between 3V and 5V. This means that no matter if we take 0.1 V and 4.5 V as inputs or 1.2 V and 3.2 V, the output will always be close to 5V, no matter what. So, a NAND gate is self-error-correcting in a way. This allows the scaling-up and chaining of thousands of gates and we know that the Boolean zero/one result is always correct.

Now you have a taste of what I will be writing about. I will try to be practical, precise, sciency, comprehensible, understandable, and fun. And, of course, I will be writing about many things. As one of my favorute Dutch expression says about “koetjes en kalfjes” (Google DuckDuckGo it).