Numbers are central to computation and computer science but they are often regarded as the province of the mathematician. Programmers need some background in what numbers are and this is what this extract from Chapter 6 of my recent book is all about.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice 
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
11. Information Theory 
12. Coding Theory – Splitting the Bit
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

There is a complexity hierarchy of numbers starting from the most simple, and probably the most obvious, working their way up through rationals and irrationals to finally the complex numbers.

I'm not going to detour into the history of numbers, fascinating though it is, and I’m not going to go into the details of the mathematical theory. What is important is that you have an intuitive feel for each of the types of number, starting with the simple numbers that we all know.

Integers and Rationals

All you really need to know is that in the beginning were the whole or natural numbers. The natural, or counting, numbers are just the ones we need to count things and in most cases these don't include zero which was quite a late invention. After all who, apart from programmers, counts zero things?

The integers are what you get when you add zero and negative numbers. You need the negatives to solve problems like "What do I add to 5 to get 3?" and zero appears as a result of "What is 5-5?".

You can motivate all of the different types of number by the need to solve equations of particular types. So the integers are the solution to equations like:

x+a=b

where a and b are natural numbers and x is sometimes a natural number and sometimes the new sort of number - a negative integer. Notice that the definition of the new type of number, an integer, only makes use of numbers we already know about, the natural numbers.

Notice that we can immediately see that the natural numbers and the integers are infinite in the usual sense of the term – there is always another integer. You can also see that if you were asked to count the number of integers in a set you could do this. The integers are naturally countable. If you are surprised that the fact that something is countable is worthy of comment, you need to know that there are things that you cannot count – see later.

Next in the number hierarchy come the fractions, the numbers which fill in all the spaces on the number line. That is, if you draw a line between two points then each point will correspond to an integer or a fraction on some measuring system. The fractional numbers are usually known as the rationals because they are a ratio of two integers. That is, the rationals are solutions of equations like:

x*a=b

where again a and b are what we already know about, i.e. integers, and x is sometimes an integer and sometimes the new type of number – a rational. The definition of the new type of number once again only involves the old type of number.

A small part of the number line to every rational number there is a point but is the reverse true? Is there a number for every point?

Notice that if you pick any two points on the line then you can always find another fractional point between them. In fact, if you pick any two points you can find an infinity of fractions that lie between them. This is quite unlike the integers where there most certainly isn't an integer between every pair of integers - for example, what is the integer between 1 and 2? Also notice that this seems to be a very different sort of infinity to the countable infinity of the integers. It can be considered to be a "small" infinity in that there are an infinite number of rational points in any small section of the line. Compare this to the "big" infinity of the integers which extends forever. You can hold an infinite number of rationals in your hand, whereas it would be impossible to hold an infinity of integers in any container, however big

The infinity of the rationals seems to be very different from the infinity of the integers, but is it really so different?

The Irrationals

Given the integers and the fractions is there a number to every point in the number line and a point to every number? No but this fact is far from obvious. If you disagree then you have been exposed to too much math - not in itself a bad thing but it can sometimes make it harder to see the naive viewpoint.

It was followers of Pythagoras who discovered a shocking truth - that there were points on the number line that didn't correspond either to integers or fractions.

The square root of two, √2, is one such point. You can find the point that corresponds to √2 simply by drawing a unit square and drawing the diagonal - now you have a line segment that is exactly √2 long and thus lines of that length exist and are easy enough to construct. This means you can find a point on the line that is √2 from the zero point quite easily. The point that is √2 exists, but does a rational number that labels it?

So far so much basic math but, and this is the big but, it can be proved (fairly easily) that there can be no fraction, i.e. a number of the form a/b that is √2.

You don't need to know the proof to trust its results but the proof is very simple. However, skip this section if you want to.

Suppose that you can express √2 as a rational number in its lowest terms, i.e. all factors canceled out, as a/b. Then (a/b)² is 2 by definition and hence a²=2b².

This implies that a² is even and hence a has to be even (as odd numbers squared are still odd).

Suppose a=2c for some integer c. Then 4c²=2b² or b²=2c² and hence b² is also even and hence b is even. Thus b=2d for some integer d.

Now we can write a/b=2c/2d, which means that a/b isn't in its lowest form as we can now remove a factor of 2 to get c/d.

As you can reduce any fraction to its lowest form by canceling common factors there can be no a/b that squares to give 2.