Infinity is a concept that mathematicians are supposed to understand and love but I argue that infinity is more at home in computer science and to understand it you need to know what it looks like. 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>

Infinity is a key, if often hidden, component of computer science arguments and formal proofs. Not understanding the nature of infinity will lead you to conclude all sorts of very wrong, and even silly, results. So let’s discover what infinity is all about and how to reason with it. It isn’t so difficult and it is a lot of fun.

Not in this extract:

• Integers and Rationals
• The Number Hierarchy

Aleph-Zero Where Infinity Begins

There are different orders of infinity something explained a little later. The usual infinity, which can be considered the smallest infinity, is usually called aleph-zero, aleph-naught or aleph-null and is written: 

As this is aleph-zero and not just aleph, you have probably guessed that there are others in the series and aleph-one, aleph-two and so on are all different orders of infinity, and yes there are, probably an aleph-zero of them.

What is this all about?

Surely there is just infinity and that's that?

Certainly not, and the existence of different orders of infinity or the "transfinite" numbers is an idea that plays an important role in computer science and the way we think about algorithms in general. Even if you are not going to specialize in computer science and complexity theory, it is part of your intellectual growth to understand one of the deepest and most profound theories of the late 19th and early 20th centuries. It was the German mathematician Georg Cantor who constructed the theory of the transfinite numbers a task that was said to have driven him mad. In fact contemplation of the transfinite is a matter of extreme logic and mathematical precision rather than lunacy.

Georg Cantor

1845-1918

Unbounded Versus Infinite

Programmers meet infinity sooner and more often than the average person. OK, mathematicians meet it all the time, but perhaps not in the reality of an infinite loop.

Question: How long does an infinite loop last?

Answer: As long as you like.

This highlights a really important idea. We really don't have an infinite loop, what we have is a finite but unbounded loop. If you have read the earlier chapters this will be nothing new, but there is a sense in which it is very much the programmer’s form of infinity. Something that is finite, but unbounded, is on its way to being infinite, but it isn't actually there yet so we don’t have to be too philosophical.

Consider again the difference between the following two sets:

U = the set of counting numbers less than n

N = the set of natural numbers, i.e. 0,1,2,3,

Set U is finite for any n, but it is unbounded in that it can be as big as you like depending on n.

On the other hand, N is the real thing - it is an infinite set.
It is comparable to the difference between someone offering you a very big stick to hold - maybe one that reaches the orbit of the moon, the sun or perhaps the nearest star- and a stick that is really infinitely long.

A stick that is finite but "as big as you like" is similar to the sort of sticks that you know. For one thing it has an end. An infinite stick doesn't have an end – it is something new and perhaps confined to the realm of theory.

The same arguments hold for U and N. The set U always has a largest member but N has no largest member. Infinity is different from finite but unbounded. 

When you write an "infinite loop" you are really just writing a finite but unbounded loop - some day it will stop.

Often finite but unbounded is all we need to prove theorems or test ideas and it avoids difficulties. For example, a finite but unbounded tape in a Turing machine does have a last cell, but an infinite tape doesn't. A Turing machine working with tape that doesn't have an end is more than just a mechanical problem – how do you move it? Indeed can it move? You can avoid this particular problem by moving the reading/writing head, which is finite, but this doesn’t solve all the conceptual difficulties of a tape that is actually infinite.

In the early days of computer science there was a tendency to prefer “finite but unbounded”, but as the subject became increasingly math-based, true infinity has replaced it in most proofs. This is a shame as the programmer’s infinity is usually all that is needed.