Building a Computer: Part I

During my senior year in high school, I was fortunate enough to participate in the Intel International Science and Engineering Fair. At the awards banquet I was seated with fourteen others and we each had the choice of ordering either salmon or steak for our respective entrées. I noticed that while taking our fifteen different orders, our waiter did not write anything down. How on Earth was he going to remember what each of us had requested?!

It turns out the answer is intimately related to Problems 2 and 5 in my last post. Did you realize you always save at least 999 people on the game show? Here’s how:

The person at the back of the line will look at all 999 hats in front of him. If the number of black hats is odd, he will shout “Black!” If the number of black hats is even, he will shout “White!” From this information, the second person in line can deduce from the hats in front of him what the color of his own hat is! For example, if Contestant 1 shouts “Black!” and Contestant 2 sees an even number of black hats in front of him, he can deduce that his own hat is black because the total number of black hats Contestant 1 sees is odd. From information given in Contestant 1’s and Contestant 2’s answers, Contestant 3 can determine his hat’s color via a similar parity argument, and so on. At least $999 will be donated to charity.

How about Problem 5? One solution requires knowledge of how to represent numbers in binary. Let’s say you owe your friend $3,761.50, and want to pay him using pennies and dimes, as well as $1, $10, $100, and hypothetical $1,000 bills. How would you pay him using the least number of monetary tokens? The answer to this is easy – we all learned about the hundredths’ place, the tenths’ place, ones’ place, the tens’ place, the hundreds’ place, and so on in elementary school. The digit in the ones’ place tells us how many $1 bills we need to give our friend, the digit in the tens’ place tells us how many $10 bills we need to give our friend, and so on. Written more suggestively,

3,761 = 3*10³ + 7*10² + 6*10¹ + 1*10⁰ + 5*10^-1 + 0*10^-2

Why does the number 10 appear so significant in the above equation? In the above equation, 10 is called the “base.” In base 10, we write every number as the sum of whole multiples of powers of 10. Notice that none of the bold numbers – the digits – can be greater than or equal to the base (10); they must be between 0 and 9. If one of the bold digits was greater than 9, we could just use a monetary token of higher value to reduce the total number of bills and coins we need to repay our friend. This leads to:

Rule #1: The value of each digit must be less than the base.

Could we use a number other than 10 as our base? Let’s try using 2! I can think of at least one way to write 3,761.50 as the sum of multiples of powers of two:

3,761.50 = 1*2¹¹ + 0*2¹⁰ + 0*2⁹ + 0*2⁸ + 0*2⁷ + 0*2⁶ + 53*2⁵ + 1*2⁴ + 0*2³ + 0*2² + 0*2¹ + 1*2⁰ + 1*2^-1

You’ll notice I’ve chosen 53 as one of my digits. Oops! We have violated Rule #1. Can we rewrite $3,761.50 in a way that respects Rule #1? As it turns out,

3,761.50 = 1*2¹¹ + 1*2¹⁰ + 1*2⁹ + 0*2⁸ + 1*2⁷ + 0*2⁶ + 1*2⁵ + 1*2⁴ + 0*2³ + 0*2² + 0*2¹ + 1*2⁰ + 1*2^-1

Let’s drop all the powers of two on the right hand side to make the expression more succinct:

3,761.50 = 111,010,110,001.1

That’s clearly not right… I’d much rather owe a friend $3,761.50 than $111,010,110,001.1! Have we proven some crazy new law of mathematics? No, we’ve just forgotten to signify that the left-hand side is written in base 10 while the right-hand side is written in base 2. Let’s add subscripts to do this:

3,761.50₁₀ = 111010110001.1₂

This makes more sense. 3,761.50₁₀ and 111010110001.1₂ both represent the same number; I am impartial between owing my friend $3,761.50₁₀ and owing him $111010110001.1₂.

For another way to understand why we need our subscripts, think about the following scenario: Let’s say you’re airdropped into a foreign country and you a see a sign that says only “Papa.” In Spanish, the word papa means potato, whereas in English it is a synonym for father. Without any context, how do you know how to interpret the sign? Maybe all signs should have subscripts attached:

Papa_Spanish = Potato_English

The subscript to tell us which dictionary we need to use to interpret the expression.

Writing in base 2 is called writing in binary. Let’s get some practice:

Exercise 1: Convert 684872.25₁₀ to binary.

Exercise 2: Prove that every number in base 10 has a binary representation, and vice versa (From Exercise 1, you should be able to develop an algorithm for translating between the two languages).

Exercise 3: Convert 684872.25₁₀ to base-16. Base-16 is called hexadecimal. Remember to respect Rule #1 (so no digits greater than 15 allowed), and create some new symbols to use as digits with values greater than 9. Why not use letters? If we assign A to a value of 10, then $latex A_{16} = 10_{10} neq 10_{16} = 16_{10} $.

Writing in base-2 has additional advantages.  We don’t need to memorize many rules for how to combine digits, like 1 + 8 = 9 or 2 + 6 = 8. We just need to remember that 0 + 0 = 0, 1 + 0 = 0 + 1 = 1, and 1 + 1 = 10 (where the first digit on the right hand side is the carry into the next largest place value). In some sense, the binary system is the most frugal way of communicating information.

The binary system is of fundamental importance to computer science. By measuring whether a current is flowing through a wire, we can tell whether the wire is “On” or “Off” – 1 or 0. We don’t need to perform delicate measurements to calculate exactly how much current is flowing, we only need to know whether the wire is dead or alive. The smallest unit of information that your computer uses to perform computations is called a bit, which tells us exactly 0 or 1. The next most complex unit of information is a byte, which is a string of 8 bits and thus has 2⁸ = 256 possible outputs. When purchasing your laptop, you may have measured its memory in gigabytes. A gigabyte is 2³⁰ (more than a billion) bytes and can store 256^{2^30} units of information, or about 1/8^th of an HD movie.

In my next post, I’ll discuss exactly how computations are implemented in circuits using the binary system, and we’ll delve further down the rabbit hole of universal computability, electrical engineering, and quantum information. In the meantime, try the following exercises:

Exercise 4: How on Earth did the waiter remember our orders???

Exercise 5: Solve Problem 5 from my last post.

Exercise 6: We have discussed how we can use the binary system to express numbers. Can we also communicate letters and other characters in binary? Think about bytes, which have 2⁸ = 256 possible outputs. What are we to do with the 256 – 10 = 246 other possible outputs?

Exercise 7: Prove that the real numbers are uncountable. The solution, of course, does not require a knowledge of binary, but is significantly easier to think about in base-2.